II慶應義塾大学 2004年 数学 第II問解答・解説

[II] 二袋の球操作（解説改訂2） 袋の順に $RB\mid RW$ のように書く。袋の中の球を取り出す組合せは等確率で数える。状態遷移を調べる際、袋の入替えや赤・白の入替えで同じになる状態はまとめる。

(1)(i) 状態Aへの初回到達 初期状態を $S=RB\mid RW$、目標を $A=R\mid W$ とする。$S$ からは確率 $1/4$ で $S$ に戻り、確率 $1/4$ で $T=RB\mid BW$ になる。残りの確率 $1/2$ で移る状態からは $A$ に到達しない。$T$ からは確率 $1/4$ で $T$ に戻り、確率 $1/4$ で $A$ になる。残りの確率 $1/2$ で移る状態からも $A$ には到達しない。

$n$ 回目に初めて $A$ となる経路では、$S$ で $k-1$ 回とどまったのち $T$ に移り、$T$ で $n-k-1$ 回とどまってから $A$ になる（$k=1,\ldots,n-1$）。各経路の確率は $4^{-n}$、経路数は $n-1$ なので $$\displaystyle \boxed{p_n=\frac{n-1}{4^n}}\qquad(n\ge1).$$

(1)(ii) 両方が空になる状態Bへの初回到達 $Z=\varnothing\mid\varnothing$ を目標とする。以下が初期状態から到達する状態と次の遷移である。$L=R\mid W$ は状態Bには到達せず、そのまま止まらない状態である。 $$\displaystyle \small \begin{array}{c|c|l} \text{状態}&\text{袋の中身}&\text{次の状態（確率）}\\ \hline S&RB\mid RW&S\ (\frac14),\ D\ (\frac14),\ E\ (\frac14),\ F\ (\frac14)\\ D&B\mid R&U\ (1)\\ E&RB\mid BW&L\ (\frac14),\ G\ (\frac12),\ E\ (\frac14)\\ F&RB\mid RB&V\ (\frac14),\ G\ (\frac12),\ U\ (\frac14)\\ G&BB\mid BR&D\ (\frac12),\ H\ (\frac12)\\ H&BB\mid BB&U\ (1)\\ U&B\mid B&Z\ (1)\\ V&R\mid R&Z\ (1)\\ L&R\mid W&L\ (1) \end{array}$$ $G$ からは $D$ または $H$ を経て、いずれも3回の操作で必ず $Z$ となる。初期状態 $S$ に戻る回数を $k$ とする。

$n=k+3$ の到達経路は、$S$ から $D$ へ進む場合と、$F$ から $U$ または $V$ へ進む場合である。合わせた確率は $$\displaystyle 4^{-k}\left(\frac14+\frac14\cdot\frac12\right) =\frac38\,4^{-k}.$$ $n\ge5$ では次の2種類もある。$S$ から $F$ を経て $G$ に進む経路は、$k=n-5$ と決まり、確率は $\displaystyle \frac18 4^{-(n-5)}$ である。また $S$ に $k$ 回、$E$ に $l$ 回とどまり、$E$ から $G$ に進む経路は $k+l=n-5$ を満たす。非負整数の組 $(k,l)$ は $n-4$ 通りあり、各経路の確率は $\displaystyle \frac18 4^{-(n-5)}$ である。従って $$\displaystyle q_1=q_2=0,\qquad q_3=\frac38,\qquad q_4=\frac3{32},$$ さらに $n\ge5$ では $$\displaystyle \begin{aligned} q_n&=\frac38 4^{-(n-3)}+\frac18 4^{-(n-5)} +\frac{n-4}{8}4^{-(n-5)}\\ &=\boxed{\frac{16n-45}{2^{2n-3}}}. \end{aligned}$$

