Задача о разорении игрока

Задача о разорении игрока — задача из области теории вероятностей.

Траектории справедливой игры длиною 1000 шагов; коридор блуждания частицы обозначен горизонтальными линиями

Формулировка

За столом сидят два игрока. У первого в распоряжении находится $-A(A<0,-A>0)$ рублей, у второго в распоряжении находится $B(B>0)$ рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за $n$ шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.

Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор $[A;B]$. Рассматривается вероятность того, что частица выйдет из коридора за $n$ шагов (проскочит через верхнюю или нижнюю стенку).

Схема Бернулли

Рассмотрим схему Бернулли с $n$ испытаниями.

Пусть $(\mathrm{\Omega },𝒜,\mathbb{P})$ — вероятностное пространство, где

• $\mathrm{\Omega }=\{\omega :\omega =(x_1;\dots ;x_n),x_i=\pm 1\}$ – элементарные исходы,
• $𝒜=\{A_i\subseteq \mathrm{\Omega }\}$ — алгебра подмножеств вероятностного пространства,
• $\mathbb{P}(\{\omega \})=p^{\nu (\omega )}\cdot q^{n-\nu (\omega )}$, где $\nu (\omega )$ — количество выпавших в данной последовательность единиц.

В выражении выше число выпавших единиц можно найти так: $\nu (\omega )=\frac{\sum _{i=1}^n{x}_i+n}{2}$.

Введём последовательность бернуллиевских случайных величин:

$i=\overline{1;n},{\xi }_i(\omega ):\mathbb{P}(\{{\xi }_i=1\})=p,\mathbb{P}(\{{\xi }_i=-1\})=q,p+q=1.$

Подзадача о нормированности вероятности

Доказать, что $\sum _{\omega \in \mathrm{\Omega }}\mathbb{P}(\{\omega \})=1.$

Решение

$\sum _{\omega \in \mathrm{\Omega }}\mathbb{P}(\{\omega \})=\sum _{\omega \in \mathrm{\Omega }}{p}^{\frac{\sum _{i=1}^n{x}_i+n}{2}}\cdot q^{n-\frac{\sum _{i=1}^n{x}_i+n}{2}}=\sum _{k=0}^n\sum _{\omega \in A_k}{p}^{\frac{\sum _{i=1}^n(x_i+1)}{2}}\cdot q^{\frac{\sum _{i=1}^n(1-x_i)}{2}}=\sum _{k=0}^n{C}_n^k{p}^k{q}^{n-k}.$ Это справедливо в силу того, что $\frac{x_i+1}{2}\in \{0;1\}.$

$\sum _{k=0}^n{C}_n^k{p}^k{q}^{n-k}=(p+q{)}^n=1$, поскольку по условию $p+q=1$. $◼$

Подзадача о независимости случайных величин ξ_i

Доказать, что ${\xi }_1$ и ${\xi }_2$ независимы.

Решение

Независимость случайных величин означает, что

$\mathbb{P}(\{{\xi }_1=1\}\cap \{{\xi }_2=1\})=\mathbb{P}(\{{\xi }_1=1\})\mathbb{P}(\{{\xi }_2=1\}),$

покажем это:

$\mathbb{P}(\{{\xi }_1=1\}\cap \{{\xi }_2=1\})=\mathbb{P}(\{\omega :\omega =(x_1;\dots ;x_n),x_1=1,x_2=1\})=$

$=\sum _{\begin{array}{c}{x}_3=\pm 1\\ \dots \\ x_n=\pm 1\end{array}}{p}^{\frac{2+\sum _{i=3}^n{x}_i+n}{2}}\cdot q^{n-\frac{2+\sum _{i=3}^n{x}_i+n}{2}}=p^2\sum _{\begin{array}{c}{x}_3=\pm 1\\ \dots \\ x_n=\pm 1\end{array}}{p}^{\frac{\sum _{i=3}^n{x}_i+(n-2)}{2}}\cdot q^{(n-2)-\frac{\sum _{i=3}^n{x}_i+(n-2)}{2}}=p^2\cdot 1.$ $◼$

Случайное блуждание

Для схемы Бернулли договоримся о следующем смысле случайной величины ξ: ${\xi }_i=+1$ означает, что второй игрок платит первому, а ${\xi }_i=-1$ – первый игрок второму.

Введём новое обозначение:

$S_0=0$, $S_k={\xi }_1+\dots +{\xi }_k,1⩽k⩽n$.

Число $n$ равно длительности игры, а последовательность $(S_k{)}_{k⩽n}$ можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля, при этом очевидно равенство $S_{k+1}=S_k+{\xi }_{k+1}$, а само $S_k$ означает выигрыш первого игрока у второго (который может быть отрицательным).

Пусть $A$, $B$ — два целых числа, $A⩽0$, $B⩾0$. Требуется найти, с какой вероятностью за $n$ шагов будет осуществлён выход частицы из коридора, ограниченного $A$ и $B$.

