確率漸化式
確率漸化式
確率の問題は, しばしば数列の漸化式の問題に帰着される.
問題《三角形の周上のランダム・ウォーク》
正三角形 $\mathrm{ABC}$ の頂点 $\mathrm A$ にいるアリが $1$ 秒ごとに異なる頂点に等確率で移動していくとき,
$n$ 秒後に頂点 $\mathrm A$ にいる確率を求めよ.
解答例
アリが $n$ 秒後に頂点 $\mathrm A,$ $\mathrm B,$ $\mathrm C$ にいる確率をそれぞれ $a_n,$ $b_n,$ $c_n$ とおく.
このとき,
\[\begin{aligned}
&a_{n+1} = \frac{1}{2}b_n+\frac{1}{2}c_n, \\
&a_n+b_n+c_n = 1
\end{aligned}\]
であるから,
$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$ とおく.
- (1)
- $p_k = ap_{k-1}+bp_{k+1}$ $(k \geqq 1)$ が成り立つことを説明せよ.
- (2)
- A, B の所持金がそれぞれ $m$ 円, $n$ 円であるとする.
このとき B が破産する確率 $p_n$ を,
(i) $a = b = \dfrac{1}{2}$ のとき (ii) $a < b$ のときの $2$ つの場合に分けて, 次の手順で求めよ.
- ①
- $p_{k+1}-\alpha p_k = \beta (p_k-\alpha p_{k-1})$ なる実数 $\alpha,$ $\beta$ $(\alpha \geqq \beta )$ を $1$ 組求める.
- ②
- $p_0 = 1,$ $p_{m+n} = 0$ であることを使って, $c = p_1-p_0$ の値を求める.
- ③
- $p_n$ を求める.
解答例
- (1)
- B の所持金が $k$ 円 $(k \geqq 1)$ のとき, 確率 $a$ でゲームに負けて所持金が $k-1$ 円になり, 確率 $b$ でゲームに勝って所持金が $k+1$ 円になるから, \[ p_k = ap_{k-1}+bp_{k+1} \quad \cdots [*]\] が成り立つ.
- (2)
- $p_{k+1}-\alpha p_k = \beta (p_k-\alpha p_{k-1})\ \cdots [*]'$ を整理すると,
\[ p_{k+1}-(\alpha +\beta )p_k+\alpha\beta p_{k-1} = 0\ \cdots [*]''\]
となる.
- (i)
- $a = b = \dfrac{1}{2}$ のとき.
- ①
- $[*]$ に $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)\] は $[*]''$ つまり $[*]'$ を満たす.
- ②
- ① の結果から \[ 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}$ である.
- ③
- ①, ② の結果から, 求める確率は \[ p_n = p_0+cn = 1-\frac{n}{m+n} = \frac{m}{m+n}\] である.
- (ii)
- $a < b$ のとき.
- ①
- $[*]$ を整理すると \[ 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)\] は $[*]''$ つまり $[*]'$ を満たす.
- ②
- ① の結果から \[ 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{aligned} 0 &= p_{m+n} = p_0+\sum_{k = 0}^{m+n-1}c\left(\frac{a}{b}\right) ^k = 1+c\cdot\frac{1-\dfrac{a^{m+n}}{b^{m+n}}}{1-\dfrac{a}{b}} \\ c &= -\frac{1-\dfrac{a}{b}}{1-\dfrac{a^{m+n}}{b^{m+n}}} \end{aligned}\] である.
- ③
- ①, ② の結果から, 求める確率は \[\begin{aligned} 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{aligned}\] である.
参考
この種の問題は「ギャンブラーの破産問題」(gambler's ruin problem) として有名である.
確率論は, このように, 投資の利益・損失の見積りなど, さまざまな問題の解決に応用されている.
問題《完全順列の確率》
$n$ 人の席替えで, 全員の席が替わる場合の数を $a_n,$ 確率を $p_n$ とおく.
- (1)
- $n > 2$ のとき, $a_n = (n-1)(a_{n-1}+a_{n-2})$ が成り立つことを説明せよ.
- (2)
- $n > 2$ のとき, $p_n-p_{n-1} = -\dfrac{1}{n}(p_{n-1}-p_{n-2})$ が成り立つことを示せ.
- (3)
- 数列 $\{ p_n\}$ の一般項を求めよ. 必要ならば, 和の記号 $\Sigma$ を用いてよい.
解答例
- (1)
- $n$ 人の席替えを考える.
特定の人物 A, 残った $n-1$ 人の順に行っても, 場合の数は変わらない.
A が移動する方法は $n-1$ 通り.
A の移動先にいる人物を B として, いったん A と B の席を入れ替える.
- (i)
- 最後に A と B が入れ替わらない場合. 全員の席が替わる方法は, A 以外の $n-1$ 人全員の席が替わる $a_{n-1}$ 通りある.
- (ii)
- 最後に A と B が入れ替わる場合. 全員の席が替わる方法は, 残りの $n-2$ 人全員の席が替わる $a_{n-2}$ 通りある.
- (2)
- $n$ 人が席替えをする方法は $n!$ 通りあるから, $p_n = \dfrac{a_n}{n!}$ である. $n > 2$ のとき, (1) で示した等式の両辺を $n!$ で割ると, \[\begin{aligned} 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} \\ p_n-p_{n-1} &= -\frac{1}{n}(p_{n-1}-p_{n-2}) \quad \cdots [1] \end{aligned}\] が得られる.
- (3)
- $p_2-p_1 = \dfrac{1}{2!}-\dfrac{0}{1!} = \dfrac{1}{2} \neq 0,$ $[1]$ と数学的帰納法により, \[ p_n-p_{n-1} \neq 0\] である. $[1]$ において $n$ を $3$ 以上 $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$ のとき成り立つ. $0! = 1$ であるから, $n \geqq 1$ のとき \[ p_n = \sum\limits_{k = 0}^n\frac{(-1)^k}{k!}\] が成り立つ.
参考
- それぞれをもとの位置と異なる位置に並べ替える順列は「完全順列」または「攪乱順列」(derangement) と呼ばれる. $n$ 個のものの「完全順列」の総数は「モンモール数」(Montmort number) と呼ばれ, その数 \[ n!\sum\limits_{k = 0}^n\frac{(-1)^k}{k!}\] を求める問題は「モンモールの問題」と呼ばれる. この公式については, こちらとこちらも参照.
- 指数関数の「マクローリン展開」$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}$ である.
問題《くじ引きのサドンデス》
つぼの中に $r$ 個 $(r \geqq 1)$ の赤玉と, $s$ 個 $(s \geqq 0)$ の白玉が入っている.
A と B の $2$ 人が, 交互に玉を $1$ 個ずつ取り出し, 先に赤玉を取り出した者を勝者とするゲームを行う.
ただし, 取り出した玉は, もとに戻さないものとする.
- (1)
- ちょうど $k$ 回目 (つまり $2$ 人の取り出した玉の合計がちょうど $k$ 個になったとき) に勝者が決まる確率を $p_k$ とするとき, \[ p_k \geqq p_{k+1} \quad (k \geqq 1)\] となることを示せ.
- (2)
- このゲームを A から始めるとする. すべての $r,$ $s$ に対して, A が勝者となる確率は $\dfrac{1}{2}$ 以上であることを示せ. また, A が勝者となる確率が $\dfrac{1}{2}$ となるための $r,$ $s$ の条件を求めよ.
(参考: $1984$ 京都大)
解答例
- (1)
- $k$ 回目に勝者が決まらない確率を $q_k$ とおく. このとき, \[\begin{aligned} p_{k+1} &= q_k\frac{r}{r+s-k} \quad \cdots [1], \\ q_{k+1} &= q_k\frac{s-k}{r+s-k} \end{aligned}\] から, \[\begin{aligned} p_{k+2} &= q_{k+1}\frac{r}{r+s-k-1} \\ &= q_k\frac{s-k}{r+s-k}\cdot\frac{r}{r+s-k-1} \quad \cdots [2] \end{aligned}\] が成り立つ. $[1],$ $[2]$ の辺々を割ると \[\frac{p_{k+1}}{p_{k+2}} = \frac{r+s-k-1}{s-k}\] が得られる. 一方, $r \geqq 1$ から $r+s-k-1 \geqq s-k$ であるので, $\dfrac{p_{k+1}}{p_{k+2}} \geqq 1$ つまり $p_{k+1} \geqq p_{k+2}$ が成り立つ. また, \[ p_1 = \frac{r}{r\!+\!s}, \quad p_2 = \frac{s}{r\!+\!s}\cdot\frac{r}{r\!+\!s\!-\!1} = p_1\frac{s}{r\!+\!s\!-\!1}\] から $p_1 \geqq p_2$ であるので, $p_k \geqq p_{k+1}$ が成り立つ.
- (2)
- A が勝つ確率を $P(A),$ B が勝つ確率を $P(B)$ とおく. $s$ が偶数のとき \[\begin{aligned} P(A) &= p_1+p_3+\cdots +p_{s-1}+p_{s+1}, \\ P(B) &= p_2+p_4+\cdots +p_s \end{aligned}\] であり, $s$ が奇数のとき \[\begin{aligned} P(A) &= p_1+p_3+\cdots +p_s, \\ P(B) &= p_2+p_4+\cdots +p_{s+1} \end{aligned}\] であるから, いずれの場合にも $p_1 \geqq p_2,$ $p_3 \geqq p_4,$ $\cdots$ から, $P(A) \geqq P(B)$ が成り立つ. よって, $P(A)+P(B) = 1$ から \[ 2P(A) \geqq P(A)+P(B) = 1\] であるので, $P(A) \geqq \dfrac{1}{2}$ が成り立つ. $p_{s+1} \neq 0$ に注意すると, この等号が成り立つためには, $p_1 = p_2$ かつ $s$ が奇数であることが必要である. $p_1 = p_2$ のとき, $p_1 = p_1\dfrac{s}{r+s-1}$ から, $r = 1$ が成り立つ. 逆に, $r = 1$ かつ $s$ が奇数であるとき $P(A) = P(B)$ となるので, 求める条件は “$r = 1$ かつ $s$ は奇数” である.