有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

確率漸化式

確率漸化式

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

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

 正三角形 $\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)
$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}$ 通りある.
(i), (ii) は排反なので, $a_n = (n-1)(a_{n-1}+a_{n-2})$ が成り立つ.
(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)
$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}$ である.

問題≪くじ引きのサドンデス≫

 つぼの中に $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{align*} 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{align*} から, \begin{align*} 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{align*} が成り立つ. $[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{align*} P(A) &= p_1+p_3+\cdots +p_{s-1}+p_{s+1}, \\ P(B) &= p_2+p_4+\cdots +p_s \end{align*} であり, $s$ が奇数のとき \begin{align*} P(A) &= p_1+p_3+\cdots +p_s, \\ P(B) &= p_2+p_4+\cdots +p_{s+1} \end{align*} であるから, いずれの場合にも $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$ は奇数」である.