東京大学 2010年 理系 第3問 解説

方針・初手

箱 $L$ のボールの個数に着目し、1回の操作による個数の変化を追跡する。状態遷移図をイメージしながら、遷移先ごとの確率から漸化式を立てる（いわゆる推移確率に基づく立式）。初期状態のボールの数 $x$ によって操作内容が変わるため、場合分けを行って遷移先を明確にすることがポイントである。

解法1

(1) 箱 $L$ のボールの個数が $z$ であるとき、1回の操作による箱 $L$ のボールの個数の変化を考える。

(i)

$0 \leqq z \leqq 15$ のとき $K(z) = z$ であるから、 表が出れば $R$ から $L$ へ $z$ 個移し、$L$ のボールは $z + z = 2z$ 個になる。（確率 $\frac{1}{2}$） 裏が出れば $L$ から $R$ へ $z$ 個移し、$L$ のボールは $z - z = 0$ 個になる。（確率 $\frac{1}{2}$） 特に、$z=0$ のときは $K(0)=0$ であり、表裏にかかわらずボールは移動せず $L$ のボールは $0$ 個のままである。したがって、$m \geqq 1$ において $P_{m-1}(0) = 0$ である。

(ii)

$16 \leqq z \leqq 30$ のとき $K(z) = 30 - z$ であるから、 表が出れば $R$ から $L$ へ $30 - z$ 個移し、$L$ のボールは $z + (30 - z) = 30$ 個になる。（確率 $\frac{1}{2}$） 裏が出れば $L$ から $R$ へ $30 - z$ 個移し、$L$ のボールは $z - (30 - z) = 2z - 30$ 個になる。（確率 $\frac{1}{2}$） 特に、$z=30$ のときは $K(30)=0$ であり、表裏にかかわらずボールは移動せず $L$ のボールは $30$ 個のままである。したがって、$m \geqq 1$ において $P_{m-1}(30) = 1$ である。

よって、初期状態 $x$ に対して、1回の操作で遷移する状態と確率から、$P_m(x)$ の漸化式は次のように立てられる。

$0 \leqq x \leqq 15$ のとき

$$ \begin{aligned} P_m(x) &= \frac{1}{2} P_{m-1}(2x) + \frac{1}{2} P_{m-1}(0) \\ &= \frac{1}{2} P_{m-1}(2x) \end{aligned} $$

$16 \leqq x \leqq 30$ のとき

$$ \begin{aligned} P_m(x) &= \frac{1}{2} P_{m-1}(30) + \frac{1}{2} P_{m-1}(2x - 30) \\ &= \frac{1}{2} \cdot 1 + \frac{1}{2} P_{m-1}(2x - 30) \\ &= \frac{1}{2} + \frac{1}{2} P_{m-1}(2x - 30) \end{aligned} $$

以上より、$P_m(x)$ を $P_{m-1}(y)$ で表すと以下のようになる。 $0 \leqq x \leqq 15$ のとき、$y = 2x$ を選んで $P_m(x) = \frac{1}{2} P_{m-1}(y)$ $16 \leqq x \leqq 30$ のとき、$y = 2x - 30$ を選んで $P_m(x) = \frac{1}{2} + \frac{1}{2} P_{m-1}(y)$

(2) (1)で求めた漸化式を繰り返し用いる。便宜上、$m=0$（0回操作後）の確率も考える。初期状態が $x$ のとき、$x=30$ ならば確率は $1$、$x \neq 30$ ならば確率は $0$ であるから、$P_0(30)=1$、$0 \leqq x \leqq 29$ のとき $P_0(x)=0$ と定義できる。これは(1)の漸化式と矛盾しない。

$x=10$ のとき、$0 \leqq x \leqq 15$ に該当するため、

$$ P_m(10) = \frac{1}{2} P_{m-1}(20) $$

次に $x=20$ について、$16 \leqq x \leqq 30$ に該当するため、

$$ P_{m-1}(20) = \frac{1}{2} + \frac{1}{2} P_{m-2}(10) $$

これらを代入して整理すると、

$$ \begin{aligned} P_m(10) &= \frac{1}{2} \left( \frac{1}{2} + \frac{1}{2} P_{m-2}(10) \right) \\ &= \frac{1}{4} P_{m-2}(10) + \frac{1}{4} \end{aligned} $$

ここで $m = 2n$ とおくと、数列 $\{ P_{2n}(10) \}$ の漸化式は、

$$ P_{2n}(10) = \frac{1}{4} P_{2(n-1)}(10) + \frac{1}{4} $$

特性方程式 $\alpha = \frac{1}{4}\alpha + \frac{1}{4}$ を解くと $\alpha = \frac{1}{3}$ となるため、次のように変形できる。

$$ P_{2n}(10) - \frac{1}{3} = \frac{1}{4} \left( P_{2(n-1)}(10) - \frac{1}{3} \right) $$

したがって、数列 $\left\{ P_{2n}(10) - \frac{1}{3} \right\}$ は公比 $\frac{1}{4}$ の等比数列である。初項は $n=1$ のときの $P_2(10) - \frac{1}{3}$ であり、$P_2(10)$ は、

