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

Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[1].

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

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

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

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

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

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

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

$\Omega ={\bigl \{}\omega \colon \omega =(x_{1};\ldots ;x_{n}),\ x_{i}=\pm 1{\bigr \}}$ – элементарные исходы,
${\mathcal {A}}=\{A_{i}\subseteq \Omega \}$ — алгебра подмножеств вероятностного пространства,
$\mathbb {P} {\bigl (}\{\omega \}{\bigr )}=p^{\nu (\omega )}\cdot q^{n-\nu (\omega )}$ , где $\nu (\omega )$ — количество выпавших в данной последовательность единиц.

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

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

$i={\overline {1;n}},\quad \xi _{i}(\omega )\colon \quad \mathbb {P} {\bigl (}\{\xi _{i}=1\}{\bigr )}=p,\quad \mathbb {P} {\bigl (}\{\xi _{i}=-1\}{\bigr )}=q,\quad p+q=1.$

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

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

Решение

$\sum \limits _{\omega \in \Omega }\mathbb {P} {\bigl (}\{\omega \}{\bigr )}=\sum \limits _{\omega \in \Omega }p^{\frac {\sum \limits _{i=1}^{n}x_{i}+n}{2}}\cdot q^{n-{\frac {\sum \limits _{i=1}^{n}x_{i}+n}{2}}}=\sum \limits _{k=0}^{n}\sum \limits _{\omega \in A_{k}}p^{\frac {\sum \limits _{i=1}^{n}(x_{i}+1)}{2}}\cdot q^{\frac {\sum \limits _{i=1}^{n}(1-x_{i})}{2}}=\sum \limits _{k=0}^{n}C_{n}^{k}p^{k}q^{n-k}.$ Это справедливо в силу того, что ${\frac {x_{i}+1}{2}}\in \{0;1\}.$

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

Подзадача о независимости случайных величин $\xi _{i}$

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

Решение

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

$\mathbb {P} {\bigl (}\{\xi _{1}=1\}\cap \{\xi _{2}=1\}{\bigr )}=\mathbb {P} {\bigl (}\{\xi _{1}=1\}{\bigr )}\mathbb {P} {\bigl (}\{\xi _{2}=1\}{\bigr )},$

покажем это:

\mathbb {P} {\bigl (}\{\xi _{1}=1\}\cap \{\xi _{2}=1\}{\bigr )}=\mathbb {P} {\bigl (}\{\omega \colon \omega =(x_{1};\ldots ;x_{n}),\ x_{1}=1,\ x_{2}=1\}{\bigr )}=

=\sum \limits _{\begin{smallmatrix}x_{3}=\pm 1\\\ldots {}\\x_{n}=\pm 1\end{smallmatrix}}p^{\frac {2+\sum \limits _{i=3}^{n}x_{i}+n}{2}}\cdot q^{n-{\frac {2+\sum \limits _{i=3}^{n}x_{i}+n}{2}}}=p^{2}\sum \limits _{\begin{smallmatrix}x_{3}=\pm 1\\\ldots {}\\x_{n}=\pm 1\end{smallmatrix}}p^{\frac {\sum \limits _{i=3}^{n}x_{i}+(n-2)}{2}}\cdot q^{(n-2)-{\frac {\sum \limits _{i=3}^{n}x_{i}+(n-2)}{2}}}=p^{2}\cdot 1.

\blacksquare

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

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

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

$S_{0}=0$ , $S_{k}=\xi _{1}+\ldots {}+\xi _{k},\quad 1\leqslant k\leqslant n$ .

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

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

Далее, пусть $x$ — целое число, $x\in \mathbb {Z} \cap [A;B]$ . Пусть также для $0\leqslant k\leqslant n$ верно, что $S_{k}^{x}=x+S_{k}$ (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть $\tau _{k}^{x}=\min {\bigl \{}l\colon 0\leqslant l\leqslant k,S_{l}^{x}=\{A\mathrm {~or~} B\}{\bigr \}}$ . Условимся считать, что $\tau _{k}^{x}=k$ , если $A<S_{l}^{x}<B\quad \forall l\colon 0\leqslant l\leqslant k$ . Если частица так и не пересекла границы, то $x_{k}$ не определён.

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

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

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

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

(1) $\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid S_{1}^{x}=x+1)=\mathbb {P} ({\mathcal {B}}_{k-1}^{x+1})$ ,