Далее, пусть $x$ — целое число, $x\in \mathbb{Z}\cap [A;B]$. Пусть также для $0⩽k⩽n$ верно, что $S_k^x=x+S_k$ (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть ${\tau }_k^x=\min \{l:0⩽l⩽k,S_l^x=\{A\mathrm{o}\mathrm{r}B\}\}$. Условимся считать, что ${\tau }_k^x=k$, если $A<S_l^x<B\mathrm{\forall }l:0⩽l⩽k$. Если частица так и не пересекла границы, то $x_k$ не определён.

Для каждого $0⩽k⩽n$ и $x\in [A;B]\cap \mathbb{Z}$ момент ${\tau }_k^x$ называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий $\mathrm{\Omega }$. $\mathrm{\forall }l<k\{\omega :{\tau }_k^x=l\}$ — это событие, состоящее в том, что случайное блуждание $\{S_i^x:0⩽i⩽k\}$, начинающееся в точке $x$, выйдет из интервала $[A;B]$ в момент $l$. Введём новые обозначения: ${𝒜}_k^x=\coprod _{0⩽l⩽k}\{\omega :{\tau }_k^x=l,S_l^x=A\}$, ${ℬ}_k^x=\coprod _{0⩽l⩽k}\{\omega :{\tau }_k^x=l,S_l^x=B\}$ для $0⩽k⩽n$. Пусть ${\alpha }_k(x)=\mathbb{P}({𝒜}_k^x)$, ${\beta }_k(x)=\mathbb{P}({ℬ}_k^x)$ — вероятности выхода частицы за время $[0;k]$ из интервала $[A;B]$ соответственно в точках $A$ и $B$.

Пусть $A<x<B$; очевидно, что ${\alpha }_0(x)={\beta }_0(x)=0$ (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь $0⩽k⩽n$. Тогда по формуле полной вероятности ${\beta }_k(x)=\mathbb{P}({ℬ}_k^x)=\mathbb{P}({ℬ}_k^x\mid S_1^x=x+1)\cdot \mathbb{P}(\{{\xi }_1=1\})+\mathbb{P}({ℬ}_k^x\mid S_1^x=x-1)\cdot \mathbb{P}(\{{\xi }_1=-1\}).$

Подзадача о рекуррентности

Доказать, что

(1) $\mathbb{P}({ℬ}_k^x\mid S_1^x=x+1)=\mathbb{P}({ℬ}_{k-1}^{x+1})$,

(2) $\mathbb{P}({ℬ}_k^x\mid S_1^x=x-1)=\mathbb{P}({ℬ}_{k-1}^{x-1})$.

Доказательство.

(1) Докажем, что $\mathbb{P}({ℬ}_k^x\mid S_1^x=x+1)=\mathbb{P}({ℬ}_{k-1}^{x+1})$.

${ℬ}_k^x=\{\omega :(x;x+{\xi }_1;\dots ;x+{\xi }_1+\dots +{\xi }_k)\in B_k^x\}$, где $B_k^x$ — множество траекторий вида $(x;x+x_1;\dots ;x+x_1+\dots +x_k),x_i=\pm 1$, которые за время $[0;k]$ впервые выходят из интервала $(A;B)$ в точке $B$ (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество $ℬ$. Представим множество $B_k^x$ как $B_k^{x;x+1}\bigsqcup B_k^{x;x-1}$. Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, $x_1=\pm 1$. $B_k^{x;x+1}$ — те траектории из $B_k^x$, для которых $x_1=1$. $B_k^{x;x-1}$ — те траектории из $B_k^x$, для которых $x_1=-1$. Заметим, что каждая траектория $(x;x+1;x+1+x_2;\dots ;x+1+x_2+\dots +x_k)$ из $B_k^{x;x+1}$ находится в однозначном соответствии с траекторией $(x+1;x+1+x_2;\dots ;x+1+x_2+\dots +x_k)$ из $B_{k-1}^{x+1}$. Взаимно-однозначное соответствие доказывается от противного. Предположим, что $x_1=-1$ (неоднозначное соответствие); тогда данная траектория $(x;x-1;x-1+x_2;\dots ;x-1+x_2+\dots +x_k)$ не сможет вывести частицу из коридора за $k$ шагов (а только лишь за $k+2$ из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: $S_{k+1}=S_k+{\xi }_{k+1}$. Из этого следует, что $\mathbb{P}\left(\right\{(x+1;x+1+x_2;\dots ;x+1+x_2+\dots +x_k)\in B_{k-1}^{x+1}\left\}\right)=\mathbb{P}\left(\right\{(x+1;x+1+x_1;\dots ;x+1+x_1+\dots +x_{k-1})\in B_{k-1}^{x+1}\left\}\right)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\mathbb{P}({ℬ}_{k-1}^{x+1})$ (так как ${\xi }_i$ суть независимые одинаково распределённые случайные величины).

Существует и другой способ доказательства:

$\mathbb{P}({ℬ}_k^x\mid S_1^x=x+1)=\mathbb{P}({ℬ}_k^x\mid {\xi }_1=1)=\mathbb{P}((x;x+{\xi }_1;\dots ;x+{\xi }_1+\dots +{\xi }_k)\in B_k^x\mid {\xi }_1=1)=$

$=\frac{\mathbb{P}((x;x+{\xi }_1;\dots ;x+{\xi }_1+\dots +{\xi }_k)\in B_k^x\cap {\xi }_1=1)}{\mathbb{P}(\{{\xi }_1=1\})}=\frac{\mathbb{P}((x;x+1;\dots ;x+1+\dots +{\xi }_k)\in B_k^x\cap {\xi }_1=1)}{\mathbb{P}(\{{\xi }_1=1\})}=$

$=\mathbb{P}(\{(x;x+1;x+1+{\xi }_2;\dots ;x+1+{\xi }_2+\dots +{\xi }_k)\in B_k^x\})=\mathbb{P}(\{(x;x+1;x+1+{\xi }_1;\dots ;x+1+{\xi }_1+\dots +{\xi }_{k-1})\in B_k^x\})=$

$=\mathbb{P}(\{(x;x+1;x+1+{\xi }_1;\dots ;x+1+{\xi }_1+\dots +{\xi }_{k-1})\in B_{k-1}^{x+1}\})=\mathbb{P}({ℬ}_{k-1}^{x+1})={\beta }_{k-1}(x+1)$.

Это справедливо потому, что вероятности независимы (это было доказано ранее).

(2) Аналогично докажем, что $\mathbb{P}({ℬ}_k^x\mid S_1^x=x-1)=\mathbb{P}({ℬ}_{k-1}^{x+1})$.

Каждая траектория $(x;x-1;x-1+x_2;\dots ;x-1+x_2+\dots +x_k)$ из $B_k^{x;x+1}$ находится в однозначном соответствии с траекторией $(x-1;x-1+x_2;\dots ;x-1+x_2+\dots +x_k)$ из $B_{k-1}^{x-1}$. Отсюда $\mathbb{P}\left(\right\{(x-1;x-1+x_2;\dots ;x-1+x_2+\dots +x_k)\in B_{k-1}^{x-1}\left\}\right)=\mathbb{P}\left(\right\{(x-1;x-1+x_1;\dots ;x-1+x_1+\dots +x_{k-1})\in B_{k-1}^{x-1}\left\}\right)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\mathbb{P}({ℬ}_{k-1}^{x-1}).$ $◼$

Вывод рекуррентного соотношения

Из уравнения для ${\beta }_k(x)$ следует, что для $x\in (A;B)$ и $k⩽n$ верно:

$\mathbb{P}({ℬ}_k^x)=\mathbb{P}({ℬ}_k^x\mid S_1^x=x+1)\cdot p+\mathbb{P}({ℬ}_k^x\mid S_1^x=x-1)\cdot q=\mathbb{P}({ℬ}_{k-1}^{x+1})\cdot p+\mathbb{P}({ℬ}_{k-1}^{x-1})\cdot q=p{\beta }_{k-1}(x+1)+q{\beta }_{k-1}(x-1).$

${\beta }_l(B)=1$, ${\beta }_l(A)=0$ для $l\in [0;n]$.

Формула полной вероятности также даёт нам следующий результат: ${\alpha }_k(x)=p{\alpha }_{k-1}(x+1)+q{\alpha }_{k-1}(x-1)$.

Также отметим, что ${ℬ}_{k-1}\subset {ℬ}_k$, и поэтому ${\beta }_{k-1}(x)⩽{\beta }_k(x)⩽1$ для $k⩽n$. Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг ($x_{j-1}=\pm 1$), на котором частица может прийти в точку $(j;S_j^x)$ как из $(j-1;S_j^x-1)$ (для ${\xi }_j=1$), так и из $(j-1;S_j^x+1)$ ($j⩽k$).

Нахождение вероятностей

При достаточно больших $n$ вероятность ${\beta }_n(x)$ близка к $\beta (x)$ — решению уравнения $\beta (x)=p\beta (x+1)+q\beta (x-1)$ при тех условиях, что $\beta (B)=1$ (выход произошёл сразу же из точки $B$ — конец игры, выиграл первый игрок), $\beta (A)=0$ (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке $A$). Эти условия следуют из того, что $\lim {\mathrm{\backslash limits}}_{l\to \mathrm{\infty }}{\beta }_l(B)=\beta (B)$. Это также будет доказано в этом разделе.

Сначала получим решение уравнения $\beta (x)=p\beta (x+1)+q\beta (x-1)$. Пусть игра несправедливая ($p\ne q$). В таком случае найдём корни уравнения, то есть $\beta (x)$. Одно частное решение видно сразу: $\beta (x)=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}=a$. Другое решение найдём, воспользовавшись тем, что $\beta (x)$ — функция. Целесообразно употребить выражение с отношением $\frac{q}{p}$, учитывая, что $p+q=1$: ${\left(\frac{q}{p}\right)}^x=\frac{q^x(p+q)}{p^x}=\frac{q^x}{p^{x-1}}+\frac{q^{x+1}}{p^x}=p\frac{q^{x+1}}{p^{x+1}}+q\frac{q^{x-1}}{p^{x-1}}=p{\left(\frac{q}{p}\right)}^{x+1}+q{\left(\frac{q}{p}\right)}^{x-1}$. Отсюда правомерно предположить, что $\beta (x)=b\cdot {\left(\frac{q}{p}\right)}^x$. Добавление константы ничего не изменит благодаря тому, что $p+q=1$.

Теперь рассмотрим общее решение: $\beta (x)=a+b{\left(\frac{q}{p}\right)}^x$. Воспользуемся теми условиями, что $\beta (A)=a+b{\left(\frac{q}{p}\right)}^A=0$ и $\beta (B)=a+b{\left(\frac{q}{p}\right)}^B=1$, и получим, что $\beta (x)=\frac{\beta (x)-0}{1-0}=\frac{\beta (x)-\beta (A)}{\beta (B)-\beta (A)}=\frac{a+b{\left(\frac{q}{p}\right)}^x-(a+b{\left(\frac{q}{p}\right)}^A)}{a+b{\left(\frac{q}{p}\right)}^B-(a+b{\left(\frac{q}{p}\right)}^A)}=\frac{{\left(\frac{q}{p}\right)}^x-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}.$

Подзадача о единственности решения

Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи $\beta (x)=p\beta (x+1)+q\beta (x-1)$ с граничными условиями может быть представлено в виде $\frac{{\left(\frac{q}{p}\right)}^x-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}$.

Решение

Рассмотрим некоторое решение $\check{\beta }(x)$ при условиях $\check{\beta }(A)=0$, $\check{\beta }(B)=1$. Тогда всегда можно подобрать такие константы $\check{a}$ и $\check{b}$, что $\check{a}+\check{b}{\left(\frac{q}{p}\right)}^A=\check{\beta }(A)$, $\check{a}+\check{b}{\left(\frac{q}{p}\right)}^{A+1}=\check{\beta }(A+1)$. Тогда из уравнения поставленной задачи следует, что $\check{\beta }(A+2)=\check{a}+\check{b}{\left(\frac{q}{p}\right)}^{A+2}$. Тогда в общем случае $\check{\beta }(x)=\check{a}+\check{b}{\left(\frac{q}{p}\right)}^x$. Следовательно, решение $\frac{{\left(\frac{q}{p}\right)}^x-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}$ является единственным. Точно такой же ход рассуждений может быть применён и к $\alpha (x)$. $◼$

Предельная сходимость

Рассмотрим вопрос о быстроте предельной сходимости ${\alpha }_n(x)$ и ${\beta }_n(x)$ к $\alpha (x)$ и $\beta (x)$. Пусть блуждание начинается из начала координат ($x=0$). Для простоты обозначим ${\alpha }_n(0)={\alpha }_n$, ${\beta }_n(0)={\beta }_n$, ${\gamma }_n=1-{\alpha }_n-{\beta }_n$. Иными словами, ${\gamma }_n$ — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: ${\gamma }_n=\mathbb{P}\{\omega :A<S_k<B;0⩽k⩽n\}$. $\omega$ представляет собой событие $\bigcap _{0⩽k⩽n}\{A<S_k<B\}$. Рассмотрим число $n=rm$, где $r,m\in \mathbb{Z}$, и цепочку случайных величин ${\zeta }_n:{\zeta }_1=\sum _{i=1}^m{\xi }_i,{\zeta }_2=\sum _{i=m+1}^{2m}{\xi }_i,\dots ,{\zeta }_r=\sum _{i=m(r-1)}^{rm}{\xi }_i$. Если обозначить совокупное богатство за $C=|A|+B$, то тогда $\{A<S_k<B;1⩽k⩽rm\}\subseteq \{|{\zeta }_1|<C;\dots ;|{\zeta }_r|<C\}$. Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма $m$ штук $x_i$ меньше, чем совокупный запас.

Подзадача о независимости случайных величин ζ_i

Докажем, что ${\zeta }_j$ независимы и одинаково распределённые. Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение.

Решение

Докажем, что $\mathbb{P}(\{{\zeta }_1=m\}\cap \{{\zeta }_2=m\})=\mathbb{P}(\{{\zeta }_1=m\})\cdot \mathbb{P}(\{{\zeta }_2=m\}).$

$\mathbb{P}(\{{\zeta }_1=m\}\cap \{{\zeta }_2=m\})=\mathbb{P}(\{\sum _{i=1}^m{\xi }_i=m\}\cap \{\sum _{i=m+1}^{2m}{\xi }_i=m\})=$

$=\mathbb{P}(\{{\xi }_{1;\dots ;m}=1\}\cap \{{\xi }_{m+1;\dots ;2m}=1\})={\mathbb{P}}^{2m}(\{{\xi }_i=1\})=\mathbb{P}(\{{\zeta }_1=m\})\cdot \mathbb{P}(\{{\zeta }_2=m\})$. $◼$

Вернёмся к рассмотрению сходимости.

Из только что доказанного следует что ${\gamma }_n⩽\mathbb{P}\left(\right\{|{\zeta }_1|;\dots ;|{\zeta }_r|<C\left\}\right)=\prod _{i=1}^r\mathbb{P}\left(\right\{|{\zeta }_i|<C\left\}\right)=\left(\mathbb{P}\right(\{|{\zeta }_1|<C\}){)}^r$.

Рассмотрим дисперсию: $\mathrm{V}\mathrm{a}\mathrm{r}({\zeta }_1)=m(1-(p-q{)}^2)$ (что вполне правомерно, так как $1-(p-q{)}^2=1-((p+q{)}^2-4pq)$, а $\xi$ — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших $m$ и $0<p<1$ верно: $\mathbb{P}\left(\right\{|{\zeta }_1|<C\left\}\right)⩽{\epsilon }_1$, где ${\epsilon }_1<1$, так как если $\mathbb{P}\left(\right\{|{\zeta }_1|⩽C\left\}\right)=1$, то $\mathrm{V}\mathrm{a}\mathrm{r}({\zeta }_1)⩽C^2$. Если $p=0$ или $p=1$, то для довольно больших $m$ верно, что $\mathbb{P}\left(\right\{|{\zeta }_1|<C\left\}\right)=0$, поэтому неравенство $\mathbb{P}\left(\right\{|{\zeta }_1|<C\left\}\right)⩽{\epsilon }_1$ верно $\mathrm{\forall }p\in [0;1]$. Из вышесказанного следует, что ${\gamma }_n⩽{\epsilon }^n$, где $\epsilon ={\epsilon }_1^{\frac{1}{m}}<1$. Так как $\alpha +\beta =1$, то $(\alpha -{\alpha }_n)-(\beta -{\beta }_n)={\gamma }_n$; так как $\alpha ⩾{\alpha }_n$ и $\beta ⩾{\beta }_n$, то $0⩽\alpha -{\alpha }_n⩽{\gamma }_n⩽{\epsilon }^n$; $0⩽\beta -{\beta }_n⩽{\gamma }_n⩽{\epsilon }^n$ при $\epsilon <1$. Аналогичные оценки справедливы и для разностей $\alpha (x)-{\alpha }_n(x)$ и $\beta (x)-{\beta }_n(x)$, так как можно свести эти разности к разностям $\alpha -{\alpha }_n$ и $\beta -{\beta }_n$ при $A_1=A-x$, $B_1=B-x$.

Вернёмся к рассмотрению $\alpha (x)$. По аналогии с решением $\frac{{\left(\frac{q}{p}\right)}^x-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}$ уравнения $\beta (x)=p\beta (x+1)+q\beta (x-1)$, можно сказать, что у уравнения $\alpha (x)=p\alpha (x+1)+q\alpha (x-1)$ при граничных условиях $\alpha (A)=1$, $\alpha (B)=0$ существует единственное решение $\alpha (x)=\frac{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^x}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A},A⩽x⩽B.$

Нетрудно заметить, что $\alpha (x)+\beta (x)=\frac{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^x}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}+\frac{{\left(\frac{q}{p}\right)}^x-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}=\frac{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}=1$ при любых $p\in [0;1]$. Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: $\beta (x)=\frac{x-A}{B-A}$, $\alpha (x)=\frac{B-x}{B-A}$.

Ответ о вероятности разорения

Величины $\alpha (x)$ и $\beta (x)$ можно назвать вероятностями разорения первого и второго игрока при начальных капиталах $x-A$ и $B-x$ при стремлении количества ходов к бесконечности и характеризации случайной величина ${\xi }_i=+1$ как выигрыша первого игрока, а ${\xi }_i=-1$ — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.

Если $A=0$, то интуитивный смысл функции $\beta (x)$ — это вероятность того, что частица, вышедшая из положения $x$, достигнет верхней стенки ($B$) ранее, чем нуля. Из формул $\beta (x)$ видно, что

$\beta (x)=\{\begin{array}{cc}\frac{x}{B},& p=q=0,5,\\ \frac{{\left(\frac{q}{p}\right)}^x-1}{{\left(\frac{q}{p}\right)}^B-1},& p\ne q\end{array}$.

Парадокс увеличения ставки при неблагоприятной игре

Что необходимо сделать первому игроку, если игра неблагоприятна для него?

Его вероятность проигрыша задана формулой $\lim {\mathrm{\backslash limits}}_{k\to \mathrm{\infty }}{\alpha }_k=\alpha =\frac{{\left(\frac{q}{p}\right)}^B-1}{{\left(\frac{q}{p}\right)}^B-{\left(\frac{q}{p}\right)}^A}$.

Теперь пусть первый игрок с капиталом $(-A)$ примет решение удвоить ставку и играть на два рубля, то есть $\mathbb{P}(\{{\xi }_i=2\})=p$, $\mathbb{P}(\{{\xi }_i=-2\})=q$. Тогда обозначим предельную вероятность разорения первого игрока так: ${\alpha }_2=\frac{{\left(\frac{q}{p}\right)}^{0,5B}-1}{{\left(\frac{q}{p}\right)}^{0,5B}-{\left(\frac{q}{p}\right)}^{0,5A}}$.

Поэтому $\alpha =\frac{{\left(\frac{q}{p}\right)}^{0,5B\cdot 2}-1^2}{{\left(\frac{q}{p}\right)}^{0,5B\cdot 2}-{\left(\frac{q}{p}\right)}^{0,5A\cdot 2}}=\frac{({\left(\frac{q}{p}\right)}^{0,5B}-1)\cdot ({\left(\frac{q}{p}\right)}^{0,5B}+1)}{({\left(\frac{q}{p}\right)}^{0,5B}-{\left(\frac{q}{p}\right)}^{0,5A})\cdot ({\left(\frac{q}{p}\right)}^{0,5B}+{\left(\frac{q}{p}\right)}^{0,5A})}={\alpha }_2\cdot \frac{({\left(\frac{q}{p}\right)}^{0,5B}+1)}{({\left(\frac{q}{p}\right)}^{0,5B}+{\left(\frac{q}{p}\right)}^{0,5A})}>{\alpha }_2$, так как ${\alpha }_2$ умножается на дробь, которая больше единицы при $q>p$.

Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше $0,5$, то ему выгодно увеличить ставку в $r>1$ раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке $B$. Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке $B$.

Длительность случайного блуждания

Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: $𝔼({\tau }_k^x)=m_k(x)$ для $k⩽n$. Выведем рекуррентное соотношение для математического ожидания продолжительности игры:

$m_k(x)=𝔼({\tau }_k^x)=\sum _{1⩽l⩽k}l\mathbb{P}(\{{\tau }_k^x=l\})=\sum _{1⩽l⩽k}l\left(p\mathbb{P}\right(\{{\tau }_k^x=l\}|\{{\xi }_1=1\})+q\mathbb{P}(\{{\tau }_k^x=l\}|\{{\xi }_1=-1\}\left)\right)=$

$=\sum _{1⩽l⩽k}l\left(p\mathbb{P}\right(\{{\tau }_{k-1}^{x+1}=l-1\})+q\mathbb{P}\{{\tau }_{k-1}^{x-1}=l-1\}))=\sum _{0⩽l⩽k-1}(l+1)(p\mathbb{P}(\{{\tau }_{k-1}^{x+1}=l\})+q\mathbb{P}(\{{\tau }_{k-1}^{x-1}=l\}))=$

$=p{m}_{k-1}(x+1)+q{m}_{k-1}(x-1)+\sum _{0⩽l⩽k-1}\left(p\mathbb{P}\right(\{{\tau }_{k-1}^{x+1}=l\})+q\mathbb{P}(\{{\tau }_{k-1}^{x-1}=l\}\left)\right)=p{m}_{k-1}(x+1)+q{m}_{k-1}(x-1)+1.$

Для $x\in (A;B)$ и $k\in [0;n]$ мы получили рекуррентное соотношение для функции $m_k(x)$: $m_k(x)=p{m}_{k-1}(x+1)+q{m}_{k-1}(x-1)+1$ при $m_0(x)=0$.

Введём граничные условия: если игра начинается в точке $A$ или $B$, то тогда она тут же и завершится — её длительность будет равна 0: $m_k(A)=m_k(B)=0$.

Из рекуррентного соотношения и граничных условий можно один за другим вычислить $m_i(x)$. Так как $m_{k+1}(x)⩾m_k(x)$, то существует предел $m(x)=\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}{m}_n(x)$, который удовлетворяет соотношению $m_k(x)=p{m}_{k-1}(x+1)+q{m}_{k-1}(x-1)+1$: $m(x)=1+pm(x+1)+qm(x-1)$ при выполнении $m(A)=m(B)=0$. Данные переходы аналогичны тем, что мы рассмотрели при переходе к $n\to \mathrm{\infty }$ в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть $m(x)<\mathrm{\infty }$, $x\in (A;B)$.

Решим данное уравнение. В уравнении вероятности проигрыша ($p\ne q$) уже были получены частные решения $a$ и $b{\left(\frac{q}{p}\right)}^x$. Здесь же появляется ещё один претендент на роль частного решения: $\frac{x}{q-p}=\frac{q-p+(p+q)x+p-q}{q-p}=\frac{q-p}{q-p}+\frac{p(x+1)}{q-p}+\frac{q(x-1)}{q-p}=1+p\frac{x+1}{q-p}+q\frac{x-1}{q-p}$, поэтому $m(x)=\frac{x}{q-p}+a+b{\left(\frac{q}{p}\right)}^x$. С учётом граничного условия $m(A)=m(B)=0$ находим при помощи ранее полученных соотношений $m(x)$: $m(x)=\frac{1}{p-q}(B\beta (x)+A\alpha (x)-x)$. В случае идеальной монетки получаем следующее выражение: $m(x)=a+bx-x^2$. Применение граничного условия даёт: $m(x)=(B-x)(x-A)$. Из этого следует, что в случае равных стартовых капиталов $m(0)=B^2$. Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.

При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: $m(x)<\mathrm{\infty }$. Теперь будет предложено доказательство этого факта.

Задача о конечности ожидаемого числа ходов

Доказать, что $m(x)<\mathrm{\infty }\mathrm{\forall }A,B$.

Решение

Достаточно доказать это для случая $x=0$ (так как ранее было уже продемонстрировано, что случаи $x\ne 0$ могут быть сведены к $x=0$ вариацией $A$ и $B$) и $p=q$, а затем рассмотреть случай $p\ne q$.

Итак, рассмотрим последовательность $S_{0;1;\dots ;n}$ и введём случайную величину $S_{{\tau }_n}=S_{{\tau }_n}(\omega )$, где ${\tau }_n={\tau }_n^0$ — момент остановки.

Пусть $S_{{\tau }_n}(\omega )=\sum _{k=0}^n{S}_k(\omega ){\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega )$. Интерпретация такова: $S_{{\tau }_n}$ — это значение случайного блуждания в момент ${\tau }_n$. Если ${\tau }_n<n$, то $S_{{\tau }_n}\in \{A;B\}$; если ${\tau }_n=n$, то $A⩽S_{{\tau }_n}⩽B$. Вспомним, что $p=q=0,5$, и докажем, что $𝔼(S_{{\tau }_n})=0$, $𝔼(S_{{\tau }_n}^2)=𝔼({\tau }_n)$.

Для доказательства первого равенства напишем: $𝔼(S_{{\tau }_n})=\sum _{k=0}^n𝔼(S_k{\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))=\sum _{k=0}^n𝔼(S_n{\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))+\sum _{k=0}^n((S_k-S_n){\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))=𝔼(S_n)+\sum _{k=0}^n((S_k-S_n){\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))$. Совершенно очевидно, что $𝔼(S_n)=0$, так как $S_n={\xi }_1+\dots +{\xi }_n$, ${\xi }_i=\pm 1$ при $p=q$. Осталось доказать, что $\sum _{k=0}^n((S_k-S_n){\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))=0$.

Для $0⩽k<n$ справедливо, что $\{{\tau }_n>k\}=\{A<S_1<B;\dots ;A<S_k<B\}$. Последнее событие может быть представлено в виде $\{\omega :({\xi }_1;\dots ;{\xi }_n)\in J\}$, где $J$ — некоторое подмножество множества $\{-1;+1{\}}^k$. Это множество определяется только ${\xi }_i$ при $i=\overline{1;k}$. Для больших $i$ значения ${\xi }_{k+1};\dots ;{\xi }_n$ не влияют на $J$. Множество вида $\{{\tau }_n=k\}=\{{\tau }_n>k-1\}\mathrm{\setminus }\{{\tau }_n>k\}$ также может быть представлено в виде $\{\omega :({\xi }_1;\dots ;{\xi }_n)\in J\}$. Благодаря независимости ${\xi }_i$ (доказано в подзадаче 2) вытекает, что $\mathrm{\forall }0⩽k<n$ случайные величины $S_n-S_k$ и ${\mathrm{𝟏}}_{\{{\tau }_n=k\}}$ независимы. Отсюда $𝔼(S_k\cdot {\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))=𝔼(S_k)\cdot 𝔼({\mathrm{𝟏}}_{\{{\tau }_n=k\}}(\omega ))=0$ в силу того, что первый множитель нулевой.

$𝔼(S_{{\tau }_n}^2)=\sum _{k=0}^n𝔼(S_k^2{\mathrm{𝟏}}_{\{{\tau }_n=k\}})=$

$=\sum _{k=0}^n𝔼\left(\right(S_n+(S_k-S_n{)}^2){\mathrm{𝟏}}_{\{{\tau }_n=k\}})=\sum _{k=0}^n(𝔼(S^2){\mathrm{𝟏}}_{\{{\tau }_n=k\}}+2𝔼(S_n(S_k-S_n)){\mathrm{𝟏}}_{\{{\tau }_n=k\}}+𝔼((S_n-S_k{)}^2\left){\mathrm{𝟏}}_{\{{\tau }_n=k\}}\right)=$

$=𝔼(S^2)-\sum _{k=0}^n𝔼((S_n-S_k{)}^2){\mathrm{𝟏}}_{\{{\tau }_n=k\}}=n-\sum _{k=0}^n𝔼(n-k)\mathbb{P}(\{{\tau }_n=k\})=\sum _{k=0}^{n}k\mathbb{P}(\{{\tau }_n=k\})=𝔼({\tau }_n).$

Установлено, что для идеальной монетки $𝔼(S_{{\tau }_n})=0$, $𝔼(S_{{\tau }_n}^2)=𝔼({\tau }_n)$.

В случае же $p\ne q$ имеют место соотношения $𝔼(S_{{\tau }_n})=(p-q)𝔼({\tau }_n)$ (поскольку $𝔼({\xi }_1)=p-q$) и $𝔼\left(\right(S_{{\tau }_n}-{\tau }_n𝔼({\xi }_1){)}^2)=\mathrm{V}\mathrm{a}\mathrm{r}({\xi }_1)\cdot 𝔼({\tau }_n)$, поскольку $\mathrm{V}\mathrm{a}\mathrm{r}({\xi }_1)=1-(p-q{)}^2$. Теперь покажем, что $\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}{m}_n(0)=m(0)<\mathrm{\infty }$.