$$ P_2(10) = \frac{1}{4} P_0(10) + \frac{1}{4} = \frac{1}{4} \cdot 0 + \frac{1}{4} = \frac{1}{4} $$

ゆえに、

$$ P_2(10) - \frac{1}{3} = \frac{1}{4} - \frac{1}{3} = -\frac{1}{12} $$

一般項は、

$$ \begin{aligned} P_{2n}(10) - \frac{1}{3} &= -\frac{1}{12} \left( \frac{1}{4} \right)^{n-1} \\ &= -\frac{1}{3} \cdot \frac{1}{4} \left( \frac{1}{4} \right)^{n-1} \\ &= -\frac{1}{3} \left( \frac{1}{4} \right)^n \end{aligned} $$

よって、

$$ P_{2n}(10) = \frac{1}{3} \left\{ 1 - \left( \frac{1}{4} \right)^n \right\} $$

(3) (2)と同様に漸化式を繰り返し用いて、状態 $x=6$ からの遷移を追う。

$$ \begin{aligned} P_m(6) &= \frac{1}{2} P_{m-1}(12) \quad (\because 0 \leqq 6 \leqq 15) \\ P_{m-1}(12) &= \frac{1}{2} P_{m-2}(24) \quad (\because 0 \leqq 12 \leqq 15) \\ P_{m-2}(24) &= \frac{1}{2} + \frac{1}{2} P_{m-3}(18) \quad (\because 16 \leqq 24 \leqq 30) \\ P_{m-3}(18) &= \frac{1}{2} + \frac{1}{2} P_{m-4}(6) \quad (\because 16 \leqq 18 \leqq 30) \end{aligned} $$

これらを順次代入して整理する。

$$ \begin{aligned} P_m(6) &= \frac{1}{2} \cdot \frac{1}{2} P_{m-2}(24) \\ &= \frac{1}{4} \left( \frac{1}{2} + \frac{1}{2} P_{m-3}(18) \right) \\ &= \frac{1}{8} + \frac{1}{8} P_{m-3}(18) \\ &= \frac{1}{8} + \frac{1}{8} \left( \frac{1}{2} + \frac{1}{2} P_{m-4}(6) \right) \\ &= \frac{1}{8} + \frac{1}{16} + \frac{1}{16} P_{m-4}(6) \\ &= \frac{1}{16} P_{m-4}(6) + \frac{3}{16} \end{aligned} $$

ここで $m = 4n$ とおくと、

$$ P_{4n}(6) = \frac{1}{16} P_{4(n-1)}(6) + \frac{3}{16} $$

特性方程式 $\alpha = \frac{1}{16}\alpha + \frac{3}{16}$ を解くと $\alpha = \frac{1}{5}$ となるため、

$$ P_{4n}(6) - \frac{1}{5} = \frac{1}{16} \left( P_{4(n-1)}(6) - \frac{1}{5} \right) $$

初項を計算するために $P_4(6)$ を求める。

$$ P_4(6) = \frac{1}{16} P_0(6) + \frac{3}{16} = \frac{3}{16} $$

初項の差分は、

$$ P_4(6) - \frac{1}{5} = \frac{3}{16} - \frac{1}{5} = -\frac{1}{80} $$

したがって一般項は、

$$ \begin{aligned} P_{4n}(6) - \frac{1}{5} &= -\frac{1}{80} \left( \frac{1}{16} \right)^{n-1} \\ &= -\frac{1}{5} \cdot \frac{1}{16} \left( \frac{1}{16} \right)^{n-1} \\ &= -\frac{1}{5} \left( \frac{1}{16} \right)^n \end{aligned} $$

よって、

$$ P_{4n}(6) = \frac{1}{5} \left\{ 1 - \left( \frac{1}{16} \right)^n \right\} $$

解説

マルコフ連鎖（状態遷移）に関する確率漸化式の典型問題である。 (1)では、問題文の操作のルールを数式に翻訳して立式する力が問われる。特に、$z=0$ のときは一度 $0$ になると抜け出せない吸収状態であり、$z=30$ のときも一度 $30$ になると抜け出せない吸収状態となることに気づくことが重要である。 (2)(3)では、(1)で求めた漸化式を繰り返し適用することで、特定の初期状態に対して閉じた漸化式を導出できる。状態がループしたり、特定の状態だけを行き来したりする性質を見抜くことで、数項進んだ漸化式を立てて容易に一般項を求めることができる。

答え

(1)

$0 \leqq x \leqq 15$ のとき、$y = 2x$ と選び、$P_m(x) = \frac{1}{2} P_{m-1}(y)$ $16 \leqq x \leqq 30$ のとき、$y = 2x - 30$ と選び、$P_m(x) = \frac{1}{2} + \frac{1}{2} P_{m-1}(y)$

(2)

$$ P_{2n}(10) = \frac{1}{3} \left\{ 1 - \left( \frac{1}{4} \right)^n \right\} $$

(3)

$$ P_{4n}(6) = \frac{1}{5} \left\{ 1 - \left( \frac{1}{16} \right)^n \right\} $$