東京大学 2001年 理系 第6問 解説

方針・初手

試行ごとの点 $A, B$ の座標の変化を調べ、その差である $a-b$ がどのように推移するかを把握することが第一歩である。 問題のルールを式に直すと、$a-b$ の値のパターンがごく限られたもの（$-1, 0, 1$ のみ）になることに気づく。 （1）では状態遷移図や推移の規則を整理して漸化式を立てる。（3）では直接 $a$ の平均を求めようとすると複雑になるため、AとBの対称性を利用して $a+b$ の増加量に注目し、期待値の線形性を用いて計算を簡略化する。

解法1

$n$ 回目の試行後の点 A, B の座標をそれぞれ $a_n, b_n$ とおき、その差を $c_n = a_n - b_n$ とおく。 試行のルールより、$c_n$ と $c_{n+1}$ の関係は次のようになる。

(i)

$c_n > 0$ （すなわち $a_n > b_n$）のとき 表が出ると、AとBが共に正の方向に1動くので $a_{n+1} = a_n + 1, b_{n+1} = b_n + 1$。よって $c_{n+1} = c_n$。 裏が出ると、Bのみ1動くので $a_{n+1} = a_n, b_{n+1} = b_n + 1$。よって $c_{n+1} = c_n - 1$。

(ii)

$c_n = 0$ （すなわち $a_n = b_n$）のとき 表が出ると、Aのみ1動くので $a_{n+1} = a_n + 1, b_{n+1} = b_n$。よって $c_{n+1} = c_n + 1 = 1$。 裏が出ると、Bのみ1動くので $a_{n+1} = a_n, b_{n+1} = b_n + 1$。よって $c_{n+1} = c_n - 1 = -1$。

(iii)

$c_n < 0$ （すなわち $a_n < b_n$）のとき 表が出ると、Aのみ1動くので $a_{n+1} = a_n + 1, b_{n+1} = b_n$。よって $c_{n+1} = c_n + 1$。 裏が出ると、AとBが共に1動くので $a_{n+1} = a_n + 1, b_{n+1} = b_n + 1$。よって $c_{n+1} = c_n$。

(1)

初期状態は $a_0 = b_0 = 0$ より $c_0 = 0$ である。 上記の推移規則から、$c_n$ は $-1, 0, 1$ のいずれかの値しかとらないことがわかる。 $n$ 回の試行後に $c_n = 0$、$c_n = 1$、$c_n = -1$ となる場合の数をそれぞれ $X_n, Y_n, Z_n$ とおく。

表裏の出方の総数は $2^n$ 通りであるから、

$$ X_n + Y_n + Z_n = 2^n $$

また、試行のルールは A と B について対称であるため $Y_n = Z_n$ が成り立つ。 よって、$X_n + 2Y_n = 2^n$ より、

$$ Y_n = \frac{2^n - X_n}{2} $$

$n+1$ 回後に $a=b$ すなわち $c_{n+1} = 0$ となるのは、推移規則より

• $c_n = 1$ のときに裏が出る（1通り）
• $c_n = -1$ のときに表が出る（1通り） のいずれかであるから、

$$ X_{n+1} = Y_n \times 1 + Z_n \times 1 = 2Y_n $$

これに先ほどの $Y_n$ の式を代入して、

$$ X_{n+1} = 2^n - X_n $$

(2)

（1）で求めた漸化式 $X_{n+1} + X_n = 2^n$ の両辺を $2^{n+1}$ で割ると、

$$ \frac{X_{n+1}}{2^{n+1}} = -\frac{1}{2} \cdot \frac{X_n}{2^n} + \frac{1}{2} $$

$x_n = \frac{X_n}{2^n}$ とおくと、$x_{n+1} = -\frac{1}{2}x_n + \frac{1}{2}$ となる。 これを変形すると、

$$ x_{n+1} - \frac{1}{3} = -\frac{1}{2} \left( x_n - \frac{1}{3} \right) $$

$X_0$ は0回投げて $a=b=0$ となる場合の数なので $X_0 = 1$ である。よって $x_0 = 1$。 数列 $\left\{ x_n - \frac{1}{3} \right\}$ は初項 $x_0 - \frac{1}{3} = \frac{2}{3}$、公比 $-\frac{1}{2}$ の等比数列であるから、

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

$$ x_n = \frac{1}{3} + \frac{2}{3} \left( -\frac{1}{2} \right)^n $$

