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

16.12.2020

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

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

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

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

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

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

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

  • Ω = { ω : ω = ( x 1 ; … ; x n ) ,   x i = ± 1 } {displaystyle Omega ={igl {}omega colon omega =(x_{1};ldots ;x_{n}), x_{i}=pm 1{igr }}} – элементарные исходы,
  • A = { A i ⊆ Ω } {displaystyle {mathcal {A}}={A_{i}subseteq Omega }} — алгебра подмножеств вероятностного пространства,
  • P ( { ω } ) = p ν ( ω ) ⋅ q n − ν ( ω ) {displaystyle mathbb {P} {igl (}{omega }{igr )}=p^{ u (omega )}cdot q^{n- u (omega )}} , где ν ( ω ) {displaystyle u (omega )} — количество выпавших в данной последовательность единиц.

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

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

i = 1 ; n ¯ , ξ i ( ω ) : P ( { ξ i = 1 } ) = p , P ( { ξ i = − 1 } ) = q , p + q = 1. {displaystyle i={overline {1;n}},quad xi _{i}(omega )colon quad mathbb {P} {igl (}{xi _{i}=1}{igr )}=p,quad mathbb {P} {igl (}{xi _{i}=-1}{igr )}=q,quad p+q=1.}

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

Доказать, что ∑ ω ∈ Ω P ( { ω } ) = 1. {displaystyle sum limits _{omega in Omega }mathbb {P} {igl (}{omega }{igr )}=1.}


Решение

∑ ω ∈ Ω P ( { ω } ) = ∑ ω ∈ Ω p ∑ i = 1 n x i + n 2 ⋅ q n − ∑ i = 1 n x i + n 2 = ∑ k = 0 n ∑ ω ∈ A k p ∑ i = 1 n ( x i + 1 ) 2 ⋅ q ∑ i = 1 n ( 1 − x i ) 2 = ∑ k = 0 n C n k p k q n − k . {displaystyle sum limits _{omega in Omega }mathbb {P} {igl (}{omega }{igr )}=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}.} Это справедливо в силу того, что x i + 1 2 ∈ { 0 ; 1 } . {displaystyle {frac {x_{i}+1}{2}}in {0;1}.}

∑ k = 0 n C n k p k q n − k = ( p + q ) n = 1 {displaystyle sum limits _{k=0}^{n}C_{n}^{k}p^{k}q^{n-k}=(p+q)^{n}=1} , поскольку по условию p + q = 1 {displaystyle p+q=1} . ◼ {displaystyle lacksquare }

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

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


Решение

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

P ( { ξ 1 = 1 } ∩ { ξ 2 = 1 } ) = P ( { ξ 1 = 1 } ) P ( { ξ 2 = 1 } ) , {displaystyle mathbb {P} {igl (}{xi _{1}=1}cap {xi _{2}=1}{igr )}=mathbb {P} {igl (}{xi _{1}=1}{igr )}mathbb {P} {igl (}{xi _{2}=1}{igr )},}

покажем это:

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

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

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

S 0 = 0 {displaystyle S_{0}=0} , S k = ξ 1 + … + ξ k , 1 ⩽ k ⩽ n {displaystyle S_{k}=xi _{1}+ldots {}+xi _{k},quad 1leqslant kleqslant n} .

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


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

