§5. Оптимальная остановка блуждания: брать или бросать дальше

Игра

Проведём небольшой вероятностный эксперимент. В начальный момент частица с равными вероятностями попадает в любую из $M + 1$ точек с целыми координатами $0, 1, \dots, M$ . Если частица оказалась на одном из концов, выигрыш равен 0. Иначе участник решает: остаться и взять приз, равный высоте столбика над этой точкой, или подбросить симметричную монетку и сдвинуть частицу на 1 влево (герб) или вправо (решка). После этого снова: взять приз или сделать ещё один «случайный шаг», и т. д.

Если частица попала в конец отрезка $[0, M]$ , блуждание принудительно останавливается, и выигрыш равен 0. Задача — выбрать стратегию, приносящую максимальный средний выигрыш.

Возьмём $M = 7$ и столбики высотой

точка	0	1	2	3	4	5	6	7
приз	0	2	3	4	6	4	1	0

Прежде чем читать дальше, ответь себе на вопросы 5 и 6. Стоит ли останавливаться в точке, где столбик невысок, но слева и справа есть повыше? А если частица в точке 6 — брать 1 или сделать ровно один шаг и взять то, что там будет?

Смысл по-пацански: синица в руке или журавль в небе — только журавль тут считается точно. Шагнуть — значит рискнуть, что тебя снесёт к краю с нулём. Но и сидеть на копеечном столбике, когда рядом шестёрка, тоже глупо.

Стратегия «Никогда»

Если никогда не брать приз, то по задаче о разорении игрока (§4) частица с вероятностью 1 рано или поздно попадёт на один из концов, где выигрыш нулевой. Средний выигрыш — 0.

Стратегия «Сразу»

Средний выигрыш при немедленной остановке в начальной точке:

\frac{0 + 2 + 3 + 4 + 6 + 4 + 1 + 0}{8} = \frac{20}8 = 2{,}5.

Стратегия «Все или ничего»

Блуждаем до момента попадания либо в точку 4 с максимальным выигрышем 6, либо на конец отрезка с нулём. Для подсчёта среднего воспользуемся свойством 1 условного математического ожидания (П7) — условием будет начальное положение.

Пусть частица начала в точке 5. Блуждание до попадания в 4 или в 7 — это задача о разорении игрока при $p = 1/2$ с начальным капиталом $k = 7 - 5 = 2$ при суммарном капитале $M = 7 - 4 = 3$ . Вероятность разорения $r_k = 1 - k/M = 1/3$ — это вероятность дойти до 7 и получить 0. Условный средний выигрыш $0 \cdot \tfrac13 + 6 \cdot \tfrac23 = 4$ .

Перебирая все начальные положения от 0 до 7, получаем безусловный средний выигрыш

6\cdot\Bigl(0 + \frac14 + \frac12 + \frac34 + 1 + \frac23 + \frac13 + 0\Bigr)\Big/8 = \frac{21}8 = 2{,}625.

Лучше, чем «Сразу», но ненамного.

Наилучшая стратегия

Красивую оптимальную стратегию легко объяснить на пальцах. Представим, что призовые столбики — картонные полоски, приклеенные к листу бумаги. Закрепим кнопками резинку в концевых точках отрезка $[0, M]$ , оттянем её вверх и отпустим. Столбики разделятся на два класса: те, что поддерживают резинку, и те, над которыми она прошла сверху, не касаясь. (Мы наглядно построили то, что формально называется выпуклой оболочкой графика — точнее, наименьшей вогнутой мажорантой функции призов.)

Оптимальная стратегия: останавливаться в тот момент, когда частица попадёт в точку, где столбик касается резинки.

Почему так? Если остановиться только в точках касания, то из любой точки между двумя соседними точками касания $a < i < b$ средний выигрыш — это линейная интерполяция их призов: вероятность дойти сначала до $b$ равна $(i - a)/(b - a)$ , как в задаче о разорении. То есть средний выигрыш — это высота резинки над точкой $i$ . Выше резинки подняться нельзя: вогнутую функцию, которая не ниже призов, симметричное блуждание в среднем не увеличивает. А резинка — самая низкая такая функция.

Для наших столбиков резинка касается точек 1, 4 и 5 (точка 5 лежит ровно на отрезке резинки между 4 и 7, там останавливаться всё равно, но можно). Средний выигрыш

\Bigl(0 + 2 + \Bigl[2\cdot\frac23 + 6\cdot\frac13\Bigr] + \Bigl[2\cdot\frac13 + 6\cdot\frac23\Bigr] + 6 + 4 + \Bigl[4\cdot\frac12 + 0\cdot\frac12\Bigr] + 0\Bigr)\Big/8 = \frac{22}8 = 2{,}75.

(вопрос 8). Поиграй сам — со столбиками из книги и со случайными:

Столбики — призы. Красные — точки, где стратегия Наилучшая велит остановиться. Сплошная линия — средний выигрыш из каждой точки старта при этой стратегии, пунктир — «резинка» (вогнутая мажоранта), выше которой не прыгнуть.Средний выигрыш при случайном старте: «Никогда» — 0,000; «Сразу» — 2,500; «Все или ничего» — 2,625; Наилучшая — 2,750. Среднее число шагов у выбранной: 0,625.

Смысл по-пацански: натяни резинку над всеми призами. Где она лежит на столбике — забирай и уходи. Где висит в воздухе — бросай монетку: впереди в среднем больше. Вся теория оптимальной остановки — это одна резинка.

Лагутин предлагал провести эксперимент вручную: открывать книгу «случайным образом» и брать цифру номера страницы (вторую справа — первые справа у правых страниц всегда нечётные, а третьи меняются слишком медленно). Если цифра больше 7, листать дальше, а шаг влево или вправо выбирать по тому, меньше ли цифра 5. Четыре игры по наилучшей стратегии дают в среднем $4 \cdot 2{,}75 = 11$ очков. Удастся ли тебе набрать больше 11 за 4 игры? Кнопка «Сыграть 4 раза» в виджете делает то же самое без книги.

Проверь себя

Частица в точке 6 (приз 1, соседи — точка 5 с призом 4 и точка 7 с призом 0). Что выгоднее: взять приз или сделать ровно один шаг и взять, что выпадет?