トップ› 東京大学› 2015年› 理系第2問

東京大学 2015年理系第2問解説

方針・初手

さいころを1回投げるごとに、確率 $\frac{1}{2}$ で長さ2の文字列 $AA$ が追加され、確率 $\frac{1}{2}$（$\frac{1}{6} \times 3$）で長さ1の文字（$B, C, D$ のいずれか）が追加される。このようにして作られる文字列について、特定の位置の文字が何であるかの確率を求める問題である。

さいころを $n$ 回投げて得られる文字列の長さは $n$ 以上 $2n$ 以下となる。したがって、「左から $n$ 番目」や「左から $n-1$ 番目」の文字は、$n$ 回以内の試行によって確実に決定される。よって、試行回数が $n$ 回に制限されていることは気にせず、無限に試行を繰り返して文字列を生成し続けるとしたときの確率として求められる。

解法1では「左から $k$ 番目が特定の文字である確率」を直接漸化式で立てる方法を、解法2では「特定の文字数で文字列のブロックが区切れる確率」を考える方法を示す。

解法1

追加される文字列について、さいころの目が $1, 2, 3$ で $AA$（長さ2）が追加される事象を $X$、さいころの目が $4, 5, 6$ で $B, C, D$（長さ1）が追加される事象を $Y$ とする。事象 $X$ が起こる確率は $\frac{3}{6} = \frac{1}{2}$、事象 $Y$ が起こる確率は $\frac{3}{6} = \frac{1}{2}$ である。

(1)

左から $k$ 番目の文字が $A$ となる確率を $a_k$ とおく。最初の1回目の試行の結果で場合分けをする。$k \ge 3$ とする。

（i） 1回目に事象 $X$ が起こる場合（確率 $\frac{1}{2}$）最初に長さ2の文字列が追加される。元の文字列の $k$ 番目の文字は、2回目以降の試行で追加された「残りの文字列」の $k-2$ 番目の文字に該当する。これが $A$ となればよいから、その確率は $a_{k-2}$ である。

（ii） 1回目に事象 $Y$ が起こる場合（確率 $\frac{1}{2}$）最初に長さ1の文字列が追加される。元の文字列の $k$ 番目の文字は、「残りの文字列」の $k-1$ 番目の文字に該当する。これが $A$ となればよいから、その確率は $a_{k-1}$ である。

以上より、$k \ge 3$ において以下の漸化式が成り立つ。

$$ a_k = \frac{1}{2} a_{k-1} + \frac{1}{2} a_{k-2} $$

初期条件を求める。 1番目の文字が $A$ となるのは、1回目に事象 $X$ が起こるときであるから、$a_1 = \frac{1}{2}$ である。 2番目の文字が $A$ となるのは、1回目に事象 $X$ が起こる（確率 $\frac{1}{2}$）、または、1回目に事象 $Y$ が起こり2回目に事象 $X$ が起こる（確率 $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$）ときであるから、

$$ a_2 = \frac{1}{2} + \frac{1}{4} = \frac{3}{4} $$

である。

漸化式の特性方程式 $x^2 - \frac{1}{2}x - \frac{1}{2} = 0$ の解は $x = 1, -\frac{1}{2}$ である。これを用いて漸化式を変形すると、以下の2式を得る。

$$ a_k - a_{k-1} = -\frac{1}{2} (a_{k-1} - a_{k-2}) \quad \cdots ① $$

$$ a_k + \frac{1}{2} a_{k-1} = a_{k-1} + \frac{1}{2} a_{k-2} \quad \cdots ② $$

①より、数列 $\{ a_k - a_{k-1} \}$ は初項 $a_2 - a_1 = \frac{3}{4} - \frac{1}{2} = \frac{1}{4}$、公比 $-\frac{1}{2}$ の等比数列であるから、