Далее, пусть x {displaystyle x} — целое число, x ∈ Z ∩ [ A ; B ] {displaystyle xin mathbb {Z} cap [A;B]} . Пусть также для 0 ⩽ k ⩽ n {displaystyle 0leqslant kleqslant n} верно, что S k x = x + S k {displaystyle S_{k}^{x}=x+S_{k}} (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть τ k x = min { l : 0 ⩽ l ⩽ k , S l x = { A   o r   B } } {displaystyle au _{k}^{x}=min {igl {}lcolon 0leqslant lleqslant k,S_{l}^{x}={Amathrm {~or~} B}{igr }}} . Условимся считать, что τ k x = k {displaystyle au _{k}^{x}=k} , если A < S l x < B ∀ l : 0 ⩽ l ⩽ k {displaystyle A<S_{l}^{x}<Bquad forall lcolon 0leqslant lleqslant k} . Если частица так и не пересекла границы, то x k {displaystyle x_{k}} не определён.

Для каждого 0 ⩽ k ⩽ n {displaystyle 0leqslant kleqslant n} и x ∈ [ A ; B ] ∩ Z {displaystyle xin [A;B]cap mathbb {Z} } момент τ k x {displaystyle au _{k}^{x}} называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий Ω {displaystyle Omega } . ∀ l < k { ω : τ k x = l } {displaystyle forall l<kquad {omega colon au _{k}^{x}=l}} — это событие, состоящее в том, что случайное блуждание { S i x : 0 ⩽ i ⩽ k } {displaystyle {S_{i}^{x}colon 0leqslant ileqslant k}} , начинающееся в точке x {displaystyle x} , выйдет из интервала [ A ; B ] {displaystyle [A;B]} в момент l {displaystyle l} . Введём новые обозначения: A k x = ∐ 0 ⩽ l ⩽ k { ω : τ k x = l ,   S l x = A } {displaystyle {mathcal {A}}_{k}^{x}=coprod limits _{0leqslant lleqslant k}{omega colon au _{k}^{x}=l, S_{l}^{x}=A}} , B k x = ∐ 0 ⩽ l ⩽ k { ω : τ k x = l ,   S l x = B } {displaystyle {mathcal {B}}_{k}^{x}=coprod limits _{0leqslant lleqslant k}{omega colon au _{k}^{x}=l, S_{l}^{x}=B}} для 0 ⩽ k ⩽ n {displaystyle 0leqslant kleqslant n} . Пусть α k ( x ) = P ( A k x ) {displaystyle alpha _{k}(x)=mathbb {P} ({mathcal {A}}_{k}^{x})} , β k ( x ) = P ( B k x ) {displaystyle eta _{k}(x)=mathbb {P} ({mathcal {B}}_{k}^{x})} — вероятности выхода частицы за время [ 0 ; k ] {displaystyle [0;k]} из интервала [ A ; B ] {displaystyle [A;B]} соответственно в точках A {displaystyle A} и B {displaystyle B} .

Пусть A < x < B {displaystyle A<x<B} ; очевидно, что α 0 ( x ) = β 0 ( x ) = 0 {displaystyle alpha _{0}(x)=eta _{0}(x)=0} (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь 0 ⩽ k ⩽ n {displaystyle 0leqslant kleqslant n} . Тогда по формуле полной вероятности β k ( x ) = P ( B k x ) = P ( B k x ∣ S 1 x = x + 1 ) ⋅ P ( { ξ 1 = 1 } ) + P ( B k x ∣ S 1 x = x − 1 ) ⋅ P ( { ξ 1 = − 1 } ) . {displaystyle eta _{k}(x)=mathbb {P} ({mathcal {B}}_{k}^{x})=mathbb {P} ({mathcal {B}}_{k}^{x}mid S_{1}^{x}=x+1)cdot mathbb {P} {igl (}{xi _{1}=1}{igr )}+mathbb {P} ({mathcal {B}}_{k}^{x}mid S_{1}^{x}=x-1)cdot mathbb {P} {igl (}{xi _{1}=-1}{igr )}.}

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

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

(1) P ( B k x ∣ S 1 x = x + 1 ) = P ( B k − 1 x + 1 ) {displaystyle mathbb {P} ({mathcal {B}}_{k}^{x}mid S_{1}^{x}=x+1)=mathbb {P} ({mathcal {B}}_{k-1}^{x+1})} ,

(2) P ( B k x ∣ S 1 x = x − 1 ) = P ( B k − 1 x − 1 ) {displaystyle mathbb {P} ({mathcal {B}}_{k}^{x}mid S_{1}^{x}=x-1)=mathbb {P} ({mathcal {B}}_{k-1}^{x-1})} .

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

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

B k x = { ω : ( x ; x + ξ 1 ; … ; x + ξ 1 + … + ξ k ) ∈ B k x } {displaystyle {mathcal {B}}_{k}^{x}={igl {}omega colon (x;x+xi _{1};ldots {};x+xi _{1}+ldots {}+xi _{k})in B_{k}^{x}{igr }}} , где B k x {displaystyle B_{k}^{x}} — множество траекторий вида ( x ; x + x 1 ; … ; x + x 1 + … + x k ) , x i = ± 1 {displaystyle (x;x+x_{1};ldots {};x+x_{1}+ldots {}+x_{k}),quad x_{i}=pm 1} , которые за время [ 0 ; k ] {displaystyle [0;k]} впервые выходят из интервала ( A ; B ) {displaystyle (A;B)} в точке B {displaystyle B} (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество B {displaystyle {mathcal {B}}} . Представим множество B k x {displaystyle B_{k}^{x}} как B k x ; x + 1 ⊔ B k x ; x − 1 {displaystyle B_{k}^{x;x+1}sqcup B_{k}^{x;x-1}} . Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, x 1 = ± 1 {displaystyle x_{1}=pm 1} . B k x ; x + 1 {displaystyle B_{k}^{x;x+1}} — те траектории из B k x {displaystyle B_{k}^{x}} , для которых x 1 = 1 {displaystyle x_{1}=1} . B k x ; x − 1 {displaystyle B_{k}^{x;x-1}} — те траектории из B k x {displaystyle B_{k}^{x}} , для которых x 1 = − 1 {displaystyle x_{1}=-1} . Заметим, что каждая траектория ( x ; x + 1 ; x + 1 + x 2 ; … ; x + 1 + x 2 + … + x k ) {displaystyle (x;x+1;x+1+x_{2};ldots {};x+1+x_{2}+ldots +x_{k})} из B k x ; x + 1 {displaystyle B_{k}^{x;x+1}} находится в однозначном соответствии с траекторией ( x + 1 ; x + 1 + x 2 ; … ; x + 1 + x 2 + … + x k ) {displaystyle (x+1;x+1+x_{2};ldots {};x+1+x_{2}+ldots +x_{k})} из B k − 1 x + 1 {displaystyle B_{k-1}^{x+1}} . Взаимно-однозначное соответствие доказывается от противного. Предположим, что x 1 = − 1 {displaystyle x_{1}=-1} (неоднозначное соответствие); тогда данная траектория ( x ; x − 1 ; x − 1 + x 2 ; … ; x − 1 + x 2 + … + x k ) {displaystyle (x;x-1;x-1+x_{2};ldots ;x-1+x_{2}+ldots +x_{k})} не сможет вывести частицу из коридора за k {displaystyle k} шагов (а только лишь за k + 2 {displaystyle k+2} из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: S k + 1 = S k + ξ k + 1 {displaystyle S_{k+1}=S_{k}+xi _{k+1}} . Из этого следует, что P ( { ( x + 1 ; x + 1 + x 2 ; … ; x + 1 + x 2 + … + x k ) ∈ B k − 1 x + 1 } ) = P ( { ( x + 1 ; x + 1 + x 1 ; … ; x + 1 + x 1 + … + x k − 1 ) ∈ B k − 1 x + 1 } ) = d e f P ( B k − 1 x + 1 ) {displaystyle mathbb {P} {Bigl (}{ig {}(x+1;x+1+x_{2};ldots ;x+1+x_{2}+ldots +x_{k})in B_{k-1}^{x+1}{igr }}{Bigr )}=mathbb {P} {Bigl (}{igl {}(x+1;x+1+x_{1};ldots ;x+1+x_{1}+ldots +x_{k-1})in B_{k-1}^{x+1}{igr }}{Bigr )}{mathrel {stackrel { m {def}}{=}}}mathbb {P} ({mathcal {B}}_{k-1}^{x+1})} (так как ξ i {displaystyle xi _{i}} суть независимые одинаково распределённые случайные величины).

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

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


(2) Аналогично докажем, что P ( B k x ∣ S 1 x = x − 1 ) = P ( B k − 1 x + 1 ) {displaystyle 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 ; … ; x − 1 + x 2 + … + x k ) {displaystyle (x;x-1;x-1+x_{2};ldots {};x-1+x_{2}+ldots +x_{k})} из B k x ; x + 1 {displaystyle B_{k}^{x;x+1}} находится в однозначном соответствии с траекторией ( x − 1 ; x − 1 + x 2 ; … ; x − 1 + x 2 + … + x k ) {displaystyle (x-1;x-1+x_{2};ldots {};x-1+x_{2}+ldots +x_{k})} из B k − 1 x − 1 {displaystyle B_{k-1}^{x-1}} . Отсюда P ( { ( x − 1 ; x − 1 + x 2 ; … ; x − 1 + x 2 + … + x k ) ∈ B k − 1 x − 1 } ) = P ( { ( x − 1 ; x − 1 + x 1 ; … ; x − 1 + x 1 + … + x k − 1 ) ∈ B k − 1 x − 1 } ) = d e f P ( B k − 1 x − 1 ) . {displaystyle mathbb {P} {Bigl (}{igl {}(x-1;x-1+x_{2};ldots ;x-1+x_{2}+ldots +x_{k})in B_{k-1}^{x-1}{igr }}{Bigr )}=mathbb {P} {Bigl (}{igl {}(x-1;x-1+x_{1};ldots ;x-1+x_{1}+ldots +x_{k-1})in B_{k-1}^{x-1}{igr }}{Bigr )}{mathrel {stackrel { m {def}}{=}}}mathbb {P} ({mathcal {B}}_{k-1}^{x-1}).} ◼ {displaystyle lacksquare }

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

Из уравнения для β k ( x ) {displaystyle eta _{k}(x)} следует, что для x ∈ ( A ; B ) {displaystyle xin (A;B)} и k ⩽ n {displaystyle kleqslant n} верно:

P ( B k x ) = P ( B k x ∣ S 1 x = x + 1 ) ⋅ p + P ( B k x ∣ S 1 x = x − 1 ) ⋅ q = P ( B k − 1 x + 1 ) ⋅ p + P ( B k − 1 x − 1 ) ⋅ q = p β k − 1 ( x + 1 ) + q β k − 1 ( x − 1 ) . {displaystyle 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=peta _{k-1}(x+1)+qeta _{k-1}(x-1).}

β l ( B ) = 1 {displaystyle eta _{l}(B)=1} , β l ( A ) = 0 {displaystyle eta _{l}(A)=0} для l ∈ [ 0 ; n ] {displaystyle lin [0;n]} .


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


Также отметим, что B k − 1 ⊂ B k {displaystyle {mathcal {B}}_{k-1}subset {mathcal {B}}_{k}} , и поэтому β k − 1 ( x ) ⩽ β k ( x ) ⩽ 1 {displaystyle eta _{k-1}(x)leqslant eta _{k}(x)leqslant 1} для k ⩽ n {displaystyle kleqslant n} . Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг ( x j − 1 = ± 1 {displaystyle x_{j-1}=pm 1} ), на котором частица может прийти в точку ( j ; S j x ) {displaystyle (j;S_{j}^{x})} как из ( j − 1 ; S j x − 1 ) {displaystyle (j-1;S_{j}^{x}-1)} (для ξ j = 1 {displaystyle xi _{j}=1} ), так и из ( j − 1 ; S j x + 1 ) {displaystyle (j-1;S_{j}^{x}+1)} ( j ⩽ k {displaystyle jleqslant k} ).

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

При достаточно больших n {displaystyle n} вероятность β n ( x ) {displaystyle eta _{n}(x)} близка к β ( x ) {displaystyle eta (x)} — решению уравнения β ( x ) = p β ( x + 1 ) + q β ( x − 1 ) {displaystyle eta (x)=peta (x+1)+qeta (x-1)} при тех условиях, что β ( B ) = 1 {displaystyle eta (B)=1} (выход произошёл сразу же из точки B {displaystyle B} — конец игры, выиграл первый игрок), β ( A ) = 0 {displaystyle eta (A)=0} (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке A {displaystyle A} ). Эти условия следуют из того, что lim l → ∞ β l ( B ) = β ( B ) {displaystyle lim limits _{l ightarrow infty }eta _{l}(B)=eta (B)} . Это также будет доказано в этом разделе.

Сначала получим решение уравнения β ( x ) = p β ( x + 1 ) + q β ( x − 1 ) {displaystyle eta (x)=peta (x+1)+qeta (x-1)} . Пусть игра несправедливая ( p ≠ q {displaystyle p eq q} ). В таком случае найдём корни уравнения, то есть β ( x ) {displaystyle eta (x)} . Одно частное решение видно сразу: β ( x ) = c o n s t = a {displaystyle eta (x)=mathrm {const} =a} . Другое решение найдём, воспользовавшись тем, что β ( x ) {displaystyle eta (x)} — функция. Целесообразно употребить выражение с отношением q p {displaystyle {frac {q}{p}}} , учитывая, что p + q = 1 {displaystyle p+q=1} : ( q p ) x = q x ( p + q ) p x = q x p x − 1 + q x + 1 p x = p q x + 1 p x + 1 + q q x − 1 p x − 1 = p ( q p ) x + 1 + q ( q p ) x − 1 {displaystyle left({frac {q}{p}} ight)^{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}}}=pleft({frac {q}{p}} ight)^{x+1}+qleft({frac {q}{p}} ight)^{x-1}} . Отсюда правомерно предположить, что β ( x ) = b ⋅ ( q p ) x {displaystyle eta (x)=bcdot left({frac {q}{p}} ight)^{x}} . Добавление константы ничего не изменит благодаря тому, что p + q = 1 {displaystyle p+q=1} .

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

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

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


Решение

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

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

Рассмотрим вопрос о быстроте предельной сходимости α n ( x ) {displaystyle alpha _{n}(x)} и β n ( x ) {displaystyle eta _{n}(x)} к α ( x ) {displaystyle alpha (x)} и β ( x ) {displaystyle eta (x)} . Пусть блуждание начинается из начала координат ( x = 0 {displaystyle x=0} ). Для простоты обозначим α n ( 0 ) = α n {displaystyle alpha _{n}(0)=alpha _{n}} , β n ( 0 ) = β n {displaystyle eta _{n}(0)=eta _{n}} , γ n = 1 − α n − β n {displaystyle gamma _{n}=1-alpha _{n}-eta _{n}} . Иными словами, γ n {displaystyle gamma _{n}} — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: γ n = P { ω : A < S k < B ; 0 ⩽ k ⩽ n } {displaystyle gamma _{n}=mathbb {P} {omega colon A<S_{k}<B;0leqslant kleqslant n}} . ω {displaystyle omega } представляет собой событие ⋂ 0 ⩽ k ⩽ n { A < S k < B } {displaystyle igcap limits _{0leqslant kleqslant n}{A<S_{k}<B}} . Рассмотрим число n = r m {displaystyle n=rm} , где r , m ∈ Z {displaystyle r,min mathbb {Z} } , и цепочку случайных величин ζ n : ζ 1 = ∑ i = 1 m ξ i ,   ζ 2 = ∑ i = m + 1 2 m ξ i ,   … ,   ζ r = ∑ i = m ( r − 1 ) r m ξ i {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}} . Если обозначить совокупное богатство за C = | A | + B {displaystyle C=|A|+B} , то тогда { A < S k < B ; 1 ⩽ k ⩽ r m } ⊆ { | ζ 1 | < C ; … ; | ζ r | < C } {displaystyle {A<S_{k}<B;1leqslant kleqslant rm}subseteq {igl {}|zeta _{1}|<C;ldots {};|zeta _{r}|<C{igr }}} . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма m {displaystyle m} штук x i {displaystyle x_{i}} меньше, чем совокупный запас.

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

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


Решение

Докажем, что P ( { ζ 1 = m } ∩ { ζ 2 = m } ) = P ( { ζ 1 = m } ) ⋅ P ( { ζ 2 = m } ) . {displaystyle mathbb {P} {igl (}{zeta _{1}=m}cap {zeta _{2}=m}{igr )}=mathbb {P} {igl (}{zeta _{1}=m}{igr )}cdot mathbb {P} {igl (}{zeta _{2}=m}{igr )}.}


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

Из только что доказанного следует что γ n ⩽ P ( { | ζ 1 | ; … ; | ζ r | < C } ) = ∏ i = 1 r P ( { | ζ i | < C } ) = ( P ( { | ζ 1 | < C } ) ) r {displaystyle gamma _{n}leqslant mathbb {P} {Bigl (}{igl {}|zeta _{1}|;ldots ;|zeta _{r}|<C{igr }}{Bigr )}=prod limits _{i=1}^{r}mathbb {P} {Bigl (}{igl {}|zeta _{i}|<C{igr }}{Bigr )}={iggl (}mathbb {P} {Bigl (}{igl {}|zeta _{1}|<C{igr }}{Bigr )}{iggr )}^{r}} .

Рассмотрим дисперсию: V a r ( ζ 1 ) = m ( 1 − ( p − q ) 2 ) {displaystyle mathrm {Var} (zeta _{1})=m{igl (}1-(p-q)^{2}{igr )}} (что вполне правомерно, так как 1 − ( p − q ) 2 = 1 − ( ( p + q ) 2 − 4 p q ) {displaystyle 1-(p-q)^{2}=1-{igl (}(p+q)^{2}-4pq{igr )}} , а ξ {displaystyle xi } — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших m {displaystyle m} и 0 < p < 1 {displaystyle 0<p<1} верно: P ( { | ζ 1 | < C } ) ⩽ ε 1 {displaystyle mathbb {P} {Bigl (}{igl {}|zeta _{1}|<C{igr }}{Bigr )}leqslant varepsilon _{1}} , где ε 1 < 1 {displaystyle varepsilon _{1}<1} , так как если P ( { | ζ 1 | ⩽ C } ) = 1 {displaystyle mathbb {P} {Bigl (}{igl {}|zeta _{1}|leqslant C{igr }}{Bigr )}=1} , то V a r ( ζ 1 ) ⩽ C 2 {displaystyle mathrm {Var} (zeta _{1})leqslant C^{2}} . Если p = 0 {displaystyle p=0} или p = 1 {displaystyle p=1} , то для довольно больших m {displaystyle m} верно, что P ( { | ζ 1 | < C } ) = 0 {displaystyle mathbb {P} {Bigl (}{igl {}|zeta _{1}|<C{igr }}{Bigr )}=0} , поэтому неравенство P ( { | ζ 1 | < C } ) ⩽ ε 1 {displaystyle mathbb {P} {Bigl (}{igl {}|zeta _{1}|<C{igr }}{Bigr )}leqslant varepsilon _{1}} верно ∀ p ∈ [ 0 ; 1 ] {displaystyle forall pin [0;1]} . Из вышесказанного следует, что γ n ⩽ ε n {displaystyle gamma _{n}leqslant varepsilon ^{n}} , где ε = ε 1 1 m < 1 {displaystyle varepsilon =varepsilon _{1}^{frac {1}{m}}<1} . Так как α + β = 1 {displaystyle alpha +eta =1} , то ( α − α n ) − ( β − β n ) = γ n {displaystyle (alpha -alpha _{n})-(eta -eta _{n})=gamma _{n}} ; так как α ⩾ α n {displaystyle alpha geqslant alpha _{n}} и β ⩾ β n {displaystyle eta geqslant eta _{n}} , то 0 ⩽ α − α n ⩽ γ n ⩽ ε n {displaystyle 0leqslant alpha -alpha _{n}leqslant gamma _{n}leqslant varepsilon ^{n}} ; 0 ⩽ β − β n ⩽ γ n ⩽ ε n {displaystyle 0leqslant eta -eta _{n}leqslant gamma _{n}leqslant varepsilon ^{n}} при ε < 1 {displaystyle varepsilon <1} . Аналогичные оценки справедливы и для разностей α ( x ) − α n ( x ) {displaystyle alpha (x)-alpha _{n}(x)} и β ( x ) − β n ( x ) {displaystyle eta (x)-eta _{n}(x)} , так как можно свести эти разности к разностям α − α n {displaystyle alpha -alpha _{n}} и β − β n {displaystyle eta -eta _{n}} при A 1 = A − x {displaystyle A_{1}=A-x} , B 1 = B − x {displaystyle B_{1}=B-x} .

Вернёмся к рассмотрению α ( x ) {displaystyle alpha (x)} . По аналогии с решением ( q p ) x − ( q p ) A ( q p ) B − ( q p ) A {displaystyle {frac {left({frac {q}{p}} ight)^{x}-left({frac {q}{p}} ight)^{A}}{left({frac {q}{p}} ight)^{B}-left({frac {q}{p}} ight)^{A}}}} уравнения β ( x ) = p β ( x + 1 ) + q β ( x − 1 ) {displaystyle eta (x)=peta (x+1)+qeta (x-1)} , можно сказать, что у уравнения α ( x ) = p α ( x + 1 ) + q α ( x − 1 ) {displaystyle alpha (x)=palpha (x+1)+qalpha (x-1)} при граничных условиях α ( A ) = 1 {displaystyle alpha (A)=1} , α ( B ) = 0 {displaystyle alpha (B)=0} существует единственное решение α ( x ) = ( q p ) B − ( q p ) x ( q p ) B − ( q p ) A , A ⩽ x ⩽ B . {displaystyle alpha (x)={frac {left({frac {q}{p}} ight)^{B}-left({frac {q}{p}} ight)^{x}}{left({frac {q}{p}} ight)^{B}-left({frac {q}{p}} ight)^{A}}},qquad Aleqslant xleqslant B.}

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

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

Величины α ( x ) {displaystyle alpha (x)} и β ( x ) {displaystyle eta (x)} можно назвать вероятностями разорения первого и второго игрока при начальных капиталах x − A {displaystyle x-A} и B − x {displaystyle B-x} при стремлении количества ходов к бесконечности и характеризации случайной величина ξ i = + 1 {displaystyle xi _{i}=+1} как выигрыша первого игрока, а ξ i = − 1 {displaystyle xi _{i}=-1} — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.

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

β ( x ) = { x B , p = q = 0 , 5 , ( q p ) x − 1 ( q p ) B − 1 , p ≠ q {displaystyle eta (x)={egin{cases}{frac {x}{B}},&p=q=0{,}5,{frac {left({frac {q}{p}} ight)^{x}-1}{left({frac {q}{p}} ight)^{B}-1}},&p eq qend{cases}}} .

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

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

Его вероятность проигрыша задана формулой lim k → ∞ α k = α = ( q p ) B − 1 ( q p ) B − ( q p ) A {displaystyle lim limits _{k ightarrow infty }alpha _{k}=alpha ={frac {left({frac {q}{p}} ight)^{B}-1}{left({frac {q}{p}} ight)^{B}-left({frac {q}{p}} ight)^{A}}}} .


Теперь пусть первый игрок с капиталом ( − A ) {displaystyle (-A)} примет решение удвоить ставку и играть на два рубля, то есть P ( { ξ i = 2 } ) = p {displaystyle mathbb {P} {igl (}{xi _{i}=2}{igr )}=p} , P ( { ξ i = − 2 } ) = q {displaystyle mathbb {P} {igl (}{xi _{i}=-2}{igr )}=q} . Тогда обозначим предельную вероятность разорения первого игрока так: α 2 = ( q p ) 0 , 5 B − 1 ( q p ) 0 , 5 B − ( q p ) 0 , 5 A {displaystyle alpha _{2}={frac {left({frac {q}{p}} ight)^{0{,}5B}-1}{left({frac {q}{p}} ight)^{0{,}5B}-left({frac {q}{p}} ight)^{0{,}5A}}}} .

Поэтому α = ( q p ) 0 , 5 B ⋅ 2 − 1 2 ( q p ) 0 , 5 B ⋅ 2 − ( q p ) 0 , 5 A ⋅ 2 = ( ( q p ) 0 , 5 B − 1 ) ⋅ ( ( q p ) 0 , 5 B + 1 ) ( ( q p ) 0 , 5 B − ( q p ) 0 , 5 A ) ⋅ ( ( q p ) 0 , 5 B + ( q p ) 0 , 5 A ) = α 2 ⋅ ( ( q p ) 0 , 5 B + 1 ) ( ( q p ) 0 , 5 B + ( q p ) 0 , 5 A ) > α 2 {displaystyle alpha ={frac {left({frac {q}{p}} ight)^{0{,}5Bcdot 2}-1^{2}}{left({frac {q}{p}} ight)^{0{,}5Bcdot 2}-left({frac {q}{p}} ight)^{0{,}5Acdot 2}}}={frac {left(left({frac {q}{p}} ight)^{0{,}5B}-1 ight)cdot left(left({frac {q}{p}} ight)^{0{,}5B}+1 ight)}{left(left({frac {q}{p}} ight)^{0{,}5B}-left({frac {q}{p}} ight)^{0{,}5A} ight)cdot left(left({frac {q}{p}} ight)^{0{,}5B}+left({frac {q}{p}} ight)^{0{,}5A} ight)}}=alpha _{2}cdot {frac {left(left({frac {q}{p}} ight)^{0{,}5B}+1 ight)}{left(left({frac {q}{p}} ight)^{0{,}5B}+left({frac {q}{p}} ight)^{0{,}5A} ight)}}>alpha _{2}} , так как α 2 {displaystyle alpha _{2}} умножается на дробь, которая больше единицы при q > p {displaystyle q>p} .


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

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

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

Для x ∈ ( A ; B ) {displaystyle xin (A;B)} и k ∈ [ 0 ; n ] {displaystyle kin [0;n]} мы получили рекуррентное соотношение для функции m k ( x ) {displaystyle m_{k}(x)} : m k ( x ) = p m k − 1 ( x + 1 ) + q m k − 1 ( x − 1 ) + 1 {displaystyle m_{k}(x)=pm_{k-1}(x+1)+qm_{k-1}(x-1)+1} при m 0 ( x ) = 0 {displaystyle m_{0}(x)=0} .


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


Из рекуррентного соотношения и граничных условий можно один за другим вычислить m i ( x ) {displaystyle m_{i}(x)} . Так как m k + 1 ( x ) ⩾ m k ( x ) {displaystyle m_{k+1}(x)geqslant m_{k}(x)} , то существует предел m ( x ) = lim n → ∞ m n ( x ) {displaystyle m(x)=lim limits _{n ightarrow infty }m_{n}(x)} , который удовлетворяет соотношению m k ( x ) = p m k − 1 ( x + 1 ) + q m k − 1 ( x − 1 ) + 1 {displaystyle m_{k}(x)=pm_{k-1}(x+1)+qm_{k-1}(x-1)+1} : m ( x ) = 1 + p m ( x + 1 ) + q m ( x − 1 ) {displaystyle m(x)=1+pm(x+1)+qm(x-1)} при выполнении m ( A ) = m ( B ) = 0 {displaystyle m(A)=m(B)=0} . Данные переходы аналогичны тем, что мы рассмотрели при переходе к n → ∞ {displaystyle n ightarrow infty } в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть m ( x ) < ∞ {displaystyle m(x)<infty } , x ∈ ( A ; B ) {displaystyle xin (A;B)} .


Решим данное уравнение. В уравнении вероятности проигрыша ( p ≠ q {displaystyle p eq q} ) уже были получены частные решения a {displaystyle a} и b ( q p ) x {displaystyle bleft({frac {q}{p}} ight)^{x}} . Здесь же появляется ещё один претендент на роль частного решения: x q − p = q − p + ( p + q ) x + p − q q − p = q − p q − p + p ( x + 1 ) q − p + q ( x − 1 ) q − p = 1 + p x + 1 q − p + q x − 1 q − p {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}}} , поэтому m ( x ) = x q − p + a + b ( q p ) x {displaystyle m(x)={frac {x}{q-p}}+a+bleft({frac {q}{p}} ight)^{x}} . С учётом граничного условия m ( A ) = m ( B ) = 0 {displaystyle m(A)=m(B)=0} находим при помощи ранее полученных соотношений m ( x ) {displaystyle m(x)} : m ( x ) = 1 p − q ( B β ( x ) + A α ( x ) − x ) {displaystyle m(x)={frac {1}{p-q}}{igl (}Beta (x)+Aalpha (x)-x{igr )}} . В случае идеальной монетки получаем следующее выражение: m ( x ) = a + b x − x 2 {displaystyle m(x)=a+bx-x^{2}} . Применение граничного условия даёт: m ( x ) = ( B − x ) ( x − A ) {displaystyle m(x)=(B-x)(x-A)} . Из этого следует, что в случае равных стартовых капиталов m ( 0 ) = B 2 {displaystyle m(0)=B^{2}} . Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.

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

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

Доказать, что m ( x ) < ∞ ∀ A , B {displaystyle m(x)<infty quad forall A,B} .


Решение

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

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

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


Для доказательства первого равенства напишем: E ( S τ n ) = ∑ k = 0 n E ( S k 1 { τ n = k } ( ω ) ) = ∑ k = 0 n E ( S n 1 { τ n = k } ( ω ) ) + ∑ k = 0 n ( ( S k − S n ) 1 { τ n = k } ( ω ) ) = E ( S n ) + ∑ k = 0 n ( ( S k − S n ) 1 { τ n = k } ( ω ) ) {displaystyle mathbb {E} (S_{ au _{n}})=sum limits _{k=0}^{n}mathbb {E} {igl (}S_{k}mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}=sum limits _{k=0}^{n}mathbb {E} {igl (}S_{n}mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}+sum limits _{k=0}^{n}{igl (}(S_{k}-S_{n})mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}=mathbb {E} (S_{n})+sum limits _{k=0}^{n}{igl (}(S_{k}-S_{n})mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}} . Совершенно очевидно, что E ( S n ) = 0 {displaystyle mathbb {E} (S_{n})=0} , так как S n = ξ 1 + … + ξ n {displaystyle S_{n}=xi _{1}+ldots +xi _{n}} , ξ i = ± 1 {displaystyle xi _{i}=pm 1} при p = q {displaystyle p=q} . Осталось доказать, что ∑ k = 0 n ( ( S k − S n ) 1 { τ n = k } ( ω ) ) = 0 {displaystyle sum limits _{k=0}^{n}{igl (}(S_{k}-S_{n})mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}=0} .

Для 0 ⩽ k < n {displaystyle 0leqslant k<n} справедливо, что { τ n > k } = { A < S 1 < B ; … ; A < S k < B } {displaystyle { au _{n}>k}={A<S_{1}<B;ldots ;A<S_{k}<B}} . Последнее событие может быть представлено в виде { ω : ( ξ 1 ; … ; ξ n ) ∈ J } {displaystyle {igl {}omega colon (xi _{1};ldots ;xi _{n})in J{igr }}} , где J {displaystyle J} — некоторое подмножество множества { − 1 ; + 1 } k {displaystyle {-1;+1}^{k}} . Это множество определяется только ξ i {displaystyle xi _{i}} при i = 1 ; k ¯ {displaystyle i={overline {1;k}}} . Для больших i {displaystyle i} значения ξ k + 1 ; … ; ξ n {displaystyle xi _{k+1};ldots ;xi _{n}} не влияют на J {displaystyle J} . Множество вида { τ n = k } = { τ n > k − 1 } ∖ { τ n > k } {displaystyle { au _{n}=k}={ au _{n}>k-1}ackslash { au _{n}>k}} также может быть представлено в виде { ω : ( ξ 1 ; … ; ξ n ) ∈ J } {displaystyle {igl {}omega colon (xi _{1};ldots ;xi _{n})in J{igr }}} . Благодаря независимости ξ i {displaystyle xi _{i}} (доказано в подзадаче 2) вытекает, что ∀ 0 ⩽ k < n {displaystyle forall 0leqslant k<n} случайные величины S n − S k {displaystyle S_{n}-S_{k}} и 1 { τ n = k } {displaystyle mathbf {1} _{{ au _{n}=k}}} независимы. Отсюда E ( S k ⋅ 1 { τ n = k } ( ω ) ) = E ( S k ) ⋅ E ( 1 { τ n = k } ( ω ) ) = 0 {displaystyle mathbb {E} {igl (}S_{k}cdot mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}=mathbb {E} (S_{k})cdot mathbb {E} {igl (}mathbf {1} _{{{ au _{n}=k}}}(omega ){igr )}=0} в силу того, что первый множитель нулевой.

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

В случае же p ≠ q {displaystyle p eq q} имеют место соотношения E ( S τ n ) = ( p − q ) E ( τ n ) {displaystyle mathbb {E} (S_{ au _{n}})=(p-q)mathbb {E} ( au _{n})} (поскольку E ( ξ 1 ) = p − q {displaystyle mathbb {E} (xi _{1})=p-q} ) и E ( ( S τ n − τ n E ( ξ 1 ) ) 2 ) = V a r ( ξ 1 ) ⋅ E ( τ n ) {displaystyle mathbb {E} {Bigl (}{igl (}S_{ au _{n}}- au _{n}mathbb {E} (xi _{1}){igr )}^{2}{Bigr )}=mathrm {Var} (xi _{1})cdot mathbb {E} ( au _{n})} , поскольку V a r ( ξ 1 ) = 1 − ( p − q ) 2 {displaystyle mathrm {Var} (xi _{1})=1-(p-q)^{2}} . Теперь покажем, что lim n → ∞ m n ( 0 ) = m ( 0 ) < ∞ {displaystyle lim limits _{n ightarrow infty }m_{n}(0)=m(0)<infty } .

В случае справедливой игры в силу соотношения E ( S τ n 2 ) = E ( τ n ) {displaystyle mathbb {E} (S_{ au _{n}}^{2})=mathbb {E} ( au _{n})} верно, что E ( τ n ) ⩽ max { A 2 ; B 2 } {displaystyle mathbb {E} ( au _{n})leqslant max{A^{2};B^{2}}} . Тогда же E ( τ n ) = E ( S τ n 2 ) = A 2 α n + B 2 β n + E ( S n 2 1 { A < S n < B } ) 1 { τ n = n } {displaystyle mathbb {E} ( au _{n})=mathbb {E} (S_{ au _{n}}^{2})=A^{2}alpha _{n}+B^{2}eta _{n}+mathbb {E} (S_{n}^{2}mathbf {1} _{{{A<S_{n}<B}}})mathbf {1} _{{{ au _{n}=n}}}} , поэтому A 2 α n + B 2 β n ⩽ E ( τ n ) ⩽ A 2 α n + B 2 β n + max { A 2 ; B 2 } ⋅ γ n {displaystyle A^{2}alpha _{n}+B^{2}eta _{n}leqslant mathbb {E} ( au _{n})leqslant A^{2}alpha _{n}+B^{2}eta _{n}+max{A^{2};B^{2}}cdot gamma _{n}} . Из неравенства γ n < ε n {displaystyle gamma _{n}<varepsilon ^{n}} следует, что математическое ожидание E ( τ n ) {displaystyle mathbb {E} ( au _{n})} сходится при n → ∞ {displaystyle n ightarrow infty } к предельному значению m ( 0 ) = A 2 α + B 2 β = A 2 ⋅ B B − A − B 2 ⋅ A B − A = | A B | {displaystyle m(0)=A^{2}alpha +B^{2}eta =A^{2}cdot {frac {B}{B-A}}-B^{2}cdot {frac {A}{B-A}}=|AB|} . В случае несправедливой игры E ( τ n ) ⩽ max { | A | ; B } | p − q | {displaystyle mathbb {E} ( au _{n})leqslant {frac {max{|A|;B}}{|p-q|}}} . Так как за τ n {displaystyle au _{n}} обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии E ( τ n ) → m ( 0 ) = α A + β B p − q {displaystyle mathbb {E} ( au _{n}) ightarrow m(0)={frac {alpha A+eta B}{p-q}}} . ◼ {displaystyle lacksquare }

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

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

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

Последовательность ξ {displaystyle 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 {displaystyle S_{k}} сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений n {displaystyle n} , q {displaystyle q} и x {displaystyle 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

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

Визуализация (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

Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах ( A ; B ; n ; q ) {displaystyle (A;B;n;q)} . Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока ( β ( x ) {displaystyle eta (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 {displaystyle n} не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших n {displaystyle n} вероятность β n ( x ) {displaystyle eta _{n}(x)} близка к β ( x ) {displaystyle eta (x)} ».

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

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

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


Имя:*
E-Mail:
Комментарий: