Парадокс Эльханана Мозеля
Задача
Вы бросаете игральную кость до тех пор, пока не выпадет 6. Каково среднее ожидаемое число бросков (включая тот, который дал 6) при условии, что во всех предыдущих бросках выпадали четные числа?
Подсказка 1
Большинство, в том числе и среди математиков, считает, что ответ равен 3. Они объясняют это примерно так: раз могут выпадать только четные числа, то задача эквивалентна бросанию кубика, у которого на двух гранях написано «2», на двух — «4», а еще на двух — «6». Но тогда вероятность выпадения грани «6» равна 1/3, следовательно, ожидаемое число бросков до выпадения первой шестерки равно 3.
Эти рассуждение и ответ — неправильны!
Подсказка 2
Давайте аккуратно опишем, как устроены бросания и в чем на самом деле состоит условие, что во всех предыдущих бросках выпадали четные числа. Мы рассматриваем (потенциально бесконечную) последовательность выпадения на кубике чисел 1, 2, 3, 4, 5, 6. Каждая последовательность заканчивается первым выпадением шестерки. Среди всех таких последовательностей выбираются только те, в которых до шестерки не было нечетных чисел 1, 3, 5. Спрашивается, какова «в среднем» длина таких последовательностей.
Решение
Разумеется, эту задачу можно решить с помощью «тяжелой артиллерии» типа формулы Байеса, но мы покажем очень элегантное и простое решение, придуманное Полом Каффом.
Пусть мы начинаем бросать кость и записываем результаты в строчку. Если выпадает нечетное число (1, 3, 5), то объявляем серию бросков неудачной и переходим на следующую строчку. Как только выпала шестерка — броски заканчиваются. Средняя длина последней строчки и будет ответом на задачу.
Отметим, что средняя длина последней строчки будет ровно такой же, как и средняя длина любой строчки. Это можно объяснить так. Рассмотрим бросание кубика, на котором написаны числа 2, 4, 6(1), 6(3), 6(5), 6. Пусть по-прежнему каждая из четырех шестерок заканчивает эксперимент (строчку), но если это «истинная» шестерка, то мы объявляем эксперимент удачным и подсчитываем число сделанных в нем бросков, а если это шестерка с нечетной цифрой в скобках, то объявляем эксперимент неудачным и забываем. Ясно, что средняя длина эксперимента не зависит от того, объявляли мы какие-то из экспериментов неудачными или нет. Поэтому достаточно сосчитать среднюю длину произвольной строчки.
В каждой написанной нами строчке все цифры, кроме последней — двойки и четверки. Любая из цифр 1, 3, 5, 6 заканчивает строчку, поэтому при каждом броске вероятность окончания строчки равна 4/6. Теперь если S — математическое ожидание длины строки (то, что мы имели в виду, говоря о «среднем ожидаемом числе бросков»), то S вычисляется из уравнения
откуда сразу находим S = 1,5. Смысл этого уравнения такой: с вероятностью 4/6 результатом броска будет цифра, которая закончит строчку, а с вероятностью 2/6 строчка продолжится. Но так как продолжение строчки состоит в таком же бросании кубика, то оно имеет среднюю длину, также равную S, то есть вся строчка, если она не закончилась сразу, имеет среднюю длину 1 + S.
Послесловие
Эту забавную головоломку предложил профессор MIT Эльханан Мозель (Elchanan Mossel). Строго говоря, она не является парадоксом, поскольку имеет четкое и совершенно строгое решение. Парадоксальность ей придает только то, что очень многие люди отказываются принимать это решение и настаивают на своей (ошибочной) версии с ответом 3.
Израильский математик Гиль Калай опубликовал задачу Мозеля в своем блоге под рубрикой TYI — test your intuition («проверьте свою интуицию»), предложив читателям блога выбрать один из вариантов ответа. Среди вариантов предлагались 1, 3/2, 2, 5/2, 3, 7/2 и 4. Поначалу перевес неправильного ответа «3» был просто подавляющим — количество выбравших его превышало 77%. Потом, после того, как в блоге Гиля появились несколько комментариев известных математиков о том, что задача не столь проста, как кажется на первый взгляд, результаты голосования чуть-чуть изменились. Однако и сейчас, на момент публикации Послесловия, на страничке голосования принят 1881 голос, из которых 975 (52%) предпочли вариант «3», а правильный ответ выбран всего 413 участниками (22%).
Разумеется, это не первая вероятностная задача, в которой интуитивно очевидный ответ оказывается неверным. Приведу еще несколько примеров таких задач. Начну с относительно малоизвестной.
Представьте, что в нашем распоряжении есть неограниченный запас белых и черных шариков и урна, в которой поначалу лежит всего два шарика — черный и белый. Мы начинаем повторять следующие действия:
1) вытаскиваем из урны случайный шарик;
2) возвращаем его обратно;
3) добавляем в урну еще один шарик того же цвета.
В какой-то момент количество шариков в урне станет равным 1000. Какова вероятность, что белых из них не менее 800?
Интуиция буквально кричит, что если в начале нам «повезет» и первый вытащенный шарик окажется белым, то дальше уже белый вытаскивается с вероятностью 2/3, а, следовательно, на очередном ходу в урне будет уже три белых шарика из четырех, и так далее. В общем, кажется, что попадание «на край», когда шариков одного цвета будет существенно больше, чем другого, является очень вероятным событием, — ну, а в половине таких случаев этот цвет окажется именно белым.
На самом же деле все расклады от 1:999 до 999:1 оказываются равновероятными (это называется равномерным распределением), поэтому вероятность наступления события «не менее 800 белых шариков» в точности равна отношению количества вариантов, в которых таких шариков не менее 800 (то есть 999 − 799 = 200), к общему количеству равновозможных вариантов (999). Ответ 200/999 настолько контринтуитивен, что в него просто невозможно поверить, пока не сосчитаешь аккуратно.
Еще один очень простой пример основан на бросании монетки (его часто называют нетранзитивной игрой Пеннея в честь Уолтера Пеннея, открывшего эту нетранзитивность в 1969 году).
Алиса и Боб бросают монетку до появления одной из двух комбинаций — «орел, орел, решка» или «решка, орел, орел». Первая из них (ООР) пусть будет выигрышем Алисы, а вторая (РОО) — выигрышем Боба. Кто будет выигрывать чаще, и во сколько раз?
Интуиция говорит, что если сами комбинации равновероятны, то Алиса и Боб будут выигрывать одинаково часто. Однако это вовсе не так (объяснение см., например, в статье «Лучшее пари для простаков», в которой приведены вероятности выигрыша для этой и других подобных игр). А в рассказе Сергея Мельникова «Прыжок через козла» описан случай, когда студенты-математики играют в эту игру со своим преподавателем физкультуры, чтобы получить у него зачет.
Пожалуй, еще более известным является «парадокс двух детей»:
У мистера Смита два ребенка, по крайней мере один из которых — мальчик. Чему равна вероятность того, что оба его ребенка — мальчики?
Правильным ответом на него обычно считается 1/3 (а не интуитивно напрашивающийся ответ 1/2), хотя на самом деле все немного сложнее, потому что у этой задачи нет однозначно понимаемой постановки. В частности, непонятно, как именно «случайно» выбирается один из детей Смита. Если мистер Смит выбирает одного из своих детей (старшего или младшего) с помощью подбрасывания монетки, а затем просто сообщает нам его пол при помощи словесной конструкции «по крайней мере один из моих детей — {мальчик/девочка}», то интуиция нас не обманывает: вероятность того, что пол другого ребенка будет таким же, строго равна 1/2.
Еще одной контринтуитивной вероятностной задаче была посвящена прошлогодняя задача «Игра в кости». Ну и, безусловно, в этом же ряду одно из почетных мест занимает задача Монти Холла, которой была посвящена одна из первых статей в задачном разделе на «Элементах».
2. Искусственные приемы выглядят очень красиво. Однако в целях обучения, а не привлечения внимания к красоте решения, на мой взгляд необходимо использовать "регулярные" методы (вероятностное пр-во и т.д.). Они позволяют решать задачи не придумывая каждый раз новых приемов.
-
Видите ли, как раз регулярные методы здесь очень легко приводят к ошибке.
И задачи на "Элементах", как я понимаю цель этого проекта, - не замена регулярному обучению по той или иной специальности, а именно демонстрация красот, которые в этой специальности возможны.-
1. К сожалению на вопрос в предыдущем посте Вы не ответили.
2. В применении "регулярных" методов в данном случае нет никаких затруднений.
Вероятность последовательности длиной k, заканчивающейся 6 и содержащей только 2 и 4 есть
P(k)=C(1/6)(2/6)^(k-1),
где константу С надо выбрать из условия нормировки => C=4.
Т.о. средняя длина последовательности 3/2.
-
Вероятность того что цепочка будет длиной 1:
1/6 (сразу выпала 6) + 1/2 * 1/6 (сначала выпала 135 которую мы проигнорируем, потом 6) + ... = 2 * 1/6
Вероятность того что цепочка будет длиной 2:
(2/6 (сразу выпала 2,4) + 1/2 * 2/6 (сначала выпала 135, потом 24) + .. ) * 1/6 (и 6ка в конце) = (2/6)^2
Вероятность того что цепочка будет длиной n: (2/6)^n
Суммируем S*p(S): https://www.wolframalpha.com/input/?i=SUM(n%2F3%5En)
Неверный результат 0.75.
--
К сожалению, финт с S+1 мне остался непонятен.
-
Я так понимаю, формула суммирования тут неверна.
Суммарная вероятность всех исходов должна быть равна единице, потому что иначе мы как бы учитываем отброшенные броски. Более правильно считать как SUM( S * p(S) ) / SUM ( p(S) ), что как раз даёт 0.75 / 0.5 = 1.5-
В целом вижу решение на пальцах.
Пусть из N бросков пусть мы получили 100 последовательностей из одной 6ки.
Последовательностей длиной два будет в 3 раза меньше, потому что нужно ещё выкинуть 2 или 4. Для длины 3 будет ещё в 3 раза меньше и т.д.
К примеру: 100, 33, 11, ...
Ожидаемое среднее считается по формуле E(S) = ∑S * P(S)
P(S) = Кол-во бросков при длине S / всего бросков N
E(S) = ∑S * Num(S) / N
Выходит 1*100 + 2*33 + 3*11 + .. / N, где N = 100 * ∑(1/3)^x = 150
1*100 + .. = 225, и результат 1.5-
Отличное решение, но, я так понял, N - это число последовательностей, а не бросков. Получается, мы делим общее число бросков на количество последовательностей, и получаем среднее число бросков для "каждой" последовательности, и, следовательно, среднее число бросков для искомой последовательности, ведь она относится к "каждой" (если в единицах размерностей (или просто - в размерностях): [число бросков (для данной длины последовательности)]*[количество последовательностей (данной длины)]+...(аналогичные члены числа и количества (другой длины))/[(общее) количество последовательностей]=[число бросков (среднее)] т.е. ∑([ч.б.]*[к.п.])/[общее к.п.]=[среднее ч.б.]). Т.о. у вас, более того, и P(S) - число последовательностей, а не бросков, а именно - расщепление (от 100%) данной последовательности от других, т.е. просто вероятность последовательности (в данной задаче вами приравниваемая к числу последовательностей, ведь мат. ожидание). Для простоты (?) можно было вместо 100, 33, 11 и т.д. сразу писать n, n*1/3, ....., n*(1/3)^(x), ведь тут важно отношение, а не абсолютная величина. Вот перефразированное ваше решение: нам нужно найти (1*n+2*n/3+3*n/9+4*n/27+...) где n- вероятность того, что наша последовательность состоит из 1 символа (броска), n/3, n/9 и т.д. - это вероятности двух, трёх и более символьных решений, а множители 1,2,3 и т.д. это количество бросков для решения данной длины (1 бросок для одно-символьного решеня, 2 для 2 - тут они совпадают) - сейчас мы считаем среднее количество символов (бросков) для всех последовательностей, ведь вероятность последовательности - это отношение встерчаемости данной последовательности к общему числу всех возможных последовательностей, и, умножая эту вероятность последовательности на число символов в длине данной последовательности, мы находим число символов, которое в среднем даёт данная последовательность при случайном выборе относительно общего числа последовательностей (например, если с 10% мы можем попасть в 11, а других последовательностей нет (по умолчанию - пустые множества или 0, поэтому это 10% , а не 100%, - нету отношения 1к1 из-за отсутствия других последовательностей), то мы попадём или в ничего, или, в 1 случае из 10, в 11, и в среднем мы получим 2/10, поэтому вклад последовательности "11" в данной выборке=0.2 символа, если же другие последовательности не пустые - то также учитывается и их вклад: тот же 0 был бы символом и в 9 из 10 случаев вы бы попали в 1 символ, и вклад последовательности (множества чисел) "0" был бы = 0,9, а средняя длина 0,9+0.2=1,1 символа в данной выборке двух последовательностей)#; но нам неизвестно значение n - найдём эту вероятность (заранее зная, что сумма всех вероятностей возможных последовательностей равняется 1, т.е. 100%): (n+n/3+n/9+...)=1, выносим n за скобки и считаем сумму ряда ∑(1/3^(m-1)), получаем 1.5*n=1, n=4/6. Выносим n за скобки и в первом уравнении, теперь уже зная n: n*∑(k/(3^(k-1)). В итоге имеем n*2.25 и, т.к. n=4/6, то ответ=1,5. Но, всё же, не лишне, что вы написали всё именно так, как рассуждали об этом сами - это даёт пищу для размышлений.
Кстати об 1+S в решении на сайте, до меня сейчас дошло: вклад (по аналогии с тем, как я расписал решение #) последовательности с 1 символом это 1*4/6 где 4/6 - вероятность последовательности из 1 символа (6), а дальше они избежали этой ненужной демагогии (с 1/3, 1/9, 1/27...) а просто сказали, что все случаи продолжения строки, которые имеют шанс 2/6 (если сначала выпала 2 или 4) имеют длину 1+S т.к. 1 символ у нас уже есть (это выпавшая 2 или 4) а S - это средняя длина строки, ведь последующие броски, после того, как у нас выпала 2 или 4, не зависят вероятностно от нашего первого броска - и мы будто первый раз бросаем кубик - ожидаемая дальше длина строки=S, после уже имеющегося одного символа. Также, если бы во второй раз выпала 2 или 4, то ожидаемая длина строки следующего броска данной последовательности была бы 1+1+S, т.к. два символа мы уже имеем, а следующий бросок не зависит от предыдущих - ожидаемое количество символов дальше, в течении бросков, = S, помимо уже 2 имеющихся (этот шаг уже включён в 2/6(1+S), не нужно продолжать и писать 2/6*2/6(1+1+S)) [т.к. в 2/6 заключён смысл продолжения строки после первого броска, со всеми дальнейшими бросками, - это учитывает длина строки (1+S), а именно прибавление S учитывает это. Это не обычное вычисление вероятности. Наверное именно это и наша невнимательность послужили причиной нашего непонимания]
-
-