(2) $\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid S_{1}^{x}=x-1)=\mathbb {P} ({\mathcal {B}}_{k-1}^{x-1})$ .

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

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

${\mathcal {B}}_{k}^{x}={\bigl \{}\omega \colon (x;x+\xi _{1};\ldots {};x+\xi _{1}+\ldots {}+\xi _{k})\in B_{k}^{x}{\bigr \}}$ , где $B_{k}^{x}$ — множество траекторий вида $(x;x+x_{1};\ldots {};x+x_{1}+\ldots {}+x_{k}),\quad x_{i}=\pm 1$ , которые за время $[0;k]$ впервые выходят из интервала $(A;B)$ в точке $B$ (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество ${\mathcal {B}}$ . Представим множество $B_{k}^{x}$ как $B_{k}^{x;x+1}\sqcup 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};\ldots {};x+1+x_{2}+\ldots +x_{k})$ из $B_{k}^{x;x+1}$ находится в однозначном соответствии с траекторией $(x+1;x+1+x_{2};\ldots {};x+1+x_{2}+\ldots +x_{k})$ из $B_{k-1}^{x+1}$ . Взаимно-однозначное соответствие доказывается от противного. Предположим, что $x_{1}=-1$ (неоднозначное соответствие); тогда данная траектория $(x;x-1;x-1+x_{2};\ldots ;x-1+x_{2}+\ldots +x_{k})$ не сможет вывести частицу из коридора за $k$ шагов (а только лишь за $k+2$ из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: $S_{k+1}=S_{k}+\xi _{k+1}$ . Из этого следует, что $\mathbb {P} {\Bigl (}{\big \{}(x+1;x+1+x_{2};\ldots ;x+1+x_{2}+\ldots +x_{k})\in B_{k-1}^{x+1}{\bigr \}}{\Bigr )}=\mathbb {P} {\Bigl (}{\bigl \{}(x+1;x+1+x_{1};\ldots ;x+1+x_{1}+\ldots +x_{k-1})\in B_{k-1}^{x+1}{\bigr \}}{\Bigr )}{\mathrel {\stackrel {\rm {def}}{=}}}\mathbb {P} ({\mathcal {B}}_{k-1}^{x+1})$ (так как $\xi _{i}$ суть независимые одинаково распределённые случайные величины).

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

\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid S_{1}^{x}=x+1)=\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid \xi _{1}=1)=\mathbb {P} {\bigl (}(x;x+\xi _{1};\ldots {};x+\xi _{1}+\ldots {}+\xi _{k})\in B_{k}^{x}\mid \xi _{1}=1{\bigr )}=

={\frac {\mathbb {P} {\bigl (}(x;x+\xi _{1};\ldots {};x+\xi _{1}+\ldots {}+\xi _{k})\in B_{k}^{x}\cap \xi _{1}=1{\bigr )}}{\mathbb {P} (\{\xi _{1}=1\})}}={\frac {\mathbb {P} {\bigl (}(x;x+1;\ldots {};x+1+\ldots {}+\xi _{k})\in B_{k}^{x}\cap \xi _{1}=1{\bigr )}}{\mathbb {P} (\{\xi _{1}=1\})}}=

=\mathbb {P} {\bigl (}\{(x;x+1;x+1+\xi _{2};\ldots {};x+1+\xi _{2}+\ldots {}+\xi _{k})\in B_{k}^{x}\}{\bigr )}=\mathbb {P} {\bigl (}\{(x;x+1;x+1+\xi _{1};\ldots {};x+1+\xi _{1}+\ldots {}+\xi _{k-1})\in B_{k}^{x}\}{\bigr )}=

=\mathbb {P} {\bigl (}\{(x;x+1;x+1+\xi _{1};\ldots {};x+1+\xi _{1}+\ldots {}+\xi _{k-1})\in B_{k-1}^{x+1}\}{\bigr )}=\mathbb {P} ({\mathcal {B}}_{k-1}^{x+1})=\beta _{k-1}(x+1)

.

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

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

