Сколько раз бросать монетку?

Разумеется, мы считаем монетку «честной», то есть имеющей равные шансы выпадения «орла» и «решки». Ответ требует понимания того, что такое среднее число бросков. Математики обычно говорят о «математическом ожидании» числа бросков. Полезно заметить, что если результатом первого броска стало выпадение решки, то весь эксперимент как бы начался заново и продлится на один ход дольше.

На первый взгляд кажется, что поскольку вероятности выпадения двух орлов (ОО) и комбинации «орел + решка» (ОР) одинаковы, то и число бросков до появления нужной комбинации будет одинаковым. Подумайте, почему это может оказаться не так. В чем разница между выпадением (невыигрышных) двух орлов во второй игре и выпадением комбинации ОР в первой?

Начнем с двух орлов. Пусть B — количество ходов, через которое в среднем наступит выигрыш. Рассмотрим также две вспомогательных величины B_Р и В_О: первая из них будет означать среднее число ходов до выигрыша, если на первом ходу выпала решка, а вторая — среднее число ходов до выигрыша, если на первом ходу выпал орел.

Заметим, что так как орел и решка на первом ходу имеют равные шансы, то В = (B_Р + В_О)/2.

Однако это не все, что можно получить «на пальцах» из условий задачи и введенных только что обозначений. Действительно, если на первом ходу выпал орел, то на втором ходу с вероятностью 1/2 игра заканчивается и имеет длину 2, а с вероятностью 1/2 выпадает решка, и игра продолжается. Длина такого продолжения (опять же, в среднем!) на 1 больше чем длина игры, начавшейся решкой, потому что тут решка выпала на втором ходу. Это означает, что В_О = (2 + (1 + B_Р))/2. Если же игра началась с решки, то она точно не закончится после второго хода, то есть после решки игру можно считать начавшейся заново и длящейся на один ход больше, чем если бы этой решки вначале не было. Иначе говоря, B_Р = 1 + В.

Мы получили три линейных уравнения, связывающих величины В, B_Р и В_О. Решив полученную систему, найдем В_О = 5, B_Р = 7, В = 6. Итак, в среднем выпадение двух орлов можно ожидать на шестом ходу.

Теперь исследуем игру, в которой выигрыш наступает после комбинации «орел + решка».

Пусть D — средняя длина игры во всех случаях, а D_О и D_Р — длины в случае первого орла и в случае первой решки соответственно. Как и в первой игре, равенство D = (D_О + D_Р)/2 следует из равенства шансов выпадения орла и решки на первом ходу.

Далее, если игра началась с орла и не закончилась на втором ходу, то это означает, что вторым ходом тоже выпал орел. То есть длина такой игры в среднем равна 1 + D_О (мы можем забыть про первого орла и считать, что игра началась со второго хода) — получаем уравнение D_О = (2 + (1 + D_О))/2, из которого сразу находим D_О = 3. Наконец, если игра началась с решки, то она фактически началась заново, то есть D_Р = 1 + D. Из уравнений D = (3 + D_Р)/2 и D_Р = 1 + D находим D = 4, D_Р = 5.

Итак, в этом случае игра в среднем закончится на четвертом ходу — на два хода быстрее.

Как бы изменились ответ и решение, если бы игра шла не до двух орлов, а до трех? Применим тот же прием для большего числа переменных.

Пусть Е_ОО, Е_ОР, Е_РО и Е_РР — средние продолжительности для игр, которые начались с выпадения «ОО», «ОР», «РО» и «РР» соответственно. Тогда средняя длина произвольной игры равна Е = (Е_ОО + Е_ОР + Е_РО + Е_РР)/4. С другой стороны, Е_ОО = (3 + (1 + Е_ОР))/2, поскольку после «ОО» игра с равной вероятностью либо заканчивается, либо продолжается выпадением решки, и тогда длится в среднем на один ход дольше, чем игра, начавшаяся с «ОР». Аналогично, Е_ОР = (1 + Е_РО + 1 + Е_РР)/2, Е_РО = (1 + Е_ОР + 1 + Е_ОО)/2 и Е_РР = (1 + Е_РО + 1 + Е_РР)/2. Эта система уравнений немного труднее предыдущих, но если не бояться трудностей, то из нее можно получить, что Е_ОО = 10, Е_ОР = 16, Е_РО = 14 и Е_РР = 16, поэтому Е = (10 + 14 + 16 + 16)/4 = 14.

Перечислим еще несколько обобщений полученных результатов.

Если считать выигрышем выпадение не обязательно трех орлов, но и трех решек подряд, то ждать придется ровно вдвое меньше — всего 7 ходов. В общем случае ждать выпадения комбинации из N одинаковых заданных результатов (то есть либо орлов, либо решек) при бросании монетки в среднем приходится 2^N + 1 − 2 хода, а если выигрышем считать появление любой из двух комбинаций, то — 2^N − 1 ход.