В случае справедливой игры в силу соотношения $𝔼(S_{{\tau }_n}^2)=𝔼({\tau }_n)$ верно, что $𝔼({\tau }_n)⩽\max \{A^2;B^2\}$. Тогда же $𝔼({\tau }_n)=𝔼(S_{{\tau }_n}^2)=A^2{\alpha }_n+B^2{\beta }_n+𝔼(S_n^2{\mathrm{𝟏}}_{\{A<S_n<B\}}){\mathrm{𝟏}}_{\{{\tau }_n=n\}}$, поэтому $A^2{\alpha }_n+B^2{\beta }_n⩽𝔼({\tau }_n)⩽A^2{\alpha }_n+B^2{\beta }_n+\max \{A^2;B^2\}\cdot {\gamma }_n$. Из неравенства ${\gamma }_n<{\epsilon }^n$ следует, что математическое ожидание $𝔼({\tau }_n)$ сходится при $n\to \mathrm{\infty }$ к предельному значению $m(0)=A^2\alpha +B^2\beta =A^2\cdot \frac{B}{B-A}-B^2\cdot \frac{A}{B-A}=|AB|$. В случае несправедливой игры $𝔼({\tau }_n)⩽\frac{\max \{|A|;B\}}{|p-q|}$. Так как за ${\tau }_n$ обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии $𝔼({\tau }_n)\to m(0)=\frac{\alpha A+\beta B}{p-q}$. $◼$

