Задача о разорении игрока
Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[1].
Формулировка
За столом сидят два игрока. У первого в распоряжении находится [math]\displaystyle{ -A\ (A\lt 0, -A\gt 0) }[/math] рублей, у второго в распоряжении находится [math]\displaystyle{ B\ (B\gt 0) }[/math] рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за [math]\displaystyle{ n }[/math] шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.
Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор [math]\displaystyle{ [A;B] }[/math]. Рассматривается вероятность того, что частица выйдет из коридора за [math]\displaystyle{ n }[/math] шагов (проскочит через верхнюю или нижнюю стенку).
Схема Бернулли
Рассмотрим схему Бернулли с [math]\displaystyle{ n }[/math] испытаниями.
Пусть [math]\displaystyle{ (\Omega,\mathcal{A},\mathbb{P}) }[/math] — вероятностное пространство, где
- [math]\displaystyle{ \Omega = \bigl\{\omega\colon \omega=(x_1;\ldots;x_n),\ x_i = \pm 1 \bigr\} }[/math] – элементарные исходы,
- [math]\displaystyle{ \mathcal{A} = \{ A_i \subseteq \Omega \} }[/math] — алгебра подмножеств вероятностного пространства,
- [math]\displaystyle{ \mathbb{P}\bigl(\{ \omega \}\bigr) = p^{\nu(\omega)}\cdot q^{n-\nu(\omega)} }[/math], где [math]\displaystyle{ \nu(\omega) }[/math] — количество выпавших в данной последовательность единиц.
В выражении выше число выпавших единиц можно найти так: [math]\displaystyle{ \nu(\omega) = \frac{\sum\limits_{i=1}^n x_i + n}{2} }[/math].
Введём последовательность бернуллиевских случайных величин:
[math]\displaystyle{ 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. }[/math]
Подзадача о нормированности вероятности
Доказать, что [math]\displaystyle{ \sum\limits_{\omega\in\Omega} \mathbb{P}\bigl(\{\omega\}\bigr) = 1. }[/math]
Решение
[math]\displaystyle{ \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^k_n p^k q^{n-k}. }[/math] Это справедливо в силу того, что [math]\displaystyle{ \frac{x_i+1}{2}\in \{ 0;1 \}. }[/math]
[math]\displaystyle{ \sum\limits_{k=0}^n C^k_n p^k q^{n-k} = (p+q)^n = 1 }[/math], поскольку по условию [math]\displaystyle{ p+q=1 }[/math]. [math]\displaystyle{ \blacksquare }[/math]
Подзадача о независимости случайных величин ξi
Доказать, что [math]\displaystyle{ \xi_1 }[/math] и [math]\displaystyle{ \xi_2 }[/math] независимы.
Решение
Независимость случайных величин означает, что
[math]\displaystyle{ \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), }[/math]
покажем это:
| [math]\displaystyle{ \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) = }[/math] |
| [math]\displaystyle{ =\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. }[/math] [math]\displaystyle{ \blacksquare }[/math] |
Случайное блуждание
Для схемы Бернулли договоримся о следующем смысле случайной величины ξ: [math]\displaystyle{ \xi_i = +1 }[/math] означает, что второй игрок платит первому, а [math]\displaystyle{ \xi_i = -1 }[/math] – первый игрок второму.
Введём новое обозначение:
[math]\displaystyle{ S_0 = 0 }[/math], [math]\displaystyle{ S_k = \xi_1 + \ldots{} + \xi_k, \quad 1\leqslant k \leqslant n }[/math].
Число [math]\displaystyle{ n }[/math] равно длительности игры, а последовательность [math]\displaystyle{ (S_k)_{k\leqslant n} }[/math] можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля, при этом очевидно равенство [math]\displaystyle{ S_{k+1} = S_k + \xi_{k+1} }[/math], а само [math]\displaystyle{ S_k }[/math] означает выигрыш первого игрока у второго (который может быть отрицательным).
Пусть [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] — два целых числа, [math]\displaystyle{ A\leqslant 0 }[/math], [math]\displaystyle{ B \geqslant 0 }[/math]. Требуется найти, с какой вероятностью за [math]\displaystyle{ n }[/math] шагов будет осуществлён выход частицы из коридора, ограниченного [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math].
Далее, пусть [math]\displaystyle{ x }[/math] — целое число, [math]\displaystyle{ x\in \mathbb{Z}\cap [A;B] }[/math]. Пусть также для [math]\displaystyle{ 0\leqslant k \leqslant n }[/math] верно, что [math]\displaystyle{ S^x_k = x+S_k }[/math] (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть [math]\displaystyle{ \tau^x_k = \min \bigl\{ l\colon 0\leqslant l \leqslant k, S^x_l = \{A \mathrm{~or~} B \} \bigr\} }[/math]. Условимся считать, что [math]\displaystyle{ \tau^x_k = k }[/math], если [math]\displaystyle{ A \lt S_l^x \lt B\quad \forall l\colon 0\leqslant l \leqslant k }[/math]. Если частица так и не пересекла границы, то [math]\displaystyle{ x_k }[/math] не определён.
Для каждого [math]\displaystyle{ 0\leqslant k \leqslant n }[/math] и [math]\displaystyle{ x\in [A; B]\cap \mathbb{Z} }[/math] момент [math]\displaystyle{ \tau^x_k }[/math] называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий [math]\displaystyle{ \Omega }[/math]. [math]\displaystyle{ \forall l\lt k\quad \{\omega\colon \tau^x_k = l\} }[/math] — это событие, состоящее в том, что случайное блуждание [math]\displaystyle{ \{S^x_i\colon 0\leqslant i \leqslant k \} }[/math], начинающееся в точке [math]\displaystyle{ x }[/math], выйдет из интервала [math]\displaystyle{ [A;B] }[/math] в момент [math]\displaystyle{ l }[/math]. Введём новые обозначения: [math]\displaystyle{ \mathcal{A}^x_k = \coprod\limits_{0\leqslant l \leqslant k}\{ \omega\colon \tau^x_k= l, \ S^x_l = A \} }[/math], [math]\displaystyle{ \mathcal{B}^x_k = \coprod\limits_{0\leqslant l \leqslant k}\{ \omega\colon \tau^x_k= l, \ S^x_l = B \} }[/math] для [math]\displaystyle{ 0\leqslant k \leqslant n }[/math]. Пусть [math]\displaystyle{ \alpha_k(x) = \mathbb{P} (\mathcal{A}^x_k) }[/math], [math]\displaystyle{ \beta_k(x) = \mathbb{P} (\mathcal{B}^x_k) }[/math] — вероятности выхода частицы за время [math]\displaystyle{ [0;k] }[/math] из интервала [math]\displaystyle{ [A;B] }[/math] соответственно в точках [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math].
Пусть [math]\displaystyle{ A\lt x\lt B }[/math]; очевидно, что [math]\displaystyle{ \alpha_0(x) = \beta_0 (x) = 0 }[/math] (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь [math]\displaystyle{ 0\leqslant k \leqslant n }[/math]. Тогда по формуле полной вероятности [math]\displaystyle{ \beta_k (x) = \mathbb{P} (\mathcal{B}^x_k) = \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 )\cdot \mathbb{P}\bigl(\{\xi_1 = 1 \}\bigr) + \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 )\cdot \mathbb{P}\bigl(\{ \xi_1 = -1 \}\bigr). }[/math]
Подзадача о рекуррентности
Доказать, что
(1) [math]\displaystyle{ \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ) }[/math],
(2) [math]\displaystyle{ \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 ) = \mathbb{P} ( \mathcal{B}^{x-1}_{k-1} ) }[/math].
Доказательство.
(1) Докажем, что [math]\displaystyle{ \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ) }[/math].
[math]\displaystyle{ \mathcal{B}^x_k = \bigl\{ \omega\colon (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k) \in B^x_k \bigr\} }[/math], где [math]\displaystyle{ B^x_k }[/math] — множество траекторий вида [math]\displaystyle{ (x;x+x_1;\ldots{};x+x_1+\ldots{}+x_k),\quad x_i=\pm 1 }[/math], которые за время [math]\displaystyle{ [0;k] }[/math] впервые выходят из интервала [math]\displaystyle{ (A;B) }[/math] в точке [math]\displaystyle{ B }[/math] (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество [math]\displaystyle{ \mathcal{B} }[/math]. Представим множество [math]\displaystyle{ B_k^x }[/math] как [math]\displaystyle{ B_k^{x;x+1}\sqcup B_k^{x;x-1} }[/math]. Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, [math]\displaystyle{ x_1=\pm 1 }[/math]. [math]\displaystyle{ B_k^{x;x+1} }[/math] — те траектории из [math]\displaystyle{ B_k^x }[/math], для которых [math]\displaystyle{ x_1=1 }[/math]. [math]\displaystyle{ B_k^{x;x-1} }[/math] — те траектории из [math]\displaystyle{ B_k^x }[/math], для которых [math]\displaystyle{ x_1=-1 }[/math]. Заметим, что каждая траектория [math]\displaystyle{ (x;x+1;x+1+x_2;\ldots{};x+1+x_2+\ldots+x_k) }[/math] из [math]\displaystyle{ B_k^{x;x+1} }[/math] находится в однозначном соответствии с траекторией [math]\displaystyle{ (x+1;x+1+x_2;\ldots{};x+1+x_2+\ldots+x_k) }[/math] из [math]\displaystyle{ B_{k-1}^{x+1} }[/math]. Взаимно-однозначное соответствие доказывается от противного. Предположим, что [math]\displaystyle{ x_1 = -1 }[/math] (неоднозначное соответствие); тогда данная траектория [math]\displaystyle{ (x;x-1;x-1+x_2;\ldots;x-1+x_2+\ldots+x_k) }[/math] не сможет вывести частицу из коридора за [math]\displaystyle{ k }[/math] шагов (а только лишь за [math]\displaystyle{ k+2 }[/math] из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: [math]\displaystyle{ S_{k+1} = S_k + \xi_{k+1} }[/math]. Из этого следует, что [math]\displaystyle{ \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}) }[/math] (так как [math]\displaystyle{ \xi_i }[/math] суть независимые одинаково распределённые случайные величины).
Существует и другой способ доказательства:
| [math]\displaystyle{ \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 ) = \mathbb{P} ( \mathcal{B}^x_k \mid \xi_1 = 1 ) = \mathbb{P} \bigl( (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k)\in B^x_k \mid \xi_1 = 1 \bigr) = }[/math] |
| [math]\displaystyle{ =\frac{\mathbb{P} \bigl( (x;x+\xi_1;\ldots{};x+\xi_1+\ldots{}+\xi_k)\in B^x_k \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^x_k \cap \xi_1 = 1 \bigr)}{\mathbb{P}(\{ \xi_1 = 1 \})} = }[/math] |
| [math]\displaystyle{ =\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) = }[/math] |
| [math]\displaystyle{ =\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) }[/math]. |
Это справедливо потому, что вероятности независимы (это было доказано ранее).
(2) Аналогично докажем, что [math]\displaystyle{ \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 ) = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1} ) }[/math].
Каждая траектория [math]\displaystyle{ (x;x-1;x-1+x_2;\ldots{};x-1+x_2+\ldots+x_k) }[/math] из [math]\displaystyle{ B_k^{x;x+1} }[/math] находится в однозначном соответствии с траекторией [math]\displaystyle{ (x-1;x-1+x_2;\ldots{};x-1+x_2+\ldots+x_k) }[/math] из [math]\displaystyle{ B_{k-1}^{x-1} }[/math]. Отсюда [math]\displaystyle{ \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}). }[/math] [math]\displaystyle{ \blacksquare }[/math]
Вывод рекуррентного соотношения
Из уравнения для [math]\displaystyle{ \beta_k(x) }[/math] следует, что для [math]\displaystyle{ x\in (A;B) }[/math] и [math]\displaystyle{ k\leqslant n }[/math] верно:
[math]\displaystyle{ \mathbb{P}(\mathcal{B}_k^x) = \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x+1 )\cdot p + \mathbb{P} ( \mathcal{B}^x_k \mid S_1^x = x-1 )\cdot q = \mathbb{P} ( \mathcal{B}^{x+1}_{k-1}) \cdot p + \mathbb{P} ( \mathcal{B}^{x-1}_{k-1})\cdot q = p\beta_{k-1}(x+1) + q\beta_{k-1}(x-1). }[/math]
[math]\displaystyle{ \beta_l(B)= 1 }[/math], [math]\displaystyle{ \beta_l(A)=0 }[/math] для [math]\displaystyle{ l\in[0;n] }[/math].
Формула полной вероятности также даёт нам следующий результат: [math]\displaystyle{ \alpha_k(x) = p\alpha_{k-1}(x+1) + q\alpha_{k-1}(x-1) }[/math].
Также отметим, что [math]\displaystyle{ \mathcal{B}_{k-1} \subset \mathcal{B}_{k} }[/math], и поэтому [math]\displaystyle{ \beta_{k-1}(x)\leqslant \beta_k(x)\leqslant 1 }[/math] для [math]\displaystyle{ k \leqslant n }[/math]. Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг ([math]\displaystyle{ x_{j-1}=\pm 1 }[/math]), на котором частица может прийти в точку [math]\displaystyle{ (j;S^x_{j}) }[/math] как из [math]\displaystyle{ (j-1;S^x_{j}-1) }[/math] (для [math]\displaystyle{ \xi_j=1 }[/math]), так и из [math]\displaystyle{ (j-1;S^x_{j}+1) }[/math] ([math]\displaystyle{ j\leqslant k }[/math]).
Нахождение вероятностей
При достаточно больших [math]\displaystyle{ n }[/math] вероятность [math]\displaystyle{ \beta_n (x) }[/math] близка к [math]\displaystyle{ \beta(x) }[/math] — решению уравнения [math]\displaystyle{ \beta(x) = p\beta(x+1) + q\beta(x-1) }[/math] при тех условиях, что [math]\displaystyle{ \beta(B)=1 }[/math] (выход произошёл сразу же из точки [math]\displaystyle{ B }[/math] — конец игры, выиграл первый игрок), [math]\displaystyle{ \beta(A)=0 }[/math] (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке [math]\displaystyle{ A }[/math]). Эти условия следуют из того, что [math]\displaystyle{ \lim\limits_{l\rightarrow\infty} \beta_l(B) = \beta(B) }[/math]. Это также будет доказано в этом разделе.
Сначала получим решение уравнения [math]\displaystyle{ \beta(x) = p\beta(x+1) + q\beta(x-1) }[/math]. Пусть игра несправедливая ([math]\displaystyle{ p\ne q }[/math]). В таком случае найдём корни уравнения, то есть [math]\displaystyle{ \beta(x) }[/math]. Одно частное решение видно сразу: [math]\displaystyle{ \beta(x) = \mathrm{const} = a }[/math]. Другое решение найдём, воспользовавшись тем, что [math]\displaystyle{ \beta(x) }[/math] — функция. Целесообразно употребить выражение с отношением [math]\displaystyle{ \frac{q}{p} }[/math], учитывая, что [math]\displaystyle{ p+q=1 }[/math]: [math]\displaystyle{ \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} }[/math]. Отсюда правомерно предположить, что [math]\displaystyle{ \beta(x) = b\cdot \left(\frac{q}{p}\right)^x }[/math]. Добавление константы ничего не изменит благодаря тому, что [math]\displaystyle{ p+q=1 }[/math].
Теперь рассмотрим общее решение: [math]\displaystyle{ \beta(x) = a + b\left(\frac{q}{p}\right)^x }[/math]. Воспользуемся теми условиями, что [math]\displaystyle{ \beta(A) = a+b\left(\frac{q}{p}\right)^A=0 }[/math] и [math]\displaystyle{ \beta(B) = a+b\left(\frac{q}{p}\right)^B=1 }[/math], и получим, что [math]\displaystyle{ \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}}. }[/math]
Подзадача о единственности решения
Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи [math]\displaystyle{ \beta(x) = p\beta(x+1) + q\beta(x-1) }[/math] с граничными условиями может быть представлено в виде [math]\displaystyle{ \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}} }[/math].
Решение
Рассмотрим некоторое решение [math]\displaystyle{ \check \beta(x) }[/math] при условиях [math]\displaystyle{ \check\beta (A)=0 }[/math], [math]\displaystyle{ \check\beta(B)=1 }[/math]. Тогда всегда можно подобрать такие константы [math]\displaystyle{ \check a }[/math] и [math]\displaystyle{ \check b }[/math], что [math]\displaystyle{ \check a + \check b \left( \frac{q}{p}\right)^{A} = \check\beta(A) }[/math], [math]\displaystyle{ \check a + \check b\left( \frac{q}{p}\right)^{A+1} = \check \beta(A+1) }[/math]. Тогда из уравнения поставленной задачи следует, что [math]\displaystyle{ \check\beta(A+2) = \check a + \check b \left( \frac{q}{p}\right)^{A+2} }[/math]. Тогда в общем случае [math]\displaystyle{ \check \beta(x) = \check a + \check b\left( \frac{q}{p}\right)^{x} }[/math]. Следовательно, решение [math]\displaystyle{ \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}} }[/math] является единственным. Точно такой же ход рассуждений может быть применён и к [math]\displaystyle{ \alpha(x) }[/math]. [math]\displaystyle{ \blacksquare }[/math]
Предельная сходимость
Рассмотрим вопрос о быстроте предельной сходимости [math]\displaystyle{ \alpha_n(x) }[/math] и [math]\displaystyle{ \beta_n(x) }[/math] к [math]\displaystyle{ \alpha(x) }[/math] и [math]\displaystyle{ \beta(x) }[/math]. Пусть блуждание начинается из начала координат ([math]\displaystyle{ x=0 }[/math]). Для простоты обозначим [math]\displaystyle{ \alpha_n(0)=\alpha_n }[/math], [math]\displaystyle{ \beta_n(0)=\beta_n }[/math], [math]\displaystyle{ \gamma_n = 1-\alpha_n-\beta_n }[/math]. Иными словами, [math]\displaystyle{ \gamma_n }[/math] — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: [math]\displaystyle{ \gamma_n = \mathbb{P} \{ \omega\colon A\lt S_k\lt B; 0\leqslant k \leqslant n \} }[/math]. [math]\displaystyle{ \omega }[/math] представляет собой событие [math]\displaystyle{ \bigcap\limits_{0\leqslant k \leqslant n} \{ A\lt S_k\lt B \} }[/math]. Рассмотрим число [math]\displaystyle{ n=rm }[/math], где [math]\displaystyle{ r,m\in \mathbb{Z} }[/math], и цепочку случайных величин [math]\displaystyle{ \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 }[/math]. Если обозначить совокупное богатство за [math]\displaystyle{ C = |A| +B }[/math], то тогда [math]\displaystyle{ \{A\lt S_k\lt B;1\leqslant k \leqslant rm \} \subseteq \bigl\{|\zeta_1|\lt C;\ldots{};|\zeta_r|\lt C\bigr\} }[/math]. Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма [math]\displaystyle{ m }[/math] штук [math]\displaystyle{ x_i }[/math] меньше, чем совокупный запас.
Подзадача о независимости случайных величин ζi
Докажем, что [math]\displaystyle{ \zeta_j }[/math] независимы и одинаково распределённые. Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение.
Решение
Докажем, что [math]\displaystyle{ \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). }[/math]
| [math]\displaystyle{ \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) = }[/math] |
| [math]\displaystyle{ =\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) }[/math]. [math]\displaystyle{ \blacksquare }[/math] |
Вернёмся к рассмотрению сходимости.
Из только что доказанного следует что [math]\displaystyle{ \gamma_n \leqslant \mathbb{P} \Bigl( \bigl\{ |\zeta_1|;\ldots;|\zeta_r|\lt C\bigr\} \Bigr) = \prod\limits_{i=1}^r \mathbb{P} \Bigl( \bigl\{ |\zeta_i|\lt C \bigr\} \Bigr) = \biggl( \mathbb{P} \Bigl( \bigl\{ |\zeta_1|\lt C \bigr\} \Bigr) \biggr)^r }[/math].
Рассмотрим дисперсию: [math]\displaystyle{ \mathrm{Var}(\zeta_1) = m\bigl(1-(p-q)^2\bigr) }[/math] (что вполне правомерно, так как [math]\displaystyle{ 1-(p-q)^2 =1-\bigl((p+q)^2-4pq\bigr) }[/math], а [math]\displaystyle{ \xi }[/math] — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших [math]\displaystyle{ m }[/math] и [math]\displaystyle{ 0\lt p\lt 1 }[/math] верно: [math]\displaystyle{ \mathbb{P}\Bigl( \bigl\{ |\zeta_1|\lt C\bigr\} \Bigr) \leqslant \varepsilon_1 }[/math], где [math]\displaystyle{ \varepsilon_1\lt 1 }[/math], так как если [math]\displaystyle{ \mathbb{P}\Bigl( \bigl\{ |\zeta_1|\leqslant C \bigr\} \Bigr)=1 }[/math], то [math]\displaystyle{ \mathrm{Var}(\zeta_1)\leqslant C^2 }[/math]. Если [math]\displaystyle{ p=0 }[/math] или [math]\displaystyle{ p=1 }[/math], то для довольно больших [math]\displaystyle{ m }[/math] верно, что [math]\displaystyle{ \mathbb{P}\Bigl( \bigl\{ |\zeta_1|\lt C \bigr\} \Bigr)=0 }[/math], поэтому неравенство [math]\displaystyle{ \mathbb{P}\Bigl( \bigl\{ |\zeta_1|\lt C \bigr\} \Bigr) \leqslant \varepsilon_1 }[/math] верно [math]\displaystyle{ \forall p\in[0;1] }[/math]. Из вышесказанного следует, что [math]\displaystyle{ \gamma_n \leqslant \varepsilon^n }[/math], где [math]\displaystyle{ \varepsilon = \varepsilon_1^{\frac{1}{m}}\lt 1 }[/math]. Так как [math]\displaystyle{ \alpha+\beta = 1 }[/math], то [math]\displaystyle{ (\alpha-\alpha_n)-(\beta-\beta_n)=\gamma_n }[/math]; так как [math]\displaystyle{ \alpha\geqslant \alpha_n }[/math] и [math]\displaystyle{ \beta\geqslant \beta_n }[/math], то [math]\displaystyle{ 0\leqslant \alpha-\alpha_n \leqslant \gamma_n \leqslant \varepsilon^n }[/math]; [math]\displaystyle{ 0\leqslant \beta-\beta_n \leqslant \gamma_n \leqslant \varepsilon^n }[/math] при [math]\displaystyle{ \varepsilon\lt 1 }[/math]. Аналогичные оценки справедливы и для разностей [math]\displaystyle{ \alpha(x)-\alpha_n(x) }[/math] и [math]\displaystyle{ \beta(x)-\beta_n(x) }[/math], так как можно свести эти разности к разностям [math]\displaystyle{ \alpha-\alpha_n }[/math] и [math]\displaystyle{ \beta-\beta_n }[/math] при [math]\displaystyle{ A_1 = A-x }[/math], [math]\displaystyle{ B_1=B-x }[/math].
Вернёмся к рассмотрению [math]\displaystyle{ \alpha(x) }[/math]. По аналогии с решением [math]\displaystyle{ \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}} }[/math] уравнения [math]\displaystyle{ \beta(x) = p\beta(x+1) + q\beta(x-1) }[/math], можно сказать, что у уравнения [math]\displaystyle{ \alpha(x) = p\alpha(x+1) + q\alpha(x-1) }[/math] при граничных условиях [math]\displaystyle{ \alpha(A)=1 }[/math], [math]\displaystyle{ \alpha(B)=0 }[/math] существует единственное решение [math]\displaystyle{ \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. }[/math]
Нетрудно заметить, что [math]\displaystyle{ \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 }[/math] при любых [math]\displaystyle{ p\in [0;1] }[/math]. Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: [math]\displaystyle{ \beta(x) = \frac{x-A}{B-A} }[/math], [math]\displaystyle{ \alpha(x) = \frac{B-x}{B-A} }[/math].
Ответ о вероятности разорения
Величины [math]\displaystyle{ \alpha(x) }[/math] и [math]\displaystyle{ \beta(x) }[/math] можно назвать вероятностями разорения первого и второго игрока при начальных капиталах [math]\displaystyle{ x-A }[/math] и [math]\displaystyle{ B-x }[/math] при стремлении количества ходов к бесконечности и характеризации случайной величина [math]\displaystyle{ \xi_i=+1 }[/math] как выигрыша первого игрока, а [math]\displaystyle{ \xi_i=-1 }[/math] — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.
Если [math]\displaystyle{ A=0 }[/math], то интуитивный смысл функции [math]\displaystyle{ \beta(x) }[/math] — это вероятность того, что частица, вышедшая из положения [math]\displaystyle{ x }[/math], достигнет верхней стенки ([math]\displaystyle{ B }[/math]) ранее, чем нуля. Из формул [math]\displaystyle{ \beta (x) }[/math] видно, что
- [math]\displaystyle{ \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\ne q \end{cases} }[/math].
Парадокс увеличения ставки при неблагоприятной игре
Что необходимо сделать первому игроку, если игра неблагоприятна для него?
Его вероятность проигрыша задана формулой [math]\displaystyle{ \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}} }[/math].
Теперь пусть первый игрок с капиталом [math]\displaystyle{ (-A) }[/math] примет решение удвоить ставку и играть на два рубля, то есть [math]\displaystyle{ \mathbb{P}\bigl( \{\xi_i=2\}\bigr)=p }[/math], [math]\displaystyle{ \mathbb{P}\bigl( \{\xi_i=-2\}\bigr)=q }[/math]. Тогда обозначим предельную вероятность разорения первого игрока так: [math]\displaystyle{ \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}} }[/math].
Поэтому [math]\displaystyle{ \alpha = \frac{\left( \frac{q}{p}\right)^{0{,}5B\cdot2} - 1^2}{ \left( \frac{q}{p}\right)^{0{,}5B\cdot2} - \left( \frac{q}{p}\right)^{0{,}5A\cdot2} } = \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)} \gt \alpha_2 }[/math], так как [math]\displaystyle{ \alpha_2 }[/math] умножается на дробь, которая больше единицы при [math]\displaystyle{ q\gt p }[/math].
Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше [math]\displaystyle{ 0{,}5 }[/math], то ему выгодно увеличить ставку в [math]\displaystyle{ r\gt 1 }[/math] раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке [math]\displaystyle{ B }[/math]. Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке [math]\displaystyle{ B }[/math].
Длительность случайного блуждания
Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: [math]\displaystyle{ \mathbb{E}(\tau^x_k)= m_k(x) }[/math] для [math]\displaystyle{ k\leqslant n }[/math]. Выведем рекуррентное соотношение для математического ожидания продолжительности игры:
| [math]\displaystyle{ 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) = }[/math] |
| [math]\displaystyle{ = \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) = }[/math] |
| [math]\displaystyle{ = 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. }[/math] |
Для [math]\displaystyle{ x\in (A;B) }[/math] и [math]\displaystyle{ k\in[0;n] }[/math] мы получили рекуррентное соотношение для функции [math]\displaystyle{ m_k(x) }[/math]: [math]\displaystyle{ m_k(x) = pm_{k-1}(x+1) + qm_{k-1}(x-1) + 1 }[/math] при [math]\displaystyle{ m_0(x)=0 }[/math].
Введём граничные условия: если игра начинается в точке [math]\displaystyle{ A }[/math] или [math]\displaystyle{ B }[/math], то тогда она тут же и завершится — её длительность будет равна 0: [math]\displaystyle{ m_k(A) = m_k(B)=0 }[/math].
Из рекуррентного соотношения и граничных условий можно один за другим вычислить [math]\displaystyle{ m_i(x) }[/math]. Так как [math]\displaystyle{ m_{k+1}(x) \geqslant m_k(x) }[/math], то существует предел [math]\displaystyle{ m(x) = \lim\limits_{n\rightarrow\infty} m_n(x) }[/math], который удовлетворяет соотношению [math]\displaystyle{ m_k(x) = pm_{k-1}(x+1) + qm_{k-1}(x-1) + 1 }[/math]: [math]\displaystyle{ m(x) = 1+pm(x+1) + qm(x-1) }[/math] при выполнении [math]\displaystyle{ m(A)=m(B)=0 }[/math]. Данные переходы аналогичны тем, что мы рассмотрели при переходе к [math]\displaystyle{ n\rightarrow\infty }[/math] в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть [math]\displaystyle{ m(x)\lt \infty }[/math], [math]\displaystyle{ x\in(A;B) }[/math].
Решим данное уравнение. В уравнении вероятности проигрыша ([math]\displaystyle{ p\ne q }[/math]) уже были получены частные решения [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b\left( \frac{q}{p}\right)^{x} }[/math]. Здесь же появляется ещё один претендент на роль частного решения: [math]\displaystyle{ \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} }[/math], поэтому [math]\displaystyle{ m(x) = \frac{x}{q-p} + a + b\left( \frac{q}{p}\right)^{x} }[/math]. С учётом граничного условия [math]\displaystyle{ m(A)=m(B)=0 }[/math] находим при помощи ранее полученных соотношений [math]\displaystyle{ m(x) }[/math]: [math]\displaystyle{ m(x) = \frac{1}{p-q}\bigl( B\beta(x) + A\alpha(x) - x\bigr) }[/math]. В случае идеальной монетки получаем следующее выражение: [math]\displaystyle{ m(x) = a+bx-x^2 }[/math]. Применение граничного условия даёт: [math]\displaystyle{ m(x)= (B-x)(x-A) }[/math]. Из этого следует, что в случае равных стартовых капиталов [math]\displaystyle{ m(0)=B^2 }[/math]. Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.
При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: [math]\displaystyle{ m(x)\lt \infty }[/math]. Теперь будет предложено доказательство этого факта.
Задача о конечности ожидаемого числа ходов
Доказать, что [math]\displaystyle{ m(x)\lt \infty\quad \forall A,B }[/math].
Решение
Достаточно доказать это для случая [math]\displaystyle{ x=0 }[/math] (так как ранее было уже продемонстрировано, что случаи [math]\displaystyle{ x\ne 0 }[/math] могут быть сведены к [math]\displaystyle{ x=0 }[/math] вариацией [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math]) и [math]\displaystyle{ p=q }[/math], а затем рассмотреть случай [math]\displaystyle{ p\ne q }[/math].
Итак, рассмотрим последовательность [math]\displaystyle{ S_{0;1;\ldots;n} }[/math] и введём случайную величину [math]\displaystyle{ S_{\tau_n} = S_{\tau_n}(\omega) }[/math], где [math]\displaystyle{ \tau_n=\tau_n^0 }[/math] — момент остановки.
Пусть [math]\displaystyle{ S_{\tau_n} (\omega) = \sum\limits_{k=0}^n S_k(\omega) \mathbf{1}_{\{ {\tau_n=k} \}}(\omega) }[/math]. Интерпретация такова: [math]\displaystyle{ S_{\tau_n} }[/math] — это значение случайного блуждания в момент [math]\displaystyle{ \tau_n }[/math]. Если [math]\displaystyle{ \tau_n\lt n }[/math], то [math]\displaystyle{ S_{\tau_n}\in \{A;B\} }[/math]; если [math]\displaystyle{ \tau_n=n }[/math], то [math]\displaystyle{ A\leqslant S_{\tau_n} \leqslant B }[/math]. Вспомним, что [math]\displaystyle{ p=q=0{,}5 }[/math], и докажем, что [math]\displaystyle{ \mathbb{E}(S_{\tau_n})=0 }[/math], [math]\displaystyle{ \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n) }[/math].
Для доказательства первого равенства напишем: [math]\displaystyle{ \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) }[/math]. Совершенно очевидно, что [math]\displaystyle{ \mathbb{E}(S_n)=0 }[/math], так как [math]\displaystyle{ S_n = \xi_1+\ldots+\xi_n }[/math], [math]\displaystyle{ \xi_i=\pm 1 }[/math] при [math]\displaystyle{ p=q }[/math]. Осталось доказать, что [math]\displaystyle{ \sum\limits_{k=0}^n \bigl( (S_k-S_n)\mathbf{1}_{\{ {\tau_n=k} \}}(\omega) \bigr) = 0 }[/math].
Для [math]\displaystyle{ 0\leqslant k \lt n }[/math] справедливо, что [math]\displaystyle{ \{ \tau_n\gt k \} = \{ A\lt S_1\lt B;\ldots;A\lt S_k\lt B\} }[/math]. Последнее событие может быть представлено в виде [math]\displaystyle{ \bigl\{\omega\colon (\xi_1;\ldots;\xi_n)\in J \bigr\} }[/math], где [math]\displaystyle{ J }[/math] — некоторое подмножество множества [math]\displaystyle{ \{ -1;+1 \}^k }[/math]. Это множество определяется только [math]\displaystyle{ \xi_i }[/math] при [math]\displaystyle{ i=\overline{1;k} }[/math]. Для больших [math]\displaystyle{ i }[/math] значения [math]\displaystyle{ \xi_{k+1};\ldots;\xi_n }[/math] не влияют на [math]\displaystyle{ J }[/math]. Множество вида [math]\displaystyle{ \{ \tau_n=k \} = \{ \tau_n\gt k-1 \} \backslash \{ \tau_n\gt k \} }[/math] также может быть представлено в виде [math]\displaystyle{ \bigl\{\omega\colon (\xi_1;\ldots;\xi_n)\in J \bigr\} }[/math]. Благодаря независимости [math]\displaystyle{ \xi_i }[/math] (доказано в подзадаче 2) вытекает, что [math]\displaystyle{ \forall 0\leqslant k \lt n }[/math] случайные величины [math]\displaystyle{ S_n-S_k }[/math] и [math]\displaystyle{ \mathbf{1}_{\{ \tau_n=k \}} }[/math] независимы. Отсюда [math]\displaystyle{ \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 }[/math] в силу того, что первый множитель нулевой.
| [math]\displaystyle{ \mathbb{E}(S_{\tau_n}^2) = \sum\limits_{k=0}^n \mathbb{E} ( S^2_k \mathbf{1}_{\{ {\tau_n=k} \}}) = }[/math] |
| [math]\displaystyle{ = \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) = }[/math] |
| [math]\displaystyle{ =\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). }[/math] |
Установлено, что для идеальной монетки [math]\displaystyle{ \mathbb{E}(S_{\tau_n})=0 }[/math], [math]\displaystyle{ \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n) }[/math].
В случае же [math]\displaystyle{ p\ne q }[/math] имеют место соотношения [math]\displaystyle{ \mathbb{E}(S_{\tau_n}) = (p-q)\mathbb{E}(\tau_n) }[/math] (поскольку [math]\displaystyle{ \mathbb{E}(\xi_1) = p-q }[/math]) и [math]\displaystyle{ \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) }[/math], поскольку [math]\displaystyle{ \mathrm{Var}(\xi_1) = 1-(p-q)^2 }[/math]. Теперь покажем, что [math]\displaystyle{ \lim\limits_{n\rightarrow\infty} m_n(0) = m(0)\lt \infty }[/math].
В случае справедливой игры в силу соотношения [math]\displaystyle{ \mathbb{E}(S_{\tau_n}^2) = \mathbb{E}(\tau_n) }[/math] верно, что [math]\displaystyle{ \mathbb{E}(\tau_n)\leqslant \max\{ A^2;B^2\} }[/math]. Тогда же [math]\displaystyle{ \mathbb{E} (\tau_n) = \mathbb{E}(S^2_{\tau_n}) = A^2 \alpha_n + B^2 \beta_n + \mathbb{E} (S^2_n \mathbf{1}_{\{{A\lt S_n\lt B}\}}) \mathbf{1}_{\{{\tau_n=n}\}} }[/math], поэтому [math]\displaystyle{ 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 }[/math]. Из неравенства [math]\displaystyle{ \gamma_n\lt \varepsilon^n }[/math] следует, что математическое ожидание [math]\displaystyle{ \mathbb{E}(\tau_n) }[/math] сходится при [math]\displaystyle{ n\rightarrow\infty }[/math] к предельному значению [math]\displaystyle{ m(0) = A^2\alpha + B^2 \beta = A^2 \cdot \frac{B}{B-A} - B^2\cdot \frac{A}{B-A} = |AB| }[/math]. В случае несправедливой игры [math]\displaystyle{ \mathbb{E}(\tau_n)\leqslant \frac{\max\{ |A|;B \}}{|p-q|} }[/math]. Так как за [math]\displaystyle{ \tau_n }[/math] обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии [math]\displaystyle{ \mathbb{E}(\tau_n)\rightarrow m(0) = \frac{\alpha A + \beta B}{p-q} }[/math]. [math]\displaystyle{ \blacksquare }[/math]
Компьютерное моделирование (метод Монте-Карло)
Для моделирования игры воспользуемся программой MATLAB.
Для начала сгенерируем последовательность [math]\displaystyle{ \xi_i }[/math], а затем при некотором первоначальном богатстве [math]\displaystyle{ x }[/math] создадим цепочку [math]\displaystyle{ S_k }[/math]:
Последовательность ξ (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), которая бы не просто, как листинг выше, генерировала ряд [math]\displaystyle{ S_k }[/math] сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений [math]\displaystyle{ n }[/math], [math]\displaystyle{ q }[/math] и [math]\displaystyle{ x }[/math] построить ряд, не усложняя вычислений. Это бы упростило рабочую область.
Генерация ряда (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
Возникает разумный вопрос: зачем считать [math]\displaystyle{ \xi }[/math], начиная только со второй величины (for i = 2:n)? Дело в том, что это делается исключительно в целях наглядной визуализации. При построении графика в следующем коде будут строиться траектории [math]\displaystyle{ S_k }[/math], и если бы было написано for i = 1:n, то тогда уже с самого первого значения некоторые траектории бы выходили из [math]\displaystyle{ x-1 }[/math], некоторые — из [math]\displaystyle{ x+1 }[/math]. Так как в данной программе из соображений оптимальности лучше не задействовать нулевое значение (из него частица выходит, но не рисуется, так как прибавление [math]\displaystyle{ \xi_1 }[/math] происходит сразу), то просто-напросто сдвинем нумерацию на оси абсцисс на единицу вправо. Теперь проведём серию тестов и наглядно рассмотрим возможные траектории при некоторых вероятностях, длинах игры и количестве игр.
Визуализация (graphS)
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
Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах [math]\displaystyle{ (A;B;n;q) }[/math]. Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока ([math]\displaystyle{ \beta(x) }[/math]) при заданных начальных капиталах и сопоставлять её с теоретической.
Полная модель игры (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
Отметим, что при небольших [math]\displaystyle{ n }[/math] не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших [math]\displaystyle{ n }[/math] вероятность [math]\displaystyle{ \beta_n(x) }[/math] близка к [math]\displaystyle{ \beta(x) }[/math]».
Тестирование
Нижеследующие данные рассчитаны для [math]\displaystyle{ n=3000 }[/math], [math]\displaystyle{ N = 3000 }[/math].
| № теста | [math]\displaystyle{ q }[/math] | [math]\displaystyle{ A }[/math] | [math]\displaystyle{ B }[/math] | [math]\displaystyle{ x }[/math] | ALPHA | [math]\displaystyle{ \alpha(x) }[/math] | BETA | [math]\displaystyle{ \beta(x) }[/math] | meanTAU | [math]\displaystyle{ m(x) }[/math] |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | [math]\displaystyle{ 0{,}49 }[/math] | [math]\displaystyle{ -6 }[/math] | [math]\displaystyle{ 5 }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0{,}4020 }[/math] | [math]\displaystyle{ 0{,}4006 }[/math] | [math]\displaystyle{ 0{,}5980 }[/math] | [math]\displaystyle{ 0{,}5994 }[/math] | [math]\displaystyle{ 30{,}9307 }[/math] | [math]\displaystyle{ 29{,}6856 }[/math] |
| 2 | [math]\displaystyle{ 0{,}6 }[/math] | [math]\displaystyle{ -60 }[/math] | [math]\displaystyle{ 6 }[/math] | [math]\displaystyle{ -3 }[/math] | [math]\displaystyle{ 0{,}9733 }[/math] | [math]\displaystyle{ 0{,}9740 }[/math] | [math]\displaystyle{ 0{,}0267 }[/math] | [math]\displaystyle{ 0{,}0260 }[/math] | [math]\displaystyle{ 278{,}2200 }[/math] | [math]\displaystyle{ 276{,}4159 }[/math] |
| 3 | [math]\displaystyle{ 0{,}6 }[/math] | [math]\displaystyle{ -20 }[/math] | [math]\displaystyle{ 2 }[/math] | [math]\displaystyle{ -1 }[/math] | [math]\displaystyle{ 0{,}7040 }[/math] | [math]\displaystyle{ 0{,}7038 }[/math] | [math]\displaystyle{ 0{,}2960 }[/math] | [math]\displaystyle{ 0{,}2962 }[/math] | [math]\displaystyle{ 62{,}2680 }[/math] | [math]\displaystyle{ 62{,}4178 }[/math] |
| 4 | [math]\displaystyle{ 0{,}54 }[/math] | [math]\displaystyle{ -10 }[/math] | [math]\displaystyle{ 50 }[/math] | [math]\displaystyle{ 10 }[/math] | [math]\displaystyle{ 0{,}9990 }[/math] | [math]\displaystyle{ 0{,}9984 }[/math] | [math]\displaystyle{ 0{,}0010 }[/math] | [math]\displaystyle{ 0{,}0016 }[/math] | [math]\displaystyle{ 251{,}3587 }[/math] | [math]\displaystyle{ 248{,}8205 }[/math] |
| 5 | [math]\displaystyle{ 0{,}5 }[/math] | [math]\displaystyle{ -10 }[/math] | [math]\displaystyle{ 20 }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0{,}6580 }[/math] | [math]\displaystyle{ 0{,}6667 }[/math] | [math]\displaystyle{ 0{,}3420 }[/math] | [math]\displaystyle{ 0{,}3333 }[/math] | [math]\displaystyle{ 202{,}3007 }[/math] | [math]\displaystyle{ 200{,}0000 }[/math] |
| 6 | [math]\displaystyle{ 0{,}35 }[/math] | [math]\displaystyle{ -3 }[/math] | [math]\displaystyle{ 90 }[/math] | [math]\displaystyle{ 0 }[/math] | [math]\displaystyle{ 0{,}1457 }[/math] | [math]\displaystyle{ 0{,}1561 }[/math] | [math]\displaystyle{ 0{,}8543 }[/math] | [math]\displaystyle{ 0{,}8439 }[/math] | [math]\displaystyle{ 256{,}4557 }[/math] | [math]\displaystyle{ 251{,}6022 }[/math] |
В экспериментах 2 и 3 продемонстрировано свойство: если игра проигрышная для первого игрока, то увеличение ставки в модели эквивалентно сокращению [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] и [math]\displaystyle{ x }[/math] в одно и то же число раз относительно нуля. Ставка увеличилась втрое — вероятность выскочить из коридора со значением [math]\displaystyle{ B }[/math] выросла в 11 раз!
См. также
- Случайное блуждание
- Случайный процесс
- Формула полной вероятности
- Распределение Бернулли
- Метод Монте-Карло
Примечания
- ↑ Ширяев А. Н. Вероятность—1, Вероятность—2 // Москва, МЦНМО. — 2007.