Если заменить монетку 6-гранной игральной костью, то ждать выпадения комбинации из N одинаковых заданных граней придется в среднем (6 + ... + 6^N) ходов, а комбинации из любых N одинаковых граней — в шесть раз меньше. Почему так? Попробуйте доказать это самостоятельно.

А теперь представьте, что вы играете против «однорукого бандита». За участие в каждой игре вы платите определенную сумму, а в случае выигрыша сразу уходите с ним. Правда ведь полезно понимать, как часто можно ждать выигрыша? И стоит ли вообще его ждать, если в среднем сумма выигрыша оказывается меньшей, чем то, что вы тратите на продолжение игры?

Если бы вместо однорукого бандита вы играли в описанную в задаче игру с бросанием монетки (до двух орлов) и за каждый бросок платили 1, а за выигрыш получали N, то при каком наименьшем N вы бы сочли игру справедливой и согласились играть? Эквивалентен ли этот вопрос тому, который был задан в задаче? Не торопитесь отвечать...

Вот еще одна ситуация с заведомо невыгодной игрой, в которой требуется аккуратный математический расчет. Пусть условия игры таковы, что ваш выигрыш в каждом раунде происходит с вероятностью, меньшей 1/2 (например, именно так обстоят дела в рулетке, где из-за наличия сектора «зеро» вероятность выигрыша при любой ставке не превышает 18/37, то есть с такой вероятностью можно удвоить ставку, а с вероятностью 19/37 — потерять ее). Если можно сыграть один раунд, то считается разумным поставить всю сумму на кон и рискнуть. А если разрешается сыграть только четное число раундов и победителем игры можно стать, только выиграв больше половины из них? Многие считают, что в этой ситуации нужно играть две игры и «уносить ноги». На самом же деле (как показывают математические расчеты) выгоднее всего сыграть достаточно большое число игр — 18 или 20. Именно при таком количестве вероятность победы в игре в целом оказывается наибольшей.

В теории вероятностей и теории игр известно много задач, при решении которых интуиция подводит даже очень искушенных в математике людей. Часто такие задачи оформляются в виде парадоксов. Например, парадокс двух братьев обычно формулируется так: каждый из братьев — Ваня и Даня — «выбрасывает» 1 или 2 пальца, потом они складывают количество пальцев, и если сумма четна, то Даня дает Ване число щелбанов, равное этой сумме, а если нечетна — то Ваня дает Дане число щелбанов, равное этой сумме.

На первый взгляд, кажется, что игра вполне честная — Ваня ставит щелбаны в двух случаях из четырех равновозможных, и при этом выдает 3 + 3 щелбана. Даня ставит брату щелбаны в двух остальных случаях, и при этом выдает 2 + 4 щелбана. Загвоздка, однако, в том, что интуиция ошибается — оптимальная стратегия для каждого из братьев отличается от стратегии «выбрасывать 1 или 2 пальца с одинаковыми вероятностями», и поэтому игра оказывается невыгодной для одного из них и выгодной для другого. Как вы думаете, для кого именно она выгодна? Проверьте свою интуицию.

Вернемся к разобранной нами задаче с выпадением орлов. Использование линейных уравнений в этой задаче избавляет от гигантских вычислительных трудностей. Ведь если бы мы просто «в лоб» постарались перечислить все (равновероятные) случаи игр, продолжавшихся не более чем N ходов, для каждой такой игры установить точную ее продолжительность (момент первого появления двух орлов подряд) и усреднить все полученные значения, то столкнулись бы с необходимостью подсчета сложных рекуррентных соотношений и вычисления «телескопических» сумм. Даже задача подсчета числа игр, в которых первое появление двух орлов происходит ровно на k-м ходу, — это не самая простая задача, а ведь для нашей задачи она являлась бы легкой разминкой перед «основным блюдом».

Если вы хотите продолжить знакомство с теорией вероятности, рекомендуем следующие книги:
1) Г. Секей, «Парадоксы в теории вероятностей и математической статистике» — книга венгерского математика Габора Секея, содержащая огромное количество неожиданных утверждений из теории вероятностей, математической статистики и теории случайных процессов.
2) Ф. Мостеллер, «Пятьдесят занимательных вероятностных задач» — подборка несложных задач для начинающих.
3) В. А. Никифоровский, «Вероятностный мир» — научно-популярная книга об истории развития теории вероятностей и ее приложений.
4) David Salsburg, The Lady Tasting Tea: How Statistics Revolutionized Science in the Twentieth Century — современная популярная книжка о математической статистике.