Компьютерное моделирование (метод Монте-Карло)

Для моделирования игры воспользуемся программой MATLAB.

Для начала сгенерируем последовательность ${\xi }_i$, а затем при некотором первоначальном богатстве $x$ создадим цепочку $S_k$:

Последовательность ξ (getXI)

n = 100;                             % The length of \xi_i series
U = rand(n,1);                       % Generate 100 random uniform [0;1] values
XI = zeros(n,1);                     % Reserve memory for 100 modified Bernoulli
q = 0.55;                            % Reverse probability
p = 1 - q;                           % Averse probability

                                     % The following cycle creates a Bernoulli distribution based on uniform [0;1]
for i = 1:n                          % This cycle divides the [0;1] array into 2 parts: lengths q and p, q+p=1
   if (U(i,1) < q)                        
       XI(i,1) = -1;                 % If a uniform random value falls into q then \xi=-1
   else XI(i,1) = 1;                 % If a uniform random value falls into p then \xi=+1
   end
end

x = 10;                              % Initial 1st player's budget offset

S = zeros(n,1);                      % Reserve memory for 100 S_1...S_100

for i = 1:n                          % Make S_k series according to rule S_{k+1} = S_k + \xi_{k+1}
    S(i,1) = x + sum(XI(1:i, 1));    % considering the initial welfare offset x
