Условие
Изначально на кону 0 рублей. Раз за разом подбрасывается правильная монетка. Если выпадает орёл, казино добавляет на кон 100 рублей. Если выпадает решка, казино забирает все деньги с кона, а вы получаете красную карточку. Игра заканчивается, когда вы получаете третью красную карточку (тогда вы не получаете ничего), либо в любой момент раньше по вашему выбору — тогда вы забираете сумму на кону. Вы максимизируете средний выигрыш.
а) Как выглядит оптимальная стратегия, если только что получена вторая красная карточка? Чему равен средний выигрыш?
б) Как выглядит оптимальная стратегия, если только что получена первая красная карточка?
в) Как выглядит оптимальная стратегия в исходной игре? Чему равен средний выигрыш?
Решение источника
Источник приводит только ответ в виде двух стратегий:
- стратегия 1: говорить «стоп», когда на кону 200 рублей, при любом числе красных карточек;
- стратегия 2: при нуле или одной красной карточке останавливаться на 200 рублях, а при двух карточках — на 100 рублях.
Средние выигрыши в источнике не вычислены.
Редакционное объяснение
Решаем с конца. Обозначим через Vc(x) максимальный средний выигрыш, если у игрока c красных карточек, а на кону x рублей. Продолжая игру, мы с вероятностью 1/2 переходим в состояние (c, x + 100), а с вероятностью 1/2 — в (c + 1, 0), причём при c = 2 это конец игры с нулём.
Две карточки. При x = 0 останавливаться бессмысленно. При x = 100 остановка даёт 100, а продолжение — 1/2 · V2(200) + 1/2 · 0 = 100: игрок безразличен. При x = 200 продолжение даёт не больше 1/2 · 300 = 150 < 200, поэтому надо остановиться. Значит, после второй карточки достаточно одного броска: при орле забрать 100 рублей (или рискнуть ещё раз — в среднем то же самое), при решке игра и так закончена. Ответ а): V2(0) = 1/2 · 100 = 50 рублей.
Одна карточка. Теперь при решке мы не теряем всё, а переходим в состояние стоимостью 50. При x = 200 продолжение даёт 1/2 · 300 + 1/2 · 50 = 175 < 200 — стоп. При x = 100 продолжение даёт 1/2 · 200 + 1/2 · 50 = 125 > 100 — играем дальше. Ответ б): останавливаться на 200 рублях; V1(100) = 125, V1(0) = 1/2 · 125 + 1/2 · 50 = 87,5.
Начало игры. При x = 200 продолжение даёт 1/2 · 300 + 1/2 · 87,5 = 193,75 < 200 — стоп. При x = 100 продолжение даёт 1/2 · 200 + 1/2 · 87,5 = 143,75 > 100 — играем. Ответ в): останавливаться на 200 рублях, средний выигрыш V0(0) = 1/2 · 143,75 + 1/2 · 87,5 = 115,625 = 925/8 рубля.
Удобное правило «на шаг вперёд»: останавливаться выгодно, когда x ≥ 100 + W, где W — ценность состояния после следующей решки. При двух карточках W = 0 и порог 100; при одной W = 50 и порог 150, то есть фактически 200; в начале W = 87,5 и порог 187,5, снова 200.
Обе стратегии источника оптимальны именно из-за безразличия в состоянии «две карточки, 100 рублей». Они дают одно и то же среднее 925/8, но разные распределения выигрыша: при стратегии 2 выигрыш 0, 100 и 200 рублей с вероятностями 9/32, 9/32 и 7/16, а при стратегии 1 — 0 и 200 рублей с вероятностями 27/64 и 37/64. Моделирование 400 000 партий дало средние 115,5 и 115,5 рубля.
Типичная ошибка — сравнивать продолжение только с суммой на кону и забывать, что после решки у игрока остаются «жизни», которые сами чего-то стоят. Именно поэтому порог при одной карточке выше, чем при двух.
Что не следует из ответа
Оптимальность здесь понимается как максимум среднего выигрыша. Игрок, который не любит риск, может предпочесть стратегию 2: при том же среднем она реже оставляет его ни с чем (9/32 против 27/64).
Средний выигрыш 115,6 рубля не означает, что в отдельной партии можно рассчитывать на такую сумму: выигрыш принимает только значения 0, 100 и 200 рублей.
Борис Демешев и участники · probability_pro, задача «Красные карточки» · Исходное задание и решение · CC BY 4.0. Адаптация: условие сокращено, стратегии из ответа источника сохранены; расчёт ценностей состояний, средний выигрыш, распределение выигрыша и симуляция добавлены редакцией.