$$ a_k - a_{k-1} = \frac{1}{4} \left( -\frac{1}{2} \right)^{k-2} = \left( -\frac{1}{2} \right)^2 \left( -\frac{1}{2} \right)^{k-2} = \left( -\frac{1}{2} \right)^k \quad \cdots ③ $$

②より、数列 $\left\{ a_k + \frac{1}{2} a_{k-1} \right\}$ はすべての項が等しい定数数列であるから、

$$ a_k + \frac{1}{2} a_{k-1} = a_2 + \frac{1}{2} a_1 = \frac{3}{4} + \frac{1}{4} = 1 \quad \cdots ④ $$

④から③を引いて、

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

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

添字をずらして $k-1$ を $n$ に置き換えると、求める確率は

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

(2)

左から $k-1$ 番目の文字が $A$ であり、かつ $k$ 番目の文字が $B$ となる確率を $b_k$ ($k \ge 2$) とおく。 (1)と同様に最初の1回目の試行で場合分けを行う。$k \ge 4$ とする。

（i） 1回目に事象 $X$ が起こる場合（確率 $\frac{1}{2}$）元の文字列の $k-1$ 番目と $k$ 番目は、残りの文字列の $k-3$ 番目と $k-2$ 番目に該当するため、条件を満たす確率は $b_{k-2}$ である。

（ii） 1回目に事象 $Y$ が起こる場合（確率 $\frac{1}{2}$）元の文字列の $k-1$ 番目と $k$ 番目は、残りの文字列の $k-2$ 番目と $k-1$ 番目に該当するため、条件を満たす確率は $b_{k-1}$ である。

よって、$k \ge 4$ において以下の漸化式が成り立つ。

$$ b_k = \frac{1}{2} b_{k-1} + \frac{1}{2} b_{k-2} $$

初期条件を求める。文字 $A$ は必ず $AA$ のペアで現れるため、1番目が $A$ で2番目が $B$ となることはなく、$b_2 = 0$ である。 2番目が $A$ で3番目が $B$ となるのは、1回目に事象 $X$ ($AA$ を追加) が起こり、2回目に文字 $B$ を追加する事象（確率 $\frac{1}{6}$）が起こる場合のみであるから、

$$ b_3 = \frac{1}{2} \times \frac{1}{6} = \frac{1}{12} $$

である。

(1)と同様に漸化式を変形すると、以下の2式を得る。

$$ b_k - b_{k-1} = -\frac{1}{2} (b_{k-1} - b_{k-2}) $$

$$ b_k + \frac{1}{2} b_{k-1} = b_{k-1} + \frac{1}{2} b_{k-2} $$

数列 $\{ b_k - b_{k-1} \}$ の初項は $b_3 - b_2 = \frac{1}{12} - 0 = \frac{1}{12}$ であるから、

$$ b_k - b_{k-1} = \frac{1}{12} \left( -\frac{1}{2} \right)^{k-3} \quad \cdots ⑤ $$

数列 $\left\{ b_k + \frac{1}{2} b_{k-1} \right\}$ の値は一定であり、その値は $b_3 + \frac{1}{2} b_2 = \frac{1}{12} + 0 = \frac{1}{12}$ であるから、

$$ b_k + \frac{1}{2} b_{k-1} = \frac{1}{12} \quad \cdots ⑥ $$

⑥から⑤を引いて、

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

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

添字をずらして $k-1$ を $n$ に置き換えると、

$$ b_n = \frac{1}{18} \left\{ 1 - \left( -\frac{1}{2} \right)^{n-2} \right\} $$

これは $n=2$ のとき $b_2 = \frac{1}{18} (1 - 1) = 0$ となり初期条件も満たすため、$n \ge 2$ のすべての整数について成り立つ。

解法2