end

Затем введём функцию getS(n, q, x), которая бы не просто, как листинг выше, генерировала ряд $S_k$ сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений $n$, $q$ и $x$ построить ряд, не усложняя вычислений. Это бы упростило рабочую область.

Генерация ряда (getS function)

function [S] = getS(n, q, x)         % This function depends on n, q and x --- 3 variables
U = rand(n,1);
XI = zeros(n,1);

for i = 2:n                          % Uniform->Bernoulli distribution transformation
   if (U(i,1) < q)
       XI(i,1) = -1; 
   else XI(i,1) = 1;
   end
end

S = zeros(n,1);                      % Reserve memory for n S_1...S_n

for i = 2:n                          % Calculate the S_1...S_n series
    S(i,1) = sum(XI(1:i, 1));        % Sums the \xi's
end
S = x + S;                           % Adds initial welfare to each S_k of the whole matrix

Возникает разумный вопрос: зачем считать $\xi$, начиная только со второй величины (for i = 2:n)? Дело в том, что это делается исключительно в целях наглядной визуализации. При построении графика в следующем коде будут строиться траектории $S_k$, и если бы было написано for i = 1:n, то тогда уже с самого первого значения некоторые траектории бы выходили из $x-1$, некоторые — из $x+1$. Так как в данной программе из соображений оптимальности лучше не задействовать нулевое значение (из него частица выходит, но не рисуется, так как прибавление ${\xi }_1$ происходит сразу), то просто-напросто сдвинем нумерацию на оси абсцисс на единицу вправо. Теперь проведём серию тестов и наглядно рассмотрим возможные траектории при некоторых вероятностях, длинах игры и количестве игр.

