COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

確率の漸化式

確率の漸化式

 確率の問題は, しばしば数列の漸化式の問題に帰着される.

問題≪三角形上のランダム・ウォーク≫

 正三角形 $\mathrm{ABC}$ の頂点 $\mathrm A$ にいるアリが $1$ 秒ごとに異なる頂点に等確率で移動していくとき, $n$ 秒後に頂点 $\mathrm A$ にいる確率を求めよ.

解答例

 アリが $n$ 秒後に頂点 $\mathrm A,$ $\mathrm B,$ $\mathrm C$ にいる確率をそれぞれ $a_n,$ $b_n,$ $c_n$ とおく. このとき, \begin{align*} &a_{n+1} = \frac{1}{2}b_n+\frac{1}{2}c_n, \\ &a_n+b_n+c_n = 1 \end{align*} であるから,
$a_{n+1} = \dfrac{1}{2}(1-a_n)$ つまり $a_{n+1} = -\dfrac{1}{2}a_n+\dfrac{1}{2}$
が成り立つ. 両辺から $\alpha = -\dfrac{1}{2}\alpha +\dfrac{1}{2}$ の解 $\alpha = \dfrac{1}{3}$ を引いて整理すると, \[ a_{n+1}-\frac{1}{3} = -\frac{1}{2}\left( a_n-\frac{1}{3}\right)\] が得られる. よって, $\left\{ a_n-\dfrac{1}{3}\right\}$ は第 $0$ 項 $a_0-\dfrac{1}{3} = 1-\dfrac{1}{3} = \dfrac{2}{3},$ 公比 $-\dfrac{1}{2}$ の等比数列であるから,
$a_n-\dfrac{1}{3} = \dfrac{2}{3}\left( -\dfrac{1}{2}\right) ^n$ つまり $a_n = \dfrac{1}{3}+\dfrac{2}{3}\left( -\dfrac{1}{2}\right) ^n$
である.

背景

 本問のアリのように, 次に移動する位置が確率的に無作為に決まる運動を「ランダム・ウォーク」(random walk)と呼ぶ. 「ランダム・ウォーク」の概念は, さまざまな物理現象のモデル化に応用されている.

問題≪破産の確率≫

 A, B の $2$ 人がゲームを行い, 勝者が敗者から $1$ 円をもらうという試行を, 一方の所持金が $0$ 円になるまで繰り返す. $2$ 人の所持金の合計は $m+n$ 円であるとし, 各回のゲームで A の勝率は $a,$ B の勝率は $b$ $(0 < a \leqq b < 1)$ であり, 引き分けはないとする. B の所持金が $k$ 円になったときに B が最終的に破産する確率を $p_k$ とおく.
(A)
$p_k = ap_{k-1}+bp_{k+1}$ $(k \geqq 1)$ が成り立つことを説明せよ.
(B)
A の所持金が $m$ 円, B の所持金が $n$ 円であるとき B が破産する確率 $p_n$ を,
(i) $a = b = \dfrac{1}{2}$ のとき,  (ii) $a < b$ のとき
の $2$ つの場合に分けて, 次の手順で求めよ.
(1)
$p_{k+1}-\alpha p_k = \beta (p_k-\alpha p_{k-1})$ を満たす定数 $\alpha,$ $\beta$ $(\alpha \geqq \beta )$ を $1$ 組求める.
(2)
$p_0 = 1,$ $p_{m+n} = 0$ であることを利用して, $c = p_1-p_0$ の値を求める.
(3)
$p_n$ を求める.

解答例

