Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Преподаватель предоставляет всем ученикам равные шансы, каждый имеет вероятность выигрыша в 1/30. Очевидно, что вероятность выигрыша для первого ученика равна 1/30, так как он может выбрать любое из 30 чисел. Вероятность выигрыша второго ученика равна 29/30 * 1/29 = 1/30 — это вероятность того, что первый ученик ошибется (29/30), а второй — нет (1/29). Для третьего ученика эта вероятность равна 29/30 • 28/29 • 1/28 = 1/30 и так далее. С другой стороны, заметим, что вероятность выигрыша для первого ученика однозначно равняется 1/30, и если бы для каждого последующего она уменьшалась, то сумма вероятностей оказалась бы меньше 1. Это абсолютно невозможно, так как 30 учеников назовут все 30 возможных чисел и один из них обязательно угадает.

Некий игрок в рулетку всегда ставит на четное или нечетное. Если он угадывает, то выигрывает столько же, сколько поставил; если ошибается, то теряет свою ставку. Он решает каждый раз ставить 1/10 от суммы, которая есть у него на руках. Если он начнет игру со 100 евро, сделает 10 ставок подряд, выиграв 5 раз и проиграв 3 раз, сколько денег у него останется — больше, меньше или столько же, сколько было вначале? Эту задачу можно обобщить для произвольной стартовой суммы, например, m евро и ставки в 1/n от суммы, которая находится на руках у игрока перед очередной ставкой.

Может показаться, что после 5 выигрышей и 5 проигрышей у игрока будет столько же денег, что и вначале. Однако это не так, и в действительности у него останется меньше денег. Выигрыш увеличивает сумму денег на 1/10, что равносильно умножению на 1,1. Проигрыш уменьшает сумму на 1/10, что равносильно умножению на 0,9. Поэтому после 5 выигрышей и 5 проигрышей (независимо от того, в каком порядке они происходили) имеем 100 * 1,1 5• 0,9 5= 100 • 1,61051 * 0,59049 = 100 • 0,95099 ≈ 95,099 евро. Игрок потеряет около 5 евро. Подобные рассуждения можно обобщить для произвольного случая. Тот факт, что итоговая сумма всегда будет меньше начальной, объясняется тем, что (1 + 1/n)(1 - 1/n) = 1 - 1/n 2, что всегда меньше 1. При умножении начальной суммы на число, меньшее 1, мы всегда получим меньшее число.

Карикатура XVIII века на игроков в «четное — нечетное». Эта игра — предшественник современной рулетки.

Одна из элементарных задач теории вероятностей с очень удивительным результатом формулируется так. Какова вероятность того, что среди 25 человек найдутся двое, у которых день рождения приходится на один и тот же день? Учитывая, что в году 365 дней (не будем учитывать високосные), а в группе всего 25 человек, интуиция подсказывает, что итоговая вероятность будет невелика и в любом случае меньше 1/2. Однако расчеты с применением теории вероятностей показывают, что эта вероятность будет больше 1/2.

Так как в нашей группе может быть двое и более людей, дни рождения которых приходятся на один день, можно вычислить вероятность того, что все члены группы родились в разные дни. Для этого упорядочим членов группы: день рождения первого человека может приходиться на любой из 365 дней, второго — на любой из 364 оставшихся, третьего — на любой из 363 оставшихся и так далее. Следовательно, вероятность того, что все 25 человек родились в разные дни, равна

p( несовпадения дней рождений) = 365/365 • 364/365 • 363/365 • 341/365 = 365! / (340! • 365 25) = 0,4313.

Отсюда получим вероятность того, что дни рождения как минимум у двух человек совпадают: 1 - 0,4313 = 0,5687 > 1/2. В действительности эта вероятность будет превышать 1/2 уже для группы из 23 человек.

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

Преподаватель математики предложил студентам бросить монету много раз, например 150, и записать результаты, обозначив орел за 1 и решку за 0. Двое его учеников получили такие результаты:

Роман:

01011001100101011011010001110001101101010110010001

01010011100110101100101100101100100101110110011011

01010010110010101100010011010110011101110101100011.

Борис:

10011101111010011100100111001000111011111101010101

11100001010001010010000010001100010100000000011001

00001001111100001101010010010011111101001100011010.

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

Равномерное распределение нулей и единиц в результатах Романа заставило преподавателя подозревать, что сжульничал именно он. Так, если сравнить распределение нулей и единиц в результатах Романа и Бориса, то мы увидим, что результаты похожи и «правдоподобны» (78 против 72 у первого из учеников, 70 против 80 у второго). Однако в результатах Бориса присутствуют последовательности из четырех, пяти и даже девяти одинаковых чисел подряд, а в результатах Романа последовательности из единиц или нулей очень коротки (максимум три единицы или нуля подряд). Именно это и наводит на подозрения.

Проанализируем этот факт с точки зрения условной вероятности. Учитывая, что каждый бросок монеты никак не зависит от предыдущих, после каждого результата единицы и нули должны появляться примерно с одинаковой частотой. Видим, что в результатах Романа после одной единицы снова единица встречается 47 раз, ноль — 30 раз. После двух единиц подряд единица встречается всего 5 раз, в то время как ноль — 18. После каждой из 5 последовательностей из трех единиц всегда находится ноль. Подобную картину мы наблюдаем только в результатах Романа. В результатах Бориса все иначе: например, после двух единиц подряд снова единица встречается 18 раз, ноль — 14 раз; после трех единиц подряд 9 раз встречается единица и 9 раз — ноль. Следовательно, представление Романа о том, что в распределении нулей и единиц не должно быть «длинных» участков, состоящих только из нулей или только из единиц, и позволило преподавателю определить жульничество.

В следующей задаче обсуждение того, как информация о предыдущих событиях влияет (или не влияет) на вероятность последующих, еще интереснее. Игра, о которой мы сейчас расскажем, является адаптацией классической дилеммы заключенного и показывает, насколько сложно рассчитать, как именно определенная информация влияет на вероятность.