Визуализация (graphS)

Три игры в 10 шагов при $q=0,45$.

Пять игр в 100 шагов при $q=0,56$. Видно, что частицу «тянет вниз» к точке $A$.

Сто справедливых игр в 10000 шагов.

N = 3;                               % Number of games played
n = 10;                              % Number of tosses
q = 0.45;                            % Chance 1st player loses 1 rouble
x = 0;                               % Initial welfare offset

matrS = zeros(N, n);                 % Reserve memory for N rows n cols matrix
for i = 1:N                          % This loop fills the S matrix with S_k, yielding N trajectories
    matrS(i,:) = getS(n, q, x)';
    plot(matrS(i,:));                % Gives an image
    hold on;                         % Holds the axes for next trajectory overlay
end
hold off;                            % Clears axes for a new plot

Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах $(A;B;n;q)$. Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока ($\beta (x)$) при заданных начальных капиталах и сопоставлять её с теоретической.

Полная модель игры (Monte_Carlo)

N = 3000;                                 % Number of games played
n = 3000;                                 % Number of tosses
q = 0.5;                                  % Chance 1st player loses 1 rouble
p = 1-q;                                  % Chance 1st player wins 1 rouble
A = -10;                                  % 1st player budget
B = 10;                                   % 2nd player budget
x = 0;                                    % Budget offset towards 1st player
Bs = 0;                                   % amount of cases particle hits B (it will change soon)
As = 0;                                   % amount of cases particle hits A (it will change soon)