Каждая траектория $(x;x-1;x-1+x_{2};\ldots {};x-1+x_{2}+\ldots +x_{k})$ из $B_{k}^{x;x+1}$ находится в однозначном соответствии с траекторией $(x-1;x-1+x_{2};\ldots {};x-1+x_{2}+\ldots +x_{k})$ из $B_{k-1}^{x-1}$ . Отсюда $\mathbb {P} {\Bigl (}{\bigl \{}(x-1;x-1+x_{2};\ldots ;x-1+x_{2}+\ldots +x_{k})\in B_{k-1}^{x-1}{\bigr \}}{\Bigr )}=\mathbb {P} {\Bigl (}{\bigl \{}(x-1;x-1+x_{1};\ldots ;x-1+x_{1}+\ldots +x_{k-1})\in B_{k-1}^{x-1}{\bigr \}}{\Bigr )}{\mathrel {\stackrel {\rm {def}}{=}}}\mathbb {P} ({\mathcal {B}}_{k-1}^{x-1}).$ $\blacksquare$

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

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

$\mathbb {P} ({\mathcal {B}}_{k}^{x})=\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid S_{1}^{x}=x+1)\cdot p+\mathbb {P} ({\mathcal {B}}_{k}^{x}\mid S_{1}^{x}=x-1)\cdot q=\mathbb {P} ({\mathcal {B}}_{k-1}^{x+1})\cdot p+\mathbb {P} ({\mathcal {B}}_{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)$ .

Также отметим, что ${\mathcal {B}}_{k-1}\subset {\mathcal {B}}_{k}$ , и поэтому $\beta _{k-1}(x)\leqslant \beta _{k}(x)\leqslant 1$ для $k\leqslant 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\leqslant 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 \limits _{l\rightarrow \infty }\beta _{l}(B)=\beta (B)$ . Это также будет доказано в этом разделе.

Сначала получим решение уравнения $\beta (x)=p\beta (x+1)+q\beta (x-1)$ . Пусть игра несправедливая ( $p\neq q$ ). В таком случае найдём корни уравнения, то есть $\beta (x)$ . Одно частное решение видно сразу: $\beta (x)=\mathrm {const} =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}-\left(a+b\left({\frac {q}{p}}\right)^{A}\right)}{a+b\left({\frac {q}{p}}\right)^{B}-\left(a+b\left({\frac {q}{p}}\right)^{A}\right)}}={\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)$ . $\blacksquare$

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

Рассмотрим вопрос о быстроте предельной сходимости $\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 \colon A<S_{k}<B;0\leqslant k\leqslant n\}$ . $\omega$ представляет собой событие $\bigcap \limits _{0\leqslant k\leqslant n}\{A<S_{k}<B\}$ . Рассмотрим число $n=rm$ , где $r,m\in \mathbb {Z}$ , и цепочку случайных величин $\zeta _{n}\colon \zeta _{1}=\sum \limits _{i=1}^{m}\xi _{i},~\zeta _{2}=\sum \limits _{i=m+1}^{2m}\xi _{i},~\ldots {},~\zeta _{r}=\sum \limits _{i=m(r-1)}^{rm}\xi _{i}$ . Если обозначить совокупное богатство за $C=|A|+B$ , то тогда $\{A<S_{k}<B;1\leqslant k\leqslant rm\}\subseteq {\bigl \{}|\zeta _{1}|<C;\ldots {};|\zeta _{r}|<C{\bigr \}}$ . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма $m$ штук $x_{i}$ меньше, чем совокупный запас.

Подзадача о независимости случайных величин $\zeta _{i}$

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

Решение

Докажем, что $\mathbb {P} {\bigl (}\{\zeta _{1}=m\}\cap \{\zeta _{2}=m\}{\bigr )}=\mathbb {P} {\bigl (}\{\zeta _{1}=m\}{\bigr )}\cdot \mathbb {P} {\bigl (}\{\zeta _{2}=m\}{\bigr )}.$

\mathbb {P} {\bigl (}\{\zeta _{1}=m\}\cap \{\zeta _{2}=m\}{\bigr )}=\mathbb {P} \left(\left\{\sum \limits _{i=1}^{m}\xi _{i}=m\right\}\cap \left\{\sum \limits _{i=m+1}^{2m}\xi _{i}=m\right\}\right)=

=\mathbb {P} {\bigl (}\{\xi _{1;\ldots ;m}=1\}\cap \{\xi _{m+1;\ldots ;2m}=1\}{\bigr )}=\mathbb {P} ^{2m}{\bigl (}\{\xi _{i}=1\}{\bigr )}=\mathbb {P} {\bigl (}\{\zeta _{1}=m\}{\bigr )}\cdot \mathbb {P} {\bigl (}\{\zeta _{2}=m\}{\bigr )}

.

\blacksquare

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

Из только что доказанного следует что ${\displaystyle \gamma _{n}\leqslant \mathbb {P} {\Bigl (}{\bigl \{}|\zeta _{1}|;\ldots$ .

Рассмотрим дисперсию: $\mathrm {Var} (\zeta _{1})=m{\bigl (}1-(p-q)^{2}{\bigr )}$ (что вполне правомерно, так как $1-(p-q)^{2}=1-{\bigl (}(p+q)^{2}-4pq{\bigr )}$ , а $\xi$ — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших $m$ и $0<p<1$ верно: $\mathbb {P} {\Bigl (}{\bigl \{}|\zeta _{1}|<C{\bigr \}}{\Bigr )}\leqslant \varepsilon _{1}$ , где $\varepsilon _{1}<1$ , так как если $\mathbb {P} {\Bigl (}{\bigl \{}|\zeta _{1}|\leqslant C{\bigr \}}{\Bigr )}=1$ , то $\mathrm {Var} (\zeta _{1})\leqslant C^{2}$ . Если $p=0$ или $p=1$ , то для довольно больших $m$ верно, что $\mathbb {P} {\Bigl (}{\bigl \{}|\zeta _{1}|<C{\bigr \}}{\Bigr )}=0$ , поэтому неравенство $\mathbb {P} {\Bigl (}{\bigl \{}|\zeta _{1}|<C{\bigr \}}{\Bigr )}\leqslant \varepsilon _{1}$ верно $\forall p\in [0;1]$ . Из вышесказанного следует, что $\gamma _{n}\leqslant \varepsilon ^{n}$ , где $\varepsilon =\varepsilon _{1}^{\frac {1}{m}}<1$ . Так как $\alpha +\beta =1$ , то $(\alpha -\alpha _{n})-(\beta -\beta _{n})=\gamma _{n}$ ; так как $\alpha \geqslant \alpha _{n}$ и $\beta \geqslant \beta _{n}$ , то $0\leqslant \alpha -\alpha _{n}\leqslant \gamma _{n}\leqslant \varepsilon ^{n}$ ; $0\leqslant \beta -\beta _{n}\leqslant \gamma _{n}\leqslant \varepsilon ^{n}$ при $\varepsilon <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}}},\qquad A\leqslant x\leqslant 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{cases}{\frac {x}{B}},&p=q=0{,}5,\\{\frac {\left({\frac {q}{p}}\right)^{x}-1}{\left({\frac {q}{p}}\right)^{B}-1}},&p\neq q\end{cases}}

.

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

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

Его вероятность проигрыша задана формулой $\lim \limits _{k\rightarrow \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} {\bigl (}\{\xi _{i}=2\}{\bigr )}=p$ , $\mathbb {P} {\bigl (}\{\xi _{i}=-2\}{\bigr )}=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(\left({\frac {q}{p}}\right)^{0{,}5B}-1\right)\cdot \left(\left({\frac {q}{p}}\right)^{0{,}5B}+1\right)}{\left(\left({\frac {q}{p}}\right)^{0{,}5B}-\left({\frac {q}{p}}\right)^{0{,}5A}\right)\cdot \left(\left({\frac {q}{p}}\right)^{0{,}5B}+\left({\frac {q}{p}}\right)^{0{,}5A}\right)}}=\alpha _{2}\cdot {\frac {\left(\left({\frac {q}{p}}\right)^{0{,}5B}+1\right)}{\left(\left({\frac {q}{p}}\right)^{0{,}5B}+\left({\frac {q}{p}}\right)^{0{,}5A}\right)}}>\alpha _{2}$ , так как $\alpha _{2}$ умножается на дробь, которая больше единицы при $q>p$ .

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

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

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

