§4. Разорение игрока: блуждание между двумя стенками

Постановка

Два противника играют много независимых партий. Первый выигрывает партию с вероятностью $p$, второй — с вероятностью $q = 1 - p$ (ничьих нет). Проигравший платит 1. Начальный капитал первого игрока $k$, второго — $M - k$. Игра кончается, когда один из них проиграет всё.

Ход игры — это траектория случайного блуждания $S_n = Z_1 + \dots + Z_n$, поднятая на $k$ единиц вверх, где шаги $Z_i$ независимы, $\mathbf P(Z_i = 1) = p$, $\mathbf P(Z_i = -1) = q$. Величина $S_n + k$ — капитал первого игрока после $n$ партий. Суммарный капитал $M$ не меняется, так что блуждание идёт по полосе между стенками 0 и $M$. Найдём $r_k$ — вероятность разорения первого игрока.

Смысл по-пацански: это та же картинка, что у Вальда в §3. Блуждание, две границы, остановка при первом касании. Только вместо «приняли гипотезу» — «пацан ушёл домой без денег».

Игра не длится вечно

Перенесём начало координат в точку $(0, k)$ и обозначим через $\nu$ момент окончания игры. Так как $\mathbf MZ_1 = p - q$ и $\mathbf DZ_1 = 1 - (p - q)^2 < \infty$, при $p \ne 1/2$ выполнены условия теоремы 3 из §3, и $\mathbf M\nu < \infty$.

Докажем, что и при $p = 1/2$ (тогда $\mathbf MZ_1 = 0$) $\mathbf M\nu$ конечно. Возьмём чётное $M = 2m$ и $l = \min\{k, M - k\}$. С вероятностью $2^{-l} \ge 2^{-m}$ игра может закончиться за $l$ партий — достаточно $l$ выигрышей (или проигрышей) подряд. Разобьём блуждание на независимые отрезки длины $m$. На каждом из них игра кончается с вероятностью не меньше $2^{-m}$, поэтому

Вероятности $\mathbf P(\nu > i)$ убывают с ростом $i$, а при $i = jm$ мажорируются членами геометрической прогрессии со знаменателем $\gamma = 1 - 2^{-m}$. Поэтому ряд $\sum_{i=0}^\infty\mathbf P(\nu > i)$ сходится, а по формуле (3) главы 1 его сумма равна $\mathbf M\nu$. (Случай нечётного $M$ разберите самостоятельно.)

Ответ через тождество Вальда

Конечность $\mathbf M\nu$ позволяет применить тождество Вальда (теорема 5 из §3). При $p = 1/2$ возьмём $c_0 = -k$, $c_1 = M - k$, $r_k = \mathbf P(S_\nu = c_0)$:

Отсюда $-kr_k + (M - k)(1 - r_k) = 0$ и

Шансы на выигрыш прямо пропорциональны начальному капиталу. Перегнать в честной игре того, у кого денег в десять раз больше, можно лишь с вероятностью $1/11$.

Ответ через первый шаг

Тот же ответ получим другим способом — разложением по первому шагу. По формуле полной вероятности после первой партии капитал станет $k + 1$ (вероятность $p$) или $k - 1$ (вероятность $q$), и дальше всё начинается заново:

с граничными условиями $r_0 = 1$, $r_M = 0$. При $p = 1/2$ соотношение (18) переписывается как $r_{k+1} - r_k = r_k - r_{k-1}$: точки $(k, r_k)$ лежат на одной прямой $r_k = A + Bk$. Из граничных условий $A = 1$, $B = -1/M$.

Смысл по-пацански: «вероятность продуть отсюда» — среднее от «вероятностей продуть» в двух соседних клетках, куда ты попадёшь через партию. Если монетка честная, это просто середина отрезка — и вся картинка выпрямляется в линейку.

Аналогия с краевой задачей

Соотношение (18) похоже на краевую задачу для дифференциального уравнения второго порядка

При малом $h > 0$ производную $y'(x)$ приближённо заменяют конечной разностью $[y(x + h) - y(x)]/h$, а $y''(x)$ — второй симметричной разностью

При $p = 1/2$ соотношение (18) принимает вид $r_{k+1} - 2r_k + r_{k-1} = 0$ — это правая часть (20) при $x = k$, $y(x) = r_k$, $h = 1$. А общее решение уравнения $y'' = 0$ — та же прямая $y = A + Bx$.

Метод стрельбы

Чтобы найти $r_k$ при $p \ne 1/2$ (задача 6), воспользуемся идеей метода стрельбы для численного решения краевых задач. Допустим, мы умеем решать задачу Коши

например, методом Эйлера из §6 главы 2. Фиксируем $a$ и меняем $c$ — начальный наклон, «угол прицела». Пусть $g(c)$ — значение решения (21) в точке $x_1$. Тогда краевая задача (19) сводится к поиску корня $c^*$ уравнения $g(c) = b$: бросаем мяч в кольцо, смотрим, перебросили или недобросили, и подправляем силу броска — делением отрезка пополам или методом Ньютона (§5 главы 9).

Для дискретной задачи (18) аналог $y'$ — приращение $\Delta_k = r_{k+1} - r_k$. Стреляем из $r_0 = 1$ с начальным наклоном $c = \Delta_0$ и подбираем $c$ так, чтобы попасть в $r_M = 0$:

Ответ задачи 6:

Устремим $M \to \infty$ — второй игрок «бесконечно богат». Предел $r_k$ равен 1, если $p \le 1/2$, и $\lambda^k$, если $p > 1/2$. Искусный игрок может с положительной вероятностью $1 - \lambda^k$ никогда не проиграть даже бесконечно богатому противнику: при $p = 0{,}55$ и $k = 10$ это $1 - (9/11)^{10} \approx 0{,}87$. Если он не проиграл сразу из-за случайности, то дальше его шансы резко растут благодаря «сносу» траектории вверх.

Смысл по-пацански: а вот обратная сторона. В рулетке ставка на красное выигрывает с вероятностью $p = 18/37 \approx 0{,}486$ — казино почти честное. Но если прийти с 50 фишками и играть до 100, разоришься с вероятностью 0,94, а не 0,5. Маленький перекос на длинной дистанции превращается в приговор.

Сколько длится игра

Найдём среднюю длительность игры $l_k = \mathbf M\nu$, $k = 1, \dots, M - 1$. Те же рассуждения, что для (18), приводят к уравнению

с граничными условиями $l_0 = 0$, $l_M = 0$. Единица в правой части добавлена потому, что одна партия уже сыграна. Нетрудно проверить, что при $p = 1/2$ решение $l_k = k(M - k)$. При больших $M$ и $k \approx aM$ среднее время игры равных по силе противников имеет порядок $M^2$.

Это становится менее удивительным, если вспомнить центральную предельную теорему: траектория симметричного блуждания $S_n$ колеблется в среднем в пределах $\pm\sqrt n$. Чтобы уйти на расстояние $M/2$, нужно порядка $M^2/4$ шагов.

При $p \ne 1/2$ дело обстоит иначе: срабатывает снос (замечание 1 из §3), и игра идёт за время порядка $M$ (вопрос 4).

При $k = 10$, $M = 20$, $p = 1/2$ средняя длительность $l_{10} = 100$. Но медиана — около 75 партий, а примерно в каждом пятом случае игра длится больше 150 партий: хвост у закона длинный. Сдвинь $p$ до 0,45 — разорение станет почти неизбежным (0,88), а игра в среднем короче (76 партий).

Проверь себя