matrS = zeros(N, n);                      % Reserve memory for N rows n cols matrix
TAU1 = n * ones(N, n);                    % Fill another N rows n cols matrix with n's
for i = 1:N                               % This loop makes up N trajectories of S_k relying on input q, x, n
  matrS(i,:) = getS(n, q, x)';
  for j = 1:n
      if (matrS(i,j) == A)||(matrS(i,j) == B) % If a particle exceeds A or B, then
      TAU1(i,j) = j;                          % put the number of step into the table
      end
  end
  plot(matrS(i,:));                       % Displays a figure
  grid on;
  hold on;                                % Simultaneous plots within same axes
end
hold off;                                 % Clears axes for a new plot

TAU = (min(TAU1'))';                      % TAU = earliest step of [A;B] corridor overrun

% As [min] affects columns and gives row then we transpose TAU1,
% minimize it by rows and make it a column again
for i = 1:N                               % Our S_n series are ready; they nest in matrS
    for j=1:TAU(i)                        % Scan only till we encounter the escape step!
        if (matrS(i,j) == A);             % If a particle escaped through A (1st player busted)
        As = As+1;                        % then add +1 to 1st player's failures
        elseif (matrS(i,j) == B)          % Otherwise if its first threshold was B
        Bs = Bs+1;                        % then add +1 to 1st player's wins
        end                               % If n is not large enough, then
    end                                   % As + Bs may not make up N
end
ALPHA = As/(As+Bs)                        % Match alphas with their theoretical values
if (q == p)
   THEORALPHA = (B-x)/(B-A)
else THEORALPHA = ((q/p)^B - (q/p)^x)/((q/p)^B - (q/p)^A)
end
BETA = 1-ALPHA                            % Same for betas
if (q == p)
   THEORBETA = (x-A)/(B-A)
else THEORBETA = 1-THEORALPHA
end
meanTAU = mean(TAU)                       % Law of large numbers for great N's
if (q == p)
   THEORTAU = (B-x)*(x-A)
else THEORTAU = 1/(p-q)*(B*THEORBETA+A*THEORALPHA-x)
end

Отметим, что при небольших $n$ не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших $n$ вероятность ${\beta }_n(x)$ близка к $\beta (x)$».

Тестирование

Нижеследующие данные рассчитаны для $n=3000$, $N=3000$.

№ теста	$q$	$A$	$B$	$x$	ALPHA	$\alpha (x)$	BETA	$\beta (x)$	meanTAU	$m(x)$
1	$0,49$	$-6$	$5$	$0$	$0,4020$	$0,4006$	$0,5980$	$0,5994$	$30,9307$	$29,6856$
2	$0,6$	$-60$	$6$	$-3$	$0,9733$	$0,9740$	$0,0267$	$0,0260$	$278,2200$	$276,4159$
3	$0,6$	$-20$	$2$	$-1$	$0,7040$	$0,7038$	$0,2960$	$0,2962$	$62,2680$	$62,4178$
4	$0,54$	$-10$	$50$	$10$	$0,9990$	$0,9984$	$0,0010$	$0,0016$	$251,3587$	$248,8205$
5	$0,5$	$-10$	$20$	$0$	$0,6580$	$0,6667$	$0,3420$	$0,3333$	$202,3007$	$200,0000$
6	$0,35$	$-3$	$90$	$0$	$0,1457$	$0,1561$	$0,8543$	$0,8439$	$256,4557$	$251,6022$

В экспериментах 2 и 3 продемонстрировано свойство: если игра проигрышная для первого игрока, то увеличение ставки в модели эквивалентно сокращению $A$, $B$ и $x$ в одно и то же число раз относительно нуля. Ставка увеличилась втрое — вероятность выскочить из коридора со значением $B$ выросла в 11 раз!

См. также

• Случайное блуждание
• Случайный процесс
• Формула полной вероятности
• Распределение Бернулли
• Метод Монте-Карло