m_{k}(x)=\mathbb {E} (\tau _{k}^{x})=\sum \limits _{1\leqslant l\leqslant k}l\mathbb {P} {\bigl (}\{\tau _{k}^{x}=l\}{\bigr )}=\sum \limits _{1\leqslant l\leqslant k}l{\Bigl (}p\mathbb {P} {\bigl (}\{\tau _{k}^{x}=l\}{\big |}\{\xi _{1}=1\}{\bigr )}+q\mathbb {P} {\bigl (}\{\tau _{k}^{x}=l\}{\big |}\{\xi _{1}=-1\}{\bigr )}{\Bigr )}=

=\sum \limits _{1\leqslant l\leqslant k}l{\Bigl (}p\mathbb {P} {\bigl (}\{\tau _{k-1}^{x+1}=l-1\}{\bigr )}+q\mathbb {P} {\bigl \{}\tau _{k-1}^{x-1}=l-1\}{\bigr )}{\Bigr )}=\sum \limits _{0\leqslant l\leqslant k-1}(l+1){\Bigl (}p\mathbb {P} {\bigl (}\{\tau _{k-1}^{x+1}=l\}{\bigr )}+q\mathbb {P} {\bigl (}\{\tau _{k-1}^{x-1}=l\}{\bigr )}{\Bigr )}=

=pm_{k-1}(x+1)+qm_{k-1}(x-1)+\sum \limits _{0\leqslant l\leqslant k-1}{\Bigl (}p\mathbb {P} {\bigl (}\{\tau _{k-1}^{x+1}=l\}{\bigr )}+q\mathbb {P} {\bigl (}\{\tau _{k-1}^{x-1}=l\}{\bigr )}{\Bigr )}=pm_{k-1}(x+1)+qm_{k-1}(x-1)+1.

Для $x\in (A;B)$ и $k\in [0;n]$ мы получили рекуррентное соотношение для функции $m_{k}(x)$ : $m_{k}(x)=pm_{k-1}(x+1)+qm_{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)\geqslant m_{k}(x)$ , то существует предел $m(x)=\lim \limits _{n\rightarrow \infty }m_{n}(x)$ , который удовлетворяет соотношению $m_{k}(x)=pm_{k-1}(x+1)+qm_{k-1}(x-1)+1$ : $m(x)=1+pm(x+1)+qm(x-1)$ при выполнении $m(A)=m(B)=0$ . Данные переходы аналогичны тем, что мы рассмотрели при переходе к $n\rightarrow \infty$ в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть $m(x)<\infty$ , $x\in (A;B)$ .

Решим данное уравнение. В уравнении вероятности проигрыша ( $p\neq 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}}{\bigl (}B\beta (x)+A\alpha (x)-x{\bigr )}$ . В случае идеальной монетки получаем следующее выражение: $m(x)=a+bx-x^{2}$ . Применение граничного условия даёт: $m(x)=(B-x)(x-A)$ . Из этого следует, что в случае равных стартовых капиталов $m(0)=B^{2}$ . Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.

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

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

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

Решение

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

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

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

Для доказательства первого равенства напишем: $\mathbb {E} (S_{\tau _{n}})=\sum \limits _{k=0}^{n}\mathbb {E} {\bigl (}S_{k}\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}=\sum \limits _{k=0}^{n}\mathbb {E} {\bigl (}S_{n}\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}+\sum \limits _{k=0}^{n}{\bigl (}(S_{k}-S_{n})\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}=\mathbb {E} (S_{n})+\sum \limits _{k=0}^{n}{\bigl (}(S_{k}-S_{n})\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}$ . Совершенно очевидно, что $\mathbb {E} (S_{n})=0$ , так как $S_{n}=\xi _{1}+\ldots +\xi _{n}$ , $\xi _{i}=\pm 1$ при $p=q$ . Осталось доказать, что $\sum \limits _{k=0}^{n}{\bigl (}(S_{k}-S_{n})\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}=0$ .

Для $0\leqslant k<n$ справедливо, что $\{\tau _{n}>k\}=\{A<S_{1}<B;\ldots ;A<S_{k}<B\}$ . Последнее событие может быть представлено в виде ${\displaystyle {\bigl \{}\omega \colon (\xi _{1};\ldots$ , где $J$ — некоторое подмножество множества $\{-1;+1\}^{k}$ . Это множество определяется только $\xi _{i}$ при $i={\overline {1;k}}$ . Для больших $i$ значения ${\displaystyle \xi _{k+1};\ldots$ не влияют на $J$ . Множество вида $\{\tau _{n}=k\}=\{\tau _{n}>k-1\}\backslash \{\tau _{n}>k\}$ также может быть представлено в виде ${\displaystyle {\bigl \{}\omega \colon (\xi _{1};\ldots$ . Благодаря независимости $\xi _{i}$ (доказано в подзадаче 2) вытекает, что $\forall 0\leqslant k<n$ случайные величины $S_{n}-S_{k}$ и $\mathbf {1} _{\{\tau _{n}=k\}}$ независимы. Отсюда $\mathbb {E} {\bigl (}S_{k}\cdot \mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}=\mathbb {E} (S_{k})\cdot \mathbb {E} {\bigl (}\mathbf {1} _{\{{\tau _{n}=k}\}}(\omega ){\bigr )}=0$ в силу того, что первый множитель нулевой.

\mathbb {E} (S_{\tau _{n}}^{2})=\sum \limits _{k=0}^{n}\mathbb {E} (S_{k}^{2}\mathbf {1} _{\{{\tau _{n}=k}\}})=

=\sum \limits _{k=0}^{n}\mathbb {E} {\Bigl (}{\bigl (}S_{n}+(S_{k}-S_{n})^{2}{\bigr )}\mathbf {1} _{\{{\tau _{n}=k}\}}{\Bigr )}=\sum \limits _{k=0}^{n}{\Bigl (}\mathbb {E} (S^{2})\mathbf {1} _{\{{\tau _{n}=k}\}}+2\mathbb {E} {\bigl (}S_{n}(S_{k}-S_{n}){\bigr )}\mathbf {1} _{\{{\tau _{n}=k}\}}+\mathbb {E} {\bigl (}(S_{n}-S_{k})^{2}{\bigr )}\mathbf {1} _{\{{\tau _{n}=k}\}}{\Bigr )}=

=\mathbb {E} (S^{2})-\sum \limits _{k=0}^{n}\mathbb {E} {\bigl (}(S_{n}-S_{k})^{2}{\bigr )}\mathbf {1} _{\{{\tau _{n}=k}\}}=n-\sum \limits _{k=0}^{n}\mathbb {E} (n-k)\mathbb {P} {\bigl (}\{\tau _{n}=k\}{\bigr )}=\sum \limits _{k=0}^{n}k\mathbb {P} {\bigl (}\{\tau _{n}=k\}{\bigr )}=\mathbb {E} (\tau _{n}).

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

В случае же $p\neq q$ имеют место соотношения $\mathbb {E} (S_{\tau _{n}})=(p-q)\mathbb {E} (\tau _{n})$ (поскольку $\mathbb {E} (\xi _{1})=p-q$ ) и $\mathbb {E} {\Bigl (}{\bigl (}S_{\tau _{n}}-\tau _{n}\mathbb {E} (\xi _{1}){\bigr )}^{2}{\Bigr )}=\mathrm {Var} (\xi _{1})\cdot \mathbb {E} (\tau _{n})$ , поскольку $\mathrm {Var} (\xi _{1})=1-(p-q)^{2}$ . Теперь покажем, что $\lim \limits _{n\rightarrow \infty }m_{n}(0)=m(0)<\infty$ .

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

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

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

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

Последовательность $\xi$ (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 раз!

См. также

Примечания

Ширяев А. Н. Вероятность—1, Вероятность—2 // Москва, МЦНМО. — 2007.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Ширяев А. Н. Вероятность—1, Вероятность—2 // Москва, МЦНМО. — 2007.

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

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

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

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

Подзадача о независимости случайных величин ξ i {\displaystyle \xi _{i}}

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

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

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

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

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

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

Подзадача о независимости случайных величин ζ i {\displaystyle \zeta _{i}}

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

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

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

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

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

Последовательность ξ {\displaystyle \xi } (getXI)

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

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

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

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

См. также

Примечания

Подзадача о независимости случайных величин $\xi _{i}$

Подзадача о независимости случайных величин $\zeta _{i}$

Последовательность $\xi$ (getXI)