(A)
B の所持金が $k$ 円$(k \geqq 1)$のとき, 確率 $a$ でゲームに負けて所持金が $k-1$ 円になり, 確率 $b$ でゲームに勝って所持金が $k+1$ 円になるから, \[ p_k = ap_{k-1}+bp_{k+1} \quad \cdots [1]\] が成り立つ.
(B)
$p_{k+1}-\alpha p_k = \beta (p_k-\alpha p_{k-1})\ \cdots [2]$ を整理すると, \[ p_{k+1}-(\alpha +\beta )p_k+\alpha\beta p_{k-1} = 0\ \cdots [2]'\] となる.
(i)
$a = b = \dfrac{1}{2}$ のとき.
(1)
$[1]$ に $a = b = \dfrac{1}{2}$ を代入して整理すると \[ p_{k+1}-2p_k+p_{k-1} = 0\] となるから, \[\alpha +\beta = 2, \quad \alpha\beta = 1\] の解 \[ (\alpha,\beta) = (1,1)\] は $[2]'$ つまり $[2]$ を満たす.
(2)
(1) の結果から \[ p_{k+1}-p_k = p_k-p_{k-1} \quad (k \geqq 1)\] が成り立つので, $\{ p_k\}$ は等差数列である. $p_0 = 1,$ $p_{m+n} = 0$ であるから, その公差は $c = -\dfrac{1}{m+n}$ である.
(3)
(1), (2) の結果から, 求める確率は \[ p_n = p_0+cn = 1-\frac{n}{m+n} = \frac{m}{m+n}\] である.
(ii)
$a < b$ のとき.
(1)
$[1]$ を整理すると \[ p_{k+1}-\frac{1}{b}p_k+\frac{a}{b}p_{k-1} = 0\] となるから, \[\alpha +\beta = \frac{1}{b}, \quad \alpha\beta = \frac{a}{b}\] の解 \[ (\alpha,\beta) = \left( 1,\frac{a}{b}\right)\] は $[2]'$ つまり $[2]$ を満たす.
(2)
(1) の結果から \[ p_{k+1}-p_k = \frac{a}{b}(p_k-p_{k-1}) \quad (k \geqq 1)\] が成り立つので, $\{ p_{k+1}-p_k\}$ は第 $0$ 項 $c,$ 公比 $\dfrac{a}{b}$ の等比数列であり, その一般項は \[ p_{k+1}-p_k = c\left(\frac{a}{b}\right) ^k\] である. よって, \begin{align*} p_{m+n} &= p_0+\sum_{k = 0}^{m+n-1}c\left(\frac{a}{b}\right) ^k \\ 0 &= 1+c\cdot\frac{1-\dfrac{a^{m+n}}{b^{m+n}}}{1-\dfrac{a}{b}} \end{align*} から, \[ c = -\frac{1-\dfrac{a}{b}}{1-\dfrac{a^{m+n}}{b^{m+n}}}\] である.
(3)
(1), (2) の結果から, 求める確率は \begin{align*} p_n &= p_0+\sum_{k = 0}^{n-1}c\left(\frac{a}{b}\right) ^k \\ &= 1-\frac{1-\dfrac{a}{b}}{1-\dfrac{a^{m+n}}{b^{m+n}}}\cdot\frac{1-\dfrac{a^n}{b^n}}{1-\dfrac{a}{b}} \\ &= 1-\frac{b^{m+n}-a^nb^m}{b^{m+n}-a^{m+n}} \\ &= \frac{a^n(b^m-a^m)}{b^{m+n}-a^{m+n}} \end{align*} である.

背景

 この種の問題は「ギャンブラーの破産問題」(gambler's ruin problem)として有名である. 確率論は, このようなリスク管理の問題など, さまざまな問題の解決に応用されている.

問題≪完全順列の確率≫

 $n$ 人のクラスで席替えをするとき, 全員が前と同じ席にならない場合の数を $a_n,$ 確率を $p_n$ とおく.
(1)
$a_{n+2} = (n+1)(a_{n+1}+a_n)$ が成り立つことを説明せよ.
(2)
$n > 2$ のとき, $p_n-p_{n-1} = -\dfrac{1}{n}(p_{n-1}-p_{n-2})$ が成り立つことを示せ.
(3)
数列 $\{ p_n\}$ の一般項を求めよ. 必要ならば, 和の記号 $\Sigma$ を用いても良い.

解答例

(1)
$n+2$ 人のクラスの席替えを考える. 特定の人物 A, 残った $n+1$ 人の順に行っても求める場合の数は同じである. A が移動する方法は $n+1$ 通り. A の移動先にいる人物を B として, いったん A と B の席を入れ替える.
(i)
最後に A と B が入れ替わらない場合. 全員が前と同じ席にならない方法は, A 以外の $n+1$ 人が同じ席にならないように移動する方法に他ならず, $a_{n+1}$ 通りある.
(ii)
最後に A と B が入れ替わる場合. 全員が前と同じ席にならない方法は, 残りの $n$ 人が同じ席にならないように移動する方法に他ならず, $a_n$ 通りある.
(i), (ii) は排反なので, \[ a_{n+2} = (n+1)(a_{n+1}+a_n)\] が成り立つ.
(2)
$n$ 人が席替えをする方法は $n!$ 通りあるから, $p_n = \dfrac{a_n}{n!}$ である. (1) の結果から, $n > 2$ のとき, \begin{align*} p_n &= \frac{(n-1)(a_{n-1}+a_{n-2})}{n!} \\ &= \frac{n-1}{n}\cdot\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\cdot\frac{a_{n-2}}{(n-2)!} \\ &= \left( 1-\frac{1}{n}\right) p_{n-1}+\frac{1}{n}p_{n-2} \end{align*} となるので, \[ p_n-p_{n-1} = -\frac{1}{n}(p_{n-1}-p_{n-2}) \quad \cdots (R_n)\] が成り立つ.
(3)
$(R_n)$ から, $3 \leqq k \leqq n$ なる各整数 $k$ に対して, \[ p_k-p_{k-1} = -\frac{1}{k}(p_{k-1}-p_{k-2}) \quad \cdots (R_k)\] が成り立つ. $p_2-p_1 = \dfrac{1}{2!}-\dfrac{0}{1!} = \dfrac{1}{2} \neq 0$ であるので, 数学的帰納法により, \[ p_n-p_{n-1} \neq 0\] が従う. $(R_k)$ $(3 \leqq k \leqq n)$の辺々を掛け合わせて $p_k-p_{k-1}$ $(3 \leqq k \leqq n-1)$で割ると, \[ p_n-p_{n-1} = (-1)^{n-2}\frac{p_2-p_1}{n(n-1)\cdots 3} = \frac{(-1)^n}{n!}\] となる. これは $n > 1$ に対して成り立つ. ゆえに, \[ p_1 = 0, \quad p_n = \sum\limits_{k = 2}^n\frac{(-1)^k}{k!} \quad (n > 1)\] が成り立つ.

背景

  • それぞれをもとの位置と異なる位置に並び替える順列を「完全順列」または「攪乱順列」(derangement)という. $n$ 個のものの「完全順列」の総数は「モンモール数」(Montmort number)と呼ばれ, その数を求める問題は「モンモールの問題」と呼ばれる. この素朴な問題は, 本問のように身近で重要な問題である.
  • $0! = 1$ と定めると $p_n = \displaystyle\sum_{k = 0}^n\frac{(-1)^k}{k!}\ (n \geqq 0)$ と表されるので, 指数関数の「マクローリン展開」$e^x = \displaystyle\sum_{n = 0}^\infty\frac{x^n}{n!}$ から, $\displaystyle\lim_{n \to \infty}p_n = \sum_{n = 0}^\infty\frac{(-1)^n}{n!} = e^{-1}$ である.