logo

ギャンブラーの破産問題 📂確率論

ギャンブラーの破産問題

問題

20190213\_101451.png

ギャンブラーの破産問題は、二人のプレイヤーが限られたお金を賭け、どちらかが破産するまで繰り返されるゲームを想定したランダムウォークの一種だ。

君がプレイヤーの一人だとすると、上の図のように、勝つ確率がpp、負ける確率が(1−p)(1-p)だと言える。状態00は君が破産した場合、状態NNは相手のお金を全部取り、これ以上ゲームを繰り返さない場合だ。これは00とNNで自分自身に移る確率が11であることを意味している。iiはゲームを始めるときの君の所持金と見ることができる。

基本的にp≠12\displaystyle p \ne {{1} \over {2}}またはi≠N2\displaystyle i \ne {{N} \over {2}}であれば、ゲームは公平ではない。このゲームは一方が破産するまで終わらないが、「君がiiだけのお金を持って始めた場合、相手を破産させて勝つ確率はどれくらいか」というのが数学的に興味深い質問になる。ただ、その前に「なぜこんな不公平で極端なゲームをするのか」という質問ができる。

しかし、これはギャンブラーの破産問題を単にゲームとして見た場合に出せる質問に過ぎず、現実では公平な戦いを見つけることの方がより難しい。これは多額の資本を持つ大企業と法の保護を受ける小規模企業の闘いと見ることもできるし、同じ資源を生産する国同士の総力戦と見ることもできる。不利な戦いでもしなくてはならないときがあり、そのときの勝率が気になるのは当然のことだ。

数学に戻って、私たちの関心事は「初期資本がiiで、勝率がppの場合、相手を破産させ、全てのお金を持ち去る確率」PiP_{i}を計算することだ。「相手を破産させ、全てのお金を持ち去る状況」を便宜上「勝利」と呼ぼう。

解決策

PiP_{i}の定義から、P0=0P_{0} = 0であり、PN=1P_{N} = 1である。

パート1.

PiP_{ i }は、ppの確率で最初のゲームに勝利し、(i+1)( i+1 )から新たに始めて勝利する確率と、(1−p)(1-p)の確率で最初のゲームに負け、(i−1)( i-1 )から新たに始めて勝利する確率を足したものだと見ることができる。式で表すとPi=pPi+1+(1−p)Pi−1P_{ i } = p P_{ i + 1 } + (1 - p ) P_{ i - 1 }になる。左辺をppと(1−p)(1-p)に分けると Pi=(p+1−p)Pi=pPi+(1−p)PiP_{ i } = (p + 1 - p ) P_{i} = p P_{i} + (1 - p) P_{i} ゆえに Pi=pPi+1+(1−p)Pi−1  ⟹  pPi+(1−p)Pi=pPi+1+(1−p)Pi−1  ⟹  p(Pi+1−Pi)=(1−p)(Pi−Pi−1)  ⟹  (Pi+1−Pi)=1−pp(Pi−Pi−1) \begin{align*} & P_{ i } =& p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p P_{i} + (1 - p) P_{i} &= p P_{ i + 1 } + (1 - p ) P_{ i - 1 } \\ \implies& p \left( P_{i+1} - P_{i} \right) =& (1 - p) \left( P_{i} - P_{i-1} \right) \\ \implies& \left( P_{i+1} - P_{i} \right) =& {{1-p} \over {p}} \left( P_{i} - P_{i-1} \right) \end{align*}

再帰的に解いていくとPi−Pi−1=(1−pp)i−1(P1−P0)\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} \left( P_{1} - P_{0} \right)だが、P0=0P_{0} = 0であるため Pi−Pi−1=(1−pp)i−1P1\displaystyle P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}

パート2.

P1−P0=(1−pp)0P1P2−P1=(1−pp)1P1P3−P2=(1−pp)2P1Pi−Pi−1=(1−pp)i−1P1P_{1} - P_{0} = \left( {{1-p} \over {p}} \right)^{0} P_{1} \\ P_{2} - P_{1} = \left( {{1-p} \over {p}} \right)^{1} P_{1} \\ P_{3} - P_{2} = \left( {{1-p} \over {p}} \right)^{2} P_{1} \\ P_{i} - P_{i-1} = \left( {{1-p} \over {p}} \right)^{i-1} P_{1}

各辺の式を足すと、左辺は (P1−P0)+(P2−P1)+⋯+(Pi−Pi−1)=Pi−P0=Pi( P_{1} - P_{0} ) + ( P_{2} - P_{1} ) + \cdots + ( P_{i} - P_{i-1} ) = P_{i} - P_{0} = P_{i} 右辺は ∑k=1i(1−pp)k−1P1=1−(1−pp)i1−(1−pp)P1\displaystyle \sum_{k=1}^{i} \left( {{1-p} \over {p}} \right)^{k-1} P_{1} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} 整理すると Pi=1−(1−pp)i1−(1−pp)P1\displaystyle P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1}

パート3.

PN=1P_{N} = 1であるため 1=PN=1−(1−pp)N1−(1−pp)P1 1 = P_{N} = {{ 1 - \left( {{1-p} \over {p}} \right)^{N} } \over {1 - \left( {{1-p} \over {p}} \right) }} P_{1} したがって P1=1−(1−pp)1−(1−pp)N P_{1} = {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} パート2.で得た式にP1P_{1}を代入することにより Pi=1−(1−pp)i1−(1−pp)⋅1−(1−pp)1−(1−pp)N=1−(1−pp)i1−(1−pp)N P_{i} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right) }} \cdot {{1 - \left( {{1-p} \over {p}} \right) } \over { 1 - \left( {{1-p} \over {p}} \right)^{N} }} = {{ 1 - \left( {{1-p} \over {p}} \right)^{i} } \over {1 - \left( {{1-p} \over {p}} \right)^{N} }} を得る。

■