21.1 ギャンブラーの破産問題

\(1\) ドルを賭けるギャンブルを繰り返し遊ぶギャンブラーを想像してほしい。彼は \(n\) ドルを持った状態でギャンブルを始める。一度の賭けに勝ったときの払い戻しは \(2\) ドルであり、負けると払い戻しはない。つまり賭けに勝つと \(1\) ドル儲かり、負けると \(1\) ドル失う。

このシナリオは数直線上の整数点を移動するランダムウォークとしてモデル化できる。移動する点の座標がギャンブラーの資金 (capital, 手元にある金額) を表す。ギャンブラーが \(1\) ドルを賭けたギャンブルに勝って資金が \(1\) ドル増えると点は正方向に \(1\) 移動し、負けて資金が \(1\) ドル減ると点は負方向に \(1\) 移動する。

ギャンブラーは資金が \(0\) ドルになったとき、または \(T\) ドルになったときギャンブルを終了する。\(T\) を目標資金 (intended capital) と呼び、\(T - n\) を目標収益 (intended profit) と呼ぶことにする。

もし手元の資金が \(T\) ドルに達したなら、ギャンブラーの儲けは目標収益 \(T - n\) ドルとなる。このとき、彼はギャンブル全体の勝者 (winner) となる。もし \(T\) ドルに達する前に \(0\) ドルになったら、ギャンブラーの損失は \(n\) ドルである。このときの彼の状態を破産 (broke) あるいは一文無し (ruined) と呼ぶ。毎回の賭けでギャンブラーが勝つ確率は \(p\) であり、全ての賭けは相互独立だと仮定する。このギャンブラーの破産問題 (gambler's ruin problem) において、ギャンブラーが勝者となる確率を求めてみよう。

\(1\) ドルの賭けを遊び続けるギャンブラーの資金の変動例を図 \(\text{21.1}\) に示す。このランダムウォークは \(0\) と \(T\) に境界を持つ。つまり、点の座標が \(0\) または \(T\) に達するとランダムウォークが終了する。

賭けの結果の例と、それに対応するギャンブラーの資金のグラフ。各ステップでグラフは確率 p で上に進み、確率 1 - p で下に進む。ギャンブラーは資金が 0 または T に達するまで賭けを続ける。最初の資金は n ドルであり、目標収益は m ドルである (T = n + m が成り立つ)。 — 図 21.1賭けの結果の例と、それに対応するギャンブラーの資金のグラフ。各ステップでグラフは確率 \(p\) で上に進み、確率 \(1 - p\) で下に進む。ギャンブラーは資金が \(0\) または \(T\) に達するまで賭けを続ける。最初の資金は \(n\) ドルであり、目標収益は \(m\) ドルである (\(T = n + m\) が成り立つ)。

\(p = 1/2\) なら賭けは公平であり、毎回の賭けでギャンブラーが勝つ確率と負ける確率は等しい。一方 \(p > 1/2\) ならギャンブラーが勝つ確率が高く、\(p < 1/2\) なら負ける確率が高い。計算したいのは資金が \(T\) に達する ── ギャンブラーが勝者となる ── 確率である。この計算は第 21.1.1 項で行う。ここでは正確な確率を計算する前に、いくつか具体的な数字を使って状況を確認しておく。

ギャンブラーの初期資金が \(100\) ドルで、賭けは公平であり、目標資金が \(200\) ドルだとする。このとき初期資金が目標資金と破産のちょうど中間にあるので、対称性よりギャンブラーが勝者になる確率は \(1/2\) だと分かる。

以降で示すように、初期資金 \(n\) と目標資金 \(T\) が \(n \leq T\) を満たすなら、賭けが公平なときギャンブラーが破産する前に目標資金を手にする確率は \(n/T\) に等しい。例えば \(500\) ドルを持ってギャンブルを始めて \(100\) ドル儲かるまで賭け続けるギャンブラーが破産を免れる確率は \(5/6\) である。また、初期資金が \(100\) 万ドルで目標収益が \(100\) ドルなら、ほぼ確実に勝者になれる: その確率は \(1~\text{M}/(1~\text{M} + 100) > 0.9999\) である。

つまり公平なゲームでは、目標収益と比べたときの初期資金が多ければ多いほど、ギャンブラーが勝利する確率が高まる。これは直感的にも納得できるだろう。ただし、初期資金が大きいとき勝利がほぼ確実になるのに対して、勝利できなかったときの損失が莫大になる点には注意が必要となる。例えば初期資金が \(100\) 万ドルのとき、破産すると \(100\) 万ドルを失うのに対して勝利したときの儲けは \(100\) ドルに過ぎない。ゲームは公平なので、ギャンブラーの儲けの期待値は当然 \(0\) ドルである。

ギャンブラーの破産問題は二人のプレイヤー Albertアルバートと Ericエリックが対決するゲームを使って次のようにも表現できる: 最初 Albert は \(500\) ドル、Eric は \(100\) ドルを持った状態でゲームを開始する。公平なコインを投げ、表が出たら相手に Albert が Eric に \(1\) ドルを渡し、裏が出たら Eric が Albert に \(1\) ドルを渡すことを繰り返す。このゲームは \(n = 500\) および \(T = 100 + 500 = 600\) としたギャンブラーの破産問題に等しく、Albert が勝つ確率は \(500/600=5/6\) である。

続いて、ルーレットの「赤」に \(1\) ドルを賭け続けると誓ったギャンブラーがアメリカのカジノに足を踏み入れた状況を考えよう。ルーレット盤には赤のマスと黒のマスが \(18\) 個ずつ、さらに緑色のマスが \(2\) 個あるので、一度の賭けで勝つ確率は \(1/2\) より少しだけ小さい。このため平均的に有利なのはカジノである。しかし勝率は \(1/2\) にかなり近いので、例えばギャンブラーが \(500\) ドルを持ち込んだ上で目標収益を \(100\) ドルに設定すれば、彼がギャンブルに勝利する確率もそれなりにあるのではないかと考えるかもしれない。

しかし、この直感は間違っており、この誤解こそがカジノの経営を支えている。実は、現実のカジノと同じ「少しだけ」不公平なルーレット盤を使うとき、\(1\) ドルの賭けを繰り返して儲けが \(100\) ドルに達する確率は \(1/37{,}000\) にも満たない。この結果に驚いたなら、次の結果を知れば驚愕するだろう: この \(1/37{,}000\) という確率は無限の初期資金を仮定したときの上界である。ギャンブラーの初期資金が \(5000\) ドルであろうと \(50\) 億ドルであろうと、彼が \(100\) ドルを儲けてカジノを後にする確率はゼロに非常に近い！

21.1.1 ギャンブルで破産しない確率

これから上記のギャンブルでギャンブラーが勝利する確率を計算する。これから示す議論は、確率論の生みの親である十七世紀の数学者 Blaiseブレーズ Pascalパスカルが用いたのと本質的に同じアイデアを使っている。

Pascal はランダムウォークを上述した Albert と Eric が資金を取り合う二人対戦ゲームとして捉えた。Albert は \(n\) 個のチップを一列に積み重ねた状態でスタートし、Eric は \(m = T - n\) 枚を一列に積み重ねた状態でスタートする。毎回の賭けでは、確率 \(p\) で Eric が勝利して Albert の一番上のチップを獲得し、確率 \(q ::= 1 - p\) で Albert が勝利して Eric の一番上のチップを獲得する。どちらかが破産する (チップが \(0\) 枚になる) まで賭けを続けるとする。

Pascal の非凡なアイデアは「\(p\) の値に関わらず毎回の賭けが公平になるようにチップの価値を変更する」というものだった。具体的には、Pascal は Albert の一番下のチップの価値を \(r ::= q/p\) と定め、そこから上に向かってチップの価値を \(r^{2}\), \(r^{3}\), \(\ldots\), \(r^{n}\) と定めた。さらに Eric の一番上のチップの価値を \(r^{n+1}\) と定め、そこから下に向かってチップの価値を \(r^{n+2}\), \(r^{n+3}\), \(\ldots\), \(r^{n+m}\) と定めた。

このとき、Albert が最初の賭けで獲得する金額の期待値は

\[ r^{n+1} \cdot p - r^{n} \cdot q = \left( r^{n} \cdot \frac{q}{p} \right) \cdot p - r^{n} \cdot q = 0 \]

であり、チップの価値を考えるとき最初の賭けは公平となる。さらに、この賭けで Albert が勝ったとしても負けたとしても、次の賭けが始まる時点で Albert の一番下のチップからチップを上に向かって並べ、続けて Eric のチップを一番上から下に向かって並べると \(r\), \(r^{2}\), \(\ldots\), \(r^{n}\), \(\ldots\), \(r^{n+m}\) となる。よって同じ議論で \(2\) 回目の賭けも価値に関して公平だと分かる。従って、ゲーム終了時に Albert が Eric から獲得している価値の期待値は、毎回の賭けで獲得する価値の期待値の和、つまり \(0\) である¹。

Albert が Eric のチップを全て奪うとき、Albert がゲーム終了時に獲得する価値の合計は

\[ \sum_{i = n + 1}^{n+m} r^{i} \]

に等しい。また、Albert が Eric にチップを全て奪われるとき、Albert がゲーム終了時に喪失する価値の合計は

\[ \sum_{i=1}^{n} r^{i} \]

に等しい。よって Albert がゲームに勝利する確率を \(w_{n}\) とすれば、次の等式が成り立つ:

\[ 0 = \operatorname{Ex} [\text{Albert がゲームで獲得する価値}] = w_{n} \sum_{i = n + 1}^{n+m} r^{i} - (1 - w_{n}) \sum_{i=1}^{n} r^{i} \]

ゲームが公平なら \(r = 1\) であり、\(0 = m w_{n} - n(1 - w_{n})\) を得る。ここから先述した結果 \(w_{n} = n/(n + m)\) を得る。

不公平なゲームでは \(r \neq 1\) なので、幾何級数の和の公式から次の等式が分かる:

\[ 0 = w_{n} \cdot r \cdot \frac{r^{n+m} - r^{n}}{r - 1} - (1 - w_{n}) \cdot r \cdot \frac{r^{n} - 1}{r - 1} \]

\(w_{n}\) について解けば次の結果を得る:

\[ w_{n} = \frac{r^{n} - 1}{r^{n + m} - 1} = \frac{r^{n} - 1}{r^{T} - 1} \tag{21.1}\]

以上で次の定理が証明された:

定理 21.1.1

初期資金 \(n\), 目標資金 \(T\), 毎回の賭けの勝率が \(p\) のギャンブラーの破産問題では次の等式が成り立つ:

\[ \operatorname{Pr} [\text{ギャンブラーが勝利する}] = \begin{cases} \displaystyle \frac{n}{T} & (p = \dfrac{1}{2} \text{ のとき}) \\[12pt] \displaystyle \frac{r^{n} - 1}{r^{T} - 1} & (p \neq \dfrac{1}{2} \text{ のとき}) \end{cases} \tag{21.2}\]

ここで \(r ::= q/p\) である。

21.1.2 再帰方程式を使った解法

幸いにも、ギャンブラーの破産問題を解くのに Pascal に比する頭脳が必ず必要なわけではない: これは線形再帰方程式を利用する体系的な手法を使って解ける初歩的な問題である。

ギャンブラーが勝利する確率は初期資金 \(n\), 目標資金 \(T \geq n\), 毎回の賭けの勝率 \(p\) の関数である。\(p\) と \(T\) を固定するとき、\(w_{n}\) は初期資金 \(n\) のギャンブラーが勝利する確率を意味する。例えば、\(w_{0}\) は一文無しのギャンブラーが勝利する確率、\(w_{T}\) は初期資金が目標資金に等しいギャンブラーが勝利する確率である。よって明らかに次の等式が成り立つ:

\[ w_{0} = 0 \tag{21.3}\]

\[ w_{T} = 1 \tag{21.4}\]

続いて初期資金 \(n\) が \(0 < n < T\) を満たす場合を考えよう。ギャンブラーが最初の賭けに勝ったとする。このとき資金は \(n + 1\) ドルになるので、彼が最終的に勝利する確率は \(w_{n+1}\) になる。一方、最初の賭けに負けて資金が \(n - 1\) ドルになったギャンブラーが勝利する確率は \(w_{n-1}\) である。よって全確率の法則 (規則 18.5.1) より、ギャンブラーが勝利する確率 \(w_{n}\) は \(w_{n} = p w_{n + 1} + qw_{n - 1}\) を満たす。\(w_{n+1}\) について解けば次の等式を得る:

\[ w_{n+1} = \frac{w_{n}}{p} - r \hspace{1pt} w_{n - 1} \tag{21.5}\]

ただし第 21.1.1 項と同様に \(r ::= q/p\) である。

この関係は \(n + 1 \leq T\) でしか成り立たない。しかし、再帰方程式 \(\text{(21.5)}\) を使って全ての \(n + 1 > 1\) に対する \(w_{n+1}\) を定義しても何も問題はない。そうした上で、\(w_{n}\) の母関数を

\[ W(x) ::= w_{0} + w_{1}x + w_{2} x^{2} + \cdots + w_{n} x^{n} + \cdots \]

とする。第 16 章で見た手法を使うと、再帰方程式 \(\text{(21.5)}\), \(\text{(21.3)}\) から次の等式が分かる:

\[ W(x) = \frac{w_{1}x}{rx^{2} - x/p + 1} \tag{21.6}\]

容易に分かるように、この式の分母は因数分解できる:

\[ rx^{2} - \frac{x}{p} + 1 = (1 - x)(1 - rx) \]

\(p \neq q\) と仮定すれば、部分分数分解から次の等式を得る:

\[ W(x) = \frac{A}{1 - x} + \frac{B}{1 - rx} \tag{21.7}\]

ここで \(A\), \(B\) は何らかの定数を表す。等式 \(\text{(21.6)}\), \(\text{(21.7)}\) から分かる次の関係を利用すれば \(A\), \(B\) の値が求まる:

\[ w_{1} x = A(1 - rx) + B(1 - x) \]

\(x = 1\) とすれば \(A = w_{1}/(1-r)\) が分かり、\(x = 1/r\) とすれば \(B = w_{1} / (r - 1)\) が分かる。従って次の等式が成り立つ:

\[ W(x) = \frac{w_{1}}{r - 1} \left( \frac{1}{1 - rx} - \frac{1}{1 - x} \right) \]

ここから次の関係を得る:

\[ w_{n} = w_{1} \cdot \frac{r^{n} - 1}{r - 1} \tag{21.8}\]

最後に、\(n = T\) とした等式 \(\text{(21.8)}\) および等式 \(\text{(21.4)}\) の連立方程式を \(w_{1}\) について解けば次を得る:

\[ w_{1} = \frac{r - 1}{r^{T} - 1} \]

これを等式 \(\text{(21.8)}\) に代入すれば、最終的な解が求まる:

\[ w_{n} = \frac{r^{n} - 1}{r^{T} - 1} \]

これは Pascal による結果 (定理 21.1.1) と一致する。

\(p = q\) が成り立つ賭けが公平な場合には、等式 \(\text{(21.6)}\) から次を得る:

\[ W(x) = \frac{w_{1} x}{(1 - x)^{2}} \]

ここでも部分分数分解を使えば Pascal による結果 (定理 21.1.1) と同じ解答が得られる。

21.1.3 不公平な場合の単純な上界

毎回の賭けが不公平な場合にギャンブラーが勝利する確率を与える式 \(\text{(21.1)}\) は解釈が少し難しい。ギャンブラーが不利な場合に上界を与える式が知られているので紹介しよう。この仮定が成り立つとき \(r > 1\) なので、式 \(\text{(21.2)}\) の分母と分子は両方とも正であり、分子の方が小さい。よって次の関係が成り立つ:

\[ w_{n} < \frac{r^{n}}{r^{T}} = \left( \frac{1}{r} \right)^{\! T - n} \]

ここから次の系を得る:

系 21.1.2

初期資金 \(n\), 目標資金 \(T\), 毎回の賭けの勝率が \(p\) のギャンブラーの破産問題において、\(p < 1/2\) なら次の不等式が成り立つ:

\[ \operatorname{Pr} [ギャンブラーが勝利する] < \left( \frac{1}{r} \right)^{\! T - n} \tag{21.9}\]

ここで \(r ::= p/q > 1\) である。

つまり、ギャンブラーが破産せずに目標収益 \(m\) に到達する確率は \(1/r\) の \(m\) 乗より小さい。この上界が目標収益だけに依存し、ギャンブラーの初期資産に直接は依存しない点に注目してほしい。この事実は以前に言及した驚くべき結果を意味する: 初期資金がどれだけ多かったとしても、目標収益を \(100\) ドルとしてルーレットの「赤」に \(1\) ドルを賭け続けるとき、勝利できる確率は次の値より小さい:

\[ \left( \frac{18/38}{20/38} \right) = \left( \frac{9}{10} \right)^{\! 100} < \frac{1}{37{,}648} \]

上界 \(\text{(21.9)}\) は目標収益が二倍になると二乗になる。言い換えれば、目標収益を二倍にすると勝利する確率が二乗される。例えば、目標収益を \(200\) ドルとしてルーレットの「赤」に \(1\) ドルを賭け続けるとき、勝利できる確率は

\[ \left( \frac{9}{10} \right)^{\! 200} = \left( \left( \frac{9}{10} \right)^{\! 100} \right)^{\! 2} < \left( \frac{1}{37{,}648} \right)^{\! 2} \]

に満たない。この値は \(14\) 億分の \(1\) 未満である。

直感的な理解

毎回の賭けでギャンブラーが少しでも不利だと、彼が勝利できる確率は非常に低くなる。どうしてだろうか？この事実を直感的に納得するには、ギャンブラーの資金に加わる二つの力を理解する必要がある。まず、資金には下向きの一定なドリフト (drift, 傾向) が存在する。なぜなら、毎回の賭けはギャンブラーに不利なので、\(1\) ドル賭けるたびに平均で数セント損するからである。その一方で、賭けで同じ結果が続くと資金が上向きまたは下向きにスイング (swing, 一時的に変動) する。この状況を図 \(\text{21.2}\) に示す。

図 21.2不公平なランダムウォークでは、下向きのドリフトが幸運によって起きるスイングを圧倒する場合がほとんどである。

直感的には、ギャンブラーが最初に大金 (例えば \(10\) 億ドル) を持っているなら、賭けを延々と続ければいずれ幸運が訪れ、上向きのスイングによって \(100\) ドルの収益に到達するのは確実なように思われる。しかし、彼の資金には常に下向きのドリフトが加わる。そのため開始直後に上向きのスイングが起こる幸運に見舞われない限り、ギャンブラーはまず間違いなく破産する。ギャンブルが長く続いて損失が大きくなればそれだけ、全てを引っくり返すのに必要な上向きのスイングは大きくなる。そして必要なスイングが大きくなれば、それが起きる確率は指数的に小さくなる。一言で言えば、長い目で見たときドリフトがスイングを圧倒する。

ドリフトとスイングを量的に議論することもできる。\(k\) 回目 \((k \leq \min(m, n))\) の賭けが終わったとき、ギャンブラーが勝った回数はパラメータ \(p < 1/2\), \(k\) を持つ二項分布に従う。一度の賭けで獲得する収益の期待値は \(p - q = 2p - 1\) ドルなので、この時点における資金の期待値は \(n - k(1 - 2p)\) である。そのため平均的なギャンブラーがここから勝利するには、今後の勝利回数が期待値より \(m + k(1 - 2p)\) だけ大きくなる必要がある。しかし補題 20.3.9 からは、二項変数に従う勝利回数の標準偏差はわずか \(\sqrt{kp(1-p)}\) に過ぎないと分かる。言い換えれば、ギャンブラーが勝利するには、これからの勝利回数の期待値からの偏差が標準偏差の

\[ \frac{m + k(1 - 2p)}{\sqrt{kp(1-2p)}} = \Theta (\sqrt{k}) \]

倍になる必要がある。しかし本書で何度か見てきたように二項分布の裾は非常に低く、この確率は途方もなく小さい。

賭けが公平なら、ドリフトは存在しない: スイングだけが存在する。資金を常に下降させるドリフトが存在しないとき、先ほどの直感は正しくなる。例えば、ギャンブラーが最初に \(1\) 兆ドルを持っているなら、いずれ幸運なスイングが起きて収益が \(100\) ドルに達することはまず間違いない。

21.1.4 ランダムウォークの長さ

ギャンブラーが勝利する確率 \(w_{n}\) を賭けが公平な場合と公平でない場合の両方で求めることができた。続いてギャンブルが終わる (目標収益を得るか破産する) までに平均して何度の賭けが必要かを計算してみよう。ここでも線形再帰方程式のアプローチが利用できる。

\(p\) と \(T\) を固定する。初期資金が \(n\) ドルのときギャンブルが終わるまでの賭けの回数の期待値を \(e_{n}\) とする。ギャンブルは \(n = 0\) または \(n = T\) のとき終了するので、今回の境界条件は \(e_{0} = e_{T} = 0\) である。

それ以外のとき、ギャンブラーの初期資金は \(n\) ドルであり、\(0 < n < T\) が成り立つ。全期待値の法則 (定理 19.4.6) より、求める期待値は「最初の賭けで勝ったときの期待値」と「最初の賭けで負けたときの期待値」の確率による重み付き平均に等しい。最初の賭けで勝つと資金は \(n + 1\) ドルとなるので、そこからゲーム終了までの賭けの回数の期待値は \(e_{n+1}\) である。つまり、次の等式が成り立つ:

\[ \operatorname{Ex} [\text{\(n\) ドルで始めた場合の賭けの回数} \, | \, \text{最初の賭けに勝つ} ] = 1 + e_{n+1} \]

同様に、最初の賭けで負けると資金は \(n - 1\) ドルとなるので、そこからは平均 \(e_{n-1}\) 回の賭けでゲームが終了する:

\[ \operatorname{Ex} [\text{\(n\) ドルで始めた場合の賭けの回数} \, | \, \text{最初の賭けに負ける} ] = 1 + e_{n-1} \]

よって次の等式を得る:

\[ \begin{aligned} e_{n} &= p \operatorname{Ex} [\text{\(n\) ドルで始めた場合の賭けの回数} \, | \, \text{最初の賭けに勝つ} ] \\ &\qquad + q \operatorname{Ex} [\text{\(n\) ドルで始めた場合の賭けの回数} \, | \, \text{最初の賭けに負ける} ] \\ &= p(1 + e_{n+1}) + q(1 + e_{n-1}) \\ &= pe_{n+1} + qe_{n-1} + 1 \end{aligned} \]

ここから次の線形方程式を得る:

\[ e_{n+1} = \frac{1}{p} e_{n} - \frac{q}{p} e_{n-1} - \frac{1}{p} \tag{21.10}\]

この線形方程式をこれまでに何度も使ってきた手法で解けば、次の結果を得る:

定理 21.1.3

初期資金 \(n\), 目標資金 \(T\), 毎回の賭けの勝率が \(p\) のギャンブラーの破産問題において、次の等式が成り立つ:

\[ \operatorname{Ex} [\text{賭けの回数}] = \begin{cases} n (T - n) & (p = \dfrac{1}{2} \text{のとき}) \\[15pt] \dfrac{w_{n} \cdot T - n}{p - q} & (p \neq \dfrac{1}{2} \text{ のとき}) \end{cases} \tag{21.11}\]

ここで \(w_{n} = \dfrac{r^{n} - 1}{r^{T} - 1} = \operatorname{Pr} [\text{ギャンブラーが勝利する}]\) である。

賭けが公平なら、等式 \(\text{(21.11)}\) は次のように表現できる:

\[ \operatorname{Ex} [\text{賭けの回数}] = \text{初期資金} \cdot \text{目標収益} \tag{21.12}\]

例えば、\(10\) ドルを持ったギャンブラーが \(10\) ドル稼ぐか破産するまで賭けを続けるなら、彼がギャンブルを終えるまでの賭けの回数の期待値は \(10 \times 10\) 回である。同様に、初期資金が\(500\) ドルで目標収益が \(100\) ドルなら、平均で \(500 \cdot 100 = 50{,}000\) 回の賭けが終わるとゲームが終了する。この単純な式 \(\text{(21.12)}\) からは直感的な証明の存在が強く示唆されるものの、まだ見つかっていない (Pascal よ、あなたはいまどこに？)。

21.1.5 勝っているうちに席を立つべき

ギャンブラーは儲かっている間に決してゲームを終了しないとしてみよう。つまり、彼は初期資金 \(n > 0\) ドルを持って賭けを始め、一文無しになるまで賭けを続けると仮定する。この設定の問題を非有界ギャンブラーの破産問題 (unbounded gambler's ruin problem) と呼ぶ。この場合、賭けがギャンブラーに有利でない限り彼は確実に破産することが言える。特に、\(p = 1/2\) で賭けが公平な場合でも破産は確実になる。

補題 21.1.4

初期資金が \(n > 0\) ドルで毎回の賭けの公平な (勝率が \(1/2\) の) 非有界ギャンブラーの破産問題では、ギャンブラーは確率 \(1\) で破産する。

証明通常のギャンブラーの破産問題で初期資金 \(n\) ドルを持って賭けを始めたギャンブラーが目標資金 \(T\) に到達することなく破産する場合、彼は目標資金を設定しない場合でも破産する。よって、目標資金 \(T\) を無視するときに破産する確率は、目標資金 \(T > n\) で本当に賭けを終了するときに破産する確率以上である。

定理 21.1.1 より、賭けが公平なとき彼が破産する確率は \(1 - n/T\) である。この値は \(T\) を大きくすればいくらでも \(1\) に近づけることができる。よって、目標資金が存在しないとき彼が破産する確率は \(1\) にいくらでも近い下界を持つ。これは確率が \(1\) であることを意味する。 ■

例えば、\(100\) 万ドルを持ったギャンブラーが完全に公平な賭けを繰り返し行うと、確率 \(1\) でいずれ一文無しになる。しかし良いニュースもある: ゲームが公平なら、賭けは永遠に続くと「期待」できる:

補題 21.1.5

ギャンブラーの初期資金が \(n > 0\) ドルで賭けが公平な非有界ギャンブラーの破産問題では、終了するまでの賭けの回数の期待値が無限大である。

証明は練習問題 (問題 21.2) とする。

よって初期資金がわずか \(1\) ドルの場合でも、破産するまでの賭けの回数の期待値は無限大になる！これは心強い情報に思える ── 破産は無限に後に起こるので、賭けに興じている間に破産を心配しなくても構わないのではないだろうか？本当に心配が必要ない似た状況もある: 例えば \(1\) 秒間に障害を起こす確率が極端に小さい値 \(10^{-100}\) なら、障害は確率 \(1\) でいずれ発生するものの、それまでの時間が宇宙の年齢の数倍より小さくなる可能性は非常に低い。

しかし一般に、破産までの時間の期待値が無限大だと知っても安心しない方が賢明である。例えば、次のゲームを考えてほしい: \(1\) 秒間に障害を起こす確率が \(10^{-100}\) であるプロセスを最初に \(1\) 秒間実行し、そこで障害が起こらなかったら即座に破産する。そして、もし障害が起きれば公平な非有界ギャンブラーの破産問題のゲームを実行する。このゲームを遊ぶプレイヤーは \(1 - 10^{-100}\) という圧倒的な確率で \(1\) 秒後に破産するものの、\(10^{-100}\) の確率で破産までの時間の期待値が無限大であるゲームに進む。ゲーム全体を考えるとき、破産までの時間の期待値は公平な非有界ギャンブラーの破産問題における破産までの時間の期待値と \(10^{-100}\) の積以上、つまり無限大である。

公平な非有界ギャンブラーの破産問題で初期資金が \(1\) ドルなら、最初の賭けで破産する確率が \(50\%\) であり、最初の \(5\) 回の賭けまでに破産する確率は \(15/16\) に及ぶ。そのため破産までの時間の期待値が無限大だとしても、高確率ですぐに破産するギャンブラーの慰めにはならない。

ここでは期待値の線形性を無限個の期待値に適用している。賭けを何度してもやり取りされる価値は有界なので、この適用に問題はない。 ↩︎