1回の試行で追加される文字列を1つの「ブロック」と呼ぶ。文字列の左からちょうど $k$ 文字のところでブロックが終了する（切れ目がある）確率を $p_k$ とする。さいころを1回投げるごとに、確率 $\frac{1}{2}$ で長さ2のブロックが、確率 $\frac{1}{2}$ で長さ1のブロックが追加される。ちょうど $k$ 文字でブロックが終了するのは、最後に長さ1のブロックが追加される（直前は $k-1$ 文字目で終了）か、最後に長さ2のブロックが追加される（直前は $k-2$ 文字目で終了）のいずれかであるから、$k \ge 2$ のとき

$$ p_k = \frac{1}{2} p_{k-1} + \frac{1}{2} p_{k-2} $$

が成り立つ。 0文字のところには必ず切れ目があると考えて $p_0 = 1$、1文字目で終了するのは最初に長さ1のブロックが出る場合であるから $p_1 = \frac{1}{2}$ である。

漸化式を変形して一般項を求める。

$$ p_k - p_{k-1} = -\frac{1}{2} (p_{k-1} - p_{k-2}) $$

$$ p_k + \frac{1}{2} p_{k-1} = p_{k-1} + \frac{1}{2} p_{k-2} $$

数列 $\{ p_k - p_{k-1} \}$ は初項 $p_1 - p_0 = -\frac{1}{2}$、公比 $-\frac{1}{2}$ の等比数列であるから、

$$ p_k - p_{k-1} = \left( -\frac{1}{2} \right)^k $$

数列 $\left\{ p_k + \frac{1}{2} p_{k-1} \right\}$ は一定で $p_1 + \frac{1}{2} p_0 = 1$ であるから、

$$ p_k + \frac{1}{2} p_{k-1} = 1 $$

2式から $p_k$ を消去すると、

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

$$ p_k = \frac{2}{3} \left\{ 1 - \left( -\frac{1}{2} \right)^{k+1} \right\} \quad (k \ge 0) $$

(1)

$n$ 番目の文字が $A$ となるのは、以下のいずれかの場合である。

(ア)

$n-1$ 文字目でブロックが終了し、次に $AA$ が追加される。このとき、$n$ 番目が $AA$ の1文字目となる。 (イ)

$n-2$ 文字目でブロックが終了し、次に $AA$ が追加される。このとき、$n$ 番目が $AA$ の2文字目となる。

(ア), (イ) は排反であるから、$n \ge 2$ のとき求める確率は、

$$ p_{n-1} \times \frac{1}{2} + p_{n-2} \times \frac{1}{2} = \frac{1}{2} \left[ \frac{2}{3} \left\{ 1 - \left( -\frac{1}{2} \right)^n \right\} + \frac{2}{3} \left\{ 1 - \left( -\frac{1}{2} \right)^{n-1} \right\} \right] $$

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

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

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

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

$n=1$ のとき、確率は最初の試行で $AA$ が出る $\frac{1}{2}$ であり、この式は $n=1$ でも成り立つ。

(2)

$n-1$ 番目が $A$ かつ $n$ 番目が $B$ となるのは、文字列 $AA$ と $B$ がこの順で連続して現れ、$B$ がちょうど $n$ 番目にあるときである。すなわち、$n-3$ 文字目でブロックが終了し、次に $AA$ が追加され、その次に $B$ が追加される場合である。 $n \ge 3$ のとき、この確率は

$$ p_{n-3} \times \frac{1}{2} \times \frac{1}{6} = \frac{1}{12} p_{n-3} $$

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

$n=2$ のとき、確率は $0$ であり、この式は $n=2$ でも成り立つ。

解説

長さが1または2増える試行を繰り返すタイプの確率問題は、漸化式を用いるのが定石である。解法1のように「最初の1回目の試行で場合分けする」手法は、元の問題と相似な構造を作り出せるため汎用性が高く、有力な解法となる。解法2のように「特定の文字数でブロックの切れ目が発生する確率」を求める手法も、事象の構造を視覚的に捉えやすく直感的である。どちらの手法でも同じ形の三項間漸化式に帰着するため、使い慣れた手法で確実に計算を進めることが重要である。