(2) 初期状態 $RBB\mid RWB$ から状態Aへの初回到達 袋内の並びを無視すると、初期状態は $X_{15}=BBR\mid BRW$ である。目標は $A=R\mid W$。次表の $N$ は、以後どの経路でも $A$ に届かない状態群をまとめた記号である。 $$\displaystyle \small \begin{array}{c|c|l} \text{状態}&\text{袋の中身}&\text{次の状態（確率）}\\ \hline X_8&BR\mid BW&A\ (\frac14),\ X_8\ (\frac14),\ N\ (\frac12)\\ X_9&BR\mid RW&X_8\ (\frac14),\ X_9\ (\frac14),\ N\ (\frac12)\\ X_{14}&BBR\mid BBW&X_8\ (\frac49),\ X_{14}\ (\frac19),\ N\ (\frac49)\\ X_{15}&BBR\mid BRW&X_9\ (\frac29),\ X_{14}\ (\frac29),\ X_{15}\ (\frac19),\ N\ (\frac49) \end{array}$$ ここで $N$ に含めた状態群は $$\begin{aligned}\mathcal N=\{&B\mid B,\ B\mid R,\ R\mid R,\ BB\mid BB,\ BB\mid BR,\\ &BB\mid RW,\ BR\mid BR,\ BBB\mid BBB,\\ &BBB\mid BBR,\ BBB\mid BRW,\ BBR\mid BBR\}.\end{aligned}$$ とその袋・赤白の入替えで得られる状態である。操作後もこの集合内か $Z$ にとどまり、$A$ には移らない。例えば $BB\mid BR$ は $B\mid R$ または $BB\mid BB$ へ、$BBB\mid BRW$ は $BB\mid RW$ または $BBB\mid BBR$ へ移り、いずれも集合内にある。表の $N$ への遷移はこの閉じた状態群への遷移をまとめたものである。

$X_8,X_9,X_{14},X_{15}$ を出発したとき、$n$ 回目に初めて $A$ となる確率をそれぞれ $f_n,g_n,h_n,r_n$ とする。また $f_0=g_0=h_0=r_0=0$ とおく。遷移表から、$n\ge1$ で $$\displaystyle f_1=\frac14,\quad f_n=\frac14 f_{n-1}\ (n\ge2),\qquad g_1=0,\quad g_n=\frac14 f_{n-1}+\frac14g_{n-1}\ (n\ge2).$$ 従って $$f_n=4^{-n},\qquad g_n=(n-1)4^{-n}.$$ 同様に $$\displaystyle h_1=0,\qquad h_n=\frac49 f_{n-1}+\frac19h_{n-1}\quad(n\ge2).$$ これを順に代入すると等比数列の和になり、 $$\displaystyle h_n=\frac49 4^{-(n-1)}\sum\limits _{j=0}^{n-2}\left(\frac49\right)^j =\frac{16}{5}4^{-n}-\frac{36}{5}9^{-n}.$$ 初期状態が $X_{15}$ であることから $$\displaystyle r_1=0,\qquad r_n=\frac29(g_{n-1}+h_{n-1})+\frac19r_{n-1}\quad(n\ge2).$$ この漸化式を解くと $$\displaystyle \boxed{r_n=\frac{40n+16}{25\cdot4^n} +\frac{234-360n}{25\cdot9^n}}\qquad(n\ge1).$$ この式は $n=1$ で $0$ である。また、$g_{n-1},h_{n-1}$ と $r_{n-1}$ の式を漸化式の右辺に代入すると $$\displaystyle \begin{aligned} \frac29(g_{n-1}+h_{n-1})+\frac19r_{n-1} &=\left(\frac{8(n-2)}9+\frac{128}{45}+\frac{160n-96}{225}\right)4^{-n}\\ &\quad+\left(-\frac{72}{5}+\frac{594-360n}{25}\right)9^{-n}\\ &=\frac{40n+16}{25\cdot4^n}+\frac{234-360n}{25\cdot9^n}. \end{aligned}$$ 従って初項と漸化式が一致し、帰納法で全ての $n$ に対して成り立つ。