したがって、求める $X_n$ は、

$$ X_n = 2^n x_n = \frac{2^n}{3} + \frac{2}{3} (-1)^n = \frac{2^n + 2 \cdot (-1)^n}{3} $$

(3)

求める平均値は、$n$ 回試行後の $a_n$ の期待値 $E[a_n]$ と同じである。 対称性より $E[a_n] = E[b_n]$ が成り立つため、

$$ E[a_n] = \frac{1}{2} E[a_n + b_n] $$

が成り立つ。和の増分 $E[a_{k+1} + b_{k+1} - (a_k + b_k)]$ について考える。 状態 $c_k$ ごとに、1回の試行による $a+b$ の増加量の期待値を調べる。

(ア)

$c_k = 1$ のとき 表が出ると増加量は $2$、裏が出ると増加量は $1$ であるから、期待される増加量は

$$ 2 \times \frac{1}{2} + 1 \times \frac{1}{2} = \frac{3}{2} $$

(イ)

$c_k = 0$ のとき 表が出ると増加量は $1$、裏が出ると増加量は $1$ であるから、期待される増加量は

$$ 1 \times \frac{1}{2} + 1 \times \frac{1}{2} = 1 $$

(ウ)

$c_k = -1$ のとき 表が出ると増加量は $1$、裏が出ると増加量は $2$ であるから、期待される増加量は

$$ 1 \times \frac{1}{2} + 2 \times \frac{1}{2} = \frac{3}{2} $$

$k$ 回目の試行後に $c_k = 0$ となる確率は $x_k$、$c_k \neq 0$ となる確率は $1 - x_k$ である。 したがって、$k+1$ 回目の試行における $a+b$ の増加量の期待値は、

$$ E[a_{k+1} + b_{k+1} - (a_k + b_k)] = 1 \cdot x_k + \frac{3}{2} \cdot (1 - x_k) = \frac{3}{2} - \frac{1}{2}x_k $$

（2）で求めた $x_k = \frac{1}{3} + \frac{2}{3} \left( -\frac{1}{2} \right)^k$ を代入すると、

$$ \frac{3}{2} - \frac{1}{2} \left\{ \frac{1}{3} + \frac{2}{3} \left( -\frac{1}{2} \right)^k \right\} = \frac{4}{3} - \frac{1}{3} \left( -\frac{1}{2} \right)^k $$

期待値の線形性より、初期状態 $a_0+b_0=0$ からの和をとることで $E[a_n + b_n]$ を求める。

$$ \begin{aligned} E[a_n + b_n] &= \sum_{k=0}^{n-1} \left\{ \frac{4}{3} - \frac{1}{3} \left( -\frac{1}{2} \right)^k \right\} \\ &= \frac{4}{3}n - \frac{1}{3} \cdot \frac{1 - \left( -\frac{1}{2} \right)^n}{1 - \left( -\frac{1}{2} \right)} \\ &= \frac{4}{3}n - \frac{1}{3} \cdot \frac{2}{3} \left\{ 1 - \left( -\frac{1}{2} \right)^n \right\} \\ &= \frac{4}{3}n - \frac{2}{9} \left\{ 1 - \left( -\frac{1}{2} \right)^n \right\} \end{aligned} $$

したがって、求める $a$ の値の平均 $E[a_n]$ は、

$$ E[a_n] = \frac{1}{2} E[a_n + b_n] = \frac{2}{3}n - \frac{1}{9} \left\{ 1 - \left( -\frac{1}{2} \right)^n \right\} $$

解説

座標の差 $a_n - b_n$ に着目し、これが $\pm 1, 0$ の狭い範囲で推移するマルコフ連鎖になっていることを見抜けるかが最大のポイントである。差が広がらないという性質に気づけば、（1）（2）は標準的な確率漸化式の問題に帰着できる。 （3）は真正面から $a_n$ の値ごとの場合の数を追うのは非常に困難である。問題設定がAとBについて完全に対称であることを利用し、$a+b$ の増加量（期待値）を考える手法が鮮やかで効率的である。

答え

(1)

$$ X_{n+1} = 2^n - X_n $$

(2)

$$ X_n = \frac{2^n + 2 \cdot (-1)^n}{3} $$

(3)

$$ \frac{2}{3}n - \frac{1}{9} \left\{ 1 - \left( -\frac{1}{2} \right)^n \right\} $$