2015/01/10

破産の確率と漸化式

分野: データの分析,確率  レベル: 最難関大学

漸化式を用いて確率を求める有名問題を解説します。難関大の受験対策のよい練習問題になるだけでなく,現実的で面白い話題です。

破産の確率の問題

以下のような問題を考えます。

問題

$n$ 円持っている。勝ったら $1$ 円もらえ,負けたら $1$ 円失う勝負を繰り返し行う。勝つ確率は $p$ である。 $N$ 円になったら十分儲かったとみなして勝負は終了する。このとき所持金が $0$ 円になって終了する確率(破産する確率)を求めよ。

数学で扱いやすいように問題を言い換えます。

破産確率の問題

問題

数直線上に $O(0),\:P(n),\:A(N)$ がある($0 <n <N$)。
$P$ は動点であり「確率 $p$ で正の方向に1進み,確率 $q=1-p$ で負の方向に1進む」という行動を繰り返す。 $P$ が $O$ か $A$ にたどり着いたら終了。このとき $O$ にたどり着いて終了する確率はいくらか?

結果と考察

答えが面白いので導出の前に結果を書いてしまいます!

破産確率は,
$p\neq q$ のとき $\dfrac{\alpha^n-\alpha^N}{1-\alpha^N}$

$p=q$ のとき $1-\dfrac{n}{N}$

ただし,表記簡略化のために $\dfrac{q}{p}=\alpha$ とおきました($\alpha$ が大きいほど負ける確率が高い)。


破産確率についての考察

  • $p=q$ のときの結果が非常に美しいです。特に $n=\dfrac{N}{2}$ のとき,当然ですが破産確率は $\dfrac{1}{2}$ になります。
  • $N$ を固定すると破産確率は $n$ の減少関数になっています。これは,スタートの位置が「破産側」より「勝利側」に近いほど破産確率が低いという直感とも合致します。
  • $p > q$ のとき,$\alpha <1$ です。 $n$ と $N$ が十分大きいとき(例えば $n=100,\:N=200$)破産確率はほぼ $0$ です。
  • $p <q$ のとき,$\alpha > 1$ です。 $n$ が十分大きく,$N$ がさらに十分大きいとき(例えば $n=100,\:N=200$)破産確率はほぼ $1$ です。

つまり,たくさんの回数勝負する場合は勝率が $\dfrac{1}{2}$ より大きいかどうかによって「ほぼ確実に勝てる」か「ほぼ確実に破産する」かが決まります。

破産確率の導出

ここからは破産確率を導出していきます。

まずは重要な漸化式を立てる部分です。

(漸化式を立てる)
$N$ を固定して $n$ を変数だと考える。破産の確率は $n$ の関数である。その確率を $a_n$ とおく。

破産の確率を一回目に勝つ場合と負ける場合に分けて考えることにより以下の漸化式が立つ:
$a_{n}=pa_{n+1}+qa_{n-1}\:(1\leq n\leq N-1)$
(一回目に勝てばその後確率 $a_{n+1}$ で破産,一回目に負ければその後確率 $a_{n-1}$ で破産)

ただし,端っこ($n=1,\:N-1$)でも漸化式が成立するように $a_0=1,\:a_N=0$ とした。

あとはこの三項間漸化式を解くだけです。どの方法でもOKですが,今回は三項間漸化式の3通りの解き方の二つ目の解き方を使います。

多くの三項間漸化式では初期条件が $a_1,\:a_2$ で与えられるのに対して,今回は $a_0$ と $a_N$ で与えられていることに注意してください。

(漸化式を解く)
特性方程式は $x=px^2+(1-p)$ であり,この解は $x=1$ と $\dfrac{q}{p}(=\alpha)$ である。 $\alpha=1$ のときは重解となるので場合分けが必要。

・ $p\neq q,\:(\alpha\neq 1)$ のとき,
漸化式の解は $a_n=A\alpha^n+B$ と書ける。
$a_0=1,\:a_N=0$ を満たすように $A,\:B$ を決めると,$A=\dfrac{1}{1-\alpha^N},\:B=\dfrac{-\alpha^N}{1-\alpha^N}$ となる:
$a_n=\dfrac{\alpha^n-\alpha^N}{1-\alpha^N}$

・ $p=q,\:(\alpha =1)$ のとき,
漸化式の解は $a_n=An+B$ と書ける。
$a_0=1,\:a_N=0$ を満たすように $A,\:B$ を決めると,$B=1,\:A=-\dfrac{1}{N}$ となる:
$a_n=1-\dfrac{n}{N}$

なお,$p=q=\dfrac{1}{2}$ のときは電気回路との対応定理を使えば一瞬で解けます。

破産したくないなら勝率が0.5より確実に大きい賭けを探さないといけません。

Tag: 漸化式の解き方と応用例まとめ

分野: データの分析,確率  レベル: 最難関大学