トップ› 東京大学› 2015年› 文系第4問

東京大学 2015年文系第4問解説

方針・初手

コインを1回投げるごとに文字列の長さは1または2増えるため、$n$ 回コインを投げ終わった時点で文字列の長さは必ず $n$ 以上となる。したがって、文字列の左から $n$ 番目の文字は、高々 $n$ 回目までのコイントスの結果によって完全に確定する。よって、本問は「無限にコイントスを繰り返し、文字列を無限に伸ばしていく過程において、左から $n$ 番目の文字が何になるか」を考えることと同値である。

文字の並びには規則性があるため、漸化式を利用する。ここでは、各文字の位置における「状態」の推移に注目する解法1と、コイントスによって文字列が「区切られる」位置に注目する解法2を示す。

解法1

左から $k$ 番目の文字の状態として、次の3つを定義し、それぞれの状態になる確率を $a_{1,k}, a_{2,k}, b_k$ とおく。

$A_1$：「$AA$」の1文字目の $A$ である状態
$A_2$：「$AA$」の2文字目の $A$ である状態
$B$：「$B$」である状態

文字列が生成される規則から、以下の遷移が成り立つ。

$k$ 番目が $A_1$ ならば、同じトスで生成された $A$ が続くため、$k+1$ 番目は確率 $1$ で $A_2$ となる。
$k$ 番目が $A_2$ または $B$ ならば、そこで1回のトス結果が完了する。$k+1$ 番目は次のトスの最初の文字となるため、確率 $1/2$ で $A_1$ となり、確率 $1/2$ で $B$ となる。

これより、以下の連立漸化式が成り立つ。

$$ \begin{cases} a_{1,k+1} = \frac{1}{2} a_{2,k} + \frac{1}{2} b_k \\ a_{2,k+1} = a_{1,k} \\ b_{k+1} = \frac{1}{2} a_{2,k} + \frac{1}{2} b_k \end{cases} $$

1文字目は1回目のトスの結果で決まり、表なら $A_1$、裏なら $B$ となるため、初期状態は以下のようになる。

$$ a_{1,1} = \frac{1}{2}, \quad a_{2,1} = 0, \quad b_1 = \frac{1}{2} $$

連立漸化式の第1式と第3式から、任意の $k \ge 1$ について $a_{1,k+1} = b_{k+1}$ が成り立つ。したがって、$k \ge 2$ において $b_k = a_{1,k}$ である。また、任意の $k \ge 1$ に対して $a_{1,k} + a_{2,k} + b_k = 1$ が成り立つ。 $k \ge 2$ のとき、これらに $b_k = a_{1,k}$ および $a_{2,k} = a_{1,k-1}$ を代入すると、

$$ a_{1,k} + a_{1,k-1} + a_{1,k} = 1 $$

$$ 2a_{1,k} + a_{1,k-1} = 1 $$

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

これを変形すると、

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

となる。数列 $\left\{ a_{1,k} - \frac{1}{3} \right\}$ は、初項が $a_{1,1} - \frac{1}{3} = \frac{1}{2} - \frac{1}{3} = \frac{1}{6}$、公比が $-\frac{1}{2}$ の等比数列であるから、

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

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

この式は $k=1$ のとき $a_{1,1} = \frac{1}{2}$ となり成立する。また、$b_k = a_{1,k}$ は $k \ge 2$ で示されたが、$k=1$ のときも $b_1 = \frac{1}{2}, a_{1,1} = \frac{1}{2}$ で一致するため、任意の $k \ge 1$ について $b_k = \frac{1}{3} - \frac{1}{3} \left(-\frac{1}{2}\right)^k$ が成り立つ。

(1)

$n$ 番目の文字が $A$ となる確率は、余事象を用いて $1 - b_n$ として求められる。

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

(2)

$n-1$ 番目の文字が $A$ で、かつ $n$ 番目の文字が $B$ となるのは、$n-1$ 番目の状態が $A_1$ または $A_2$ であり、そこから $n$ 番目で状態 $B$ に遷移する事象である。 $n-1$ 番目が $A_1$ の場合、$n$ 番目は必ず $A_2$ となるため条件を満たさない。 $n-1$ 番目が $A_2$ の場合、次の遷移で確率 $\frac{1}{2}$ で $B$ となる。したがって、求める確率は $a_{2,n-1} \times \frac{1}{2}$ である。

$n=2$ のとき、$a_{2,1} = 0$ より確率は $0$ である。 $n \ge 3$ のとき、$a_{2,n-1} = a_{1,n-2} = \frac{1}{3} - \frac{1}{3} \left(-\frac{1}{2}\right)^{n-2}$ であるから、求める確率は

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

となる。この式に $n=2$ を代入すると $\frac{1}{6} - \frac{2}{3} \cdot \frac{1}{4} = 0$ となり、$n=2$ の場合も成立する。

解法2

文字列の左から $k$ 番目の文字と $k+1$ 番目の文字の間が、いずれかのコイントスによって生成された文字列の「区切り」となる事象を $E_k$ とし、その確率を $p_k$ とする。便宜上、文字列の先頭を「$0$ 番目の直後の区切り」と考え、$p_0 = 1$ とする。 1回目のトスで裏が出れば長さ1の文字 $B$ が生成され、1番目の直後が区切りとなるため、$p_1 = \frac{1}{2}$ である。

$k \ge 2$ について、$E_k$ が起こるのは、次の2つの排反な事象のいずれかである。 (i)

$k-1$ 番目の直後が区切りであり、次のトスで裏（$B$、長さ1）が出る。（確率 $\frac{1}{2}$） (ii)

$k-2$ 番目の直後が区切りであり、次のトスで表（$AA$、長さ2）が出る。（確率 $\frac{1}{2}$）

したがって、漸化式

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

が成り立つ。特性方程式 $x^2 - \frac{1}{2}x - \frac{1}{2} = 0$ より $(x-1)(2x+1) = 0$ となり、

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

と変形できる。階差数列が等比数列となるから、

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

$k \ge 1$ に対して一般項を求めると、

$$ \begin{aligned} p_k &= p_0 + \sum_{i=1}^k \left(-\frac{1}{2}\right)^i \\ &= 1 + \frac{-\frac{1}{2} \left\{ 1 - \left(-\frac{1}{2}\right)^k \right\}}{1 - \left(-\frac{1}{2}\right)} \\ &= 1 - \frac{1}{3} \left\{ 1 - \left(-\frac{1}{2}\right)^k \right\} \\ &= \frac{2}{3} + \frac{1}{3} \left(-\frac{1}{2}\right)^k \end{aligned} $$

この式は $k=0$ のときも成立する。

(1)

$n$ 番目の文字が $A$ となる事象の余事象は、$n$ 番目の文字が $B$ となる事象である。 $n$ 番目が $B$ となるのは、$n-1$ 番目の直後が区切りであり、その次のトスで裏（$B$）が出る場合である。その確率は $p_{n-1} \times \frac{1}{2}$ となる。したがって、求める確率は

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

(2)

$n-1$ 番目の文字が $A$ で、かつ $n$ 番目の文字が $B$ となる条件を考える。 $n$ 番目が $B$ であるためには、$n-1$ 番目の直後が区切りで、次に裏が出る必要がある。さらに、その直前にある $n-1$ 番目の文字が $A$ であるためには、直前のトスが表（$AA$）でなければならない。すなわち、$n \ge 3$ において「$n-3$ 番目の直後が区切りとなり、次に表（$AA$）が出て、その次に裏（$B$）が出る」ことが条件となる。この確率は、

$$ p_{n-3} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} \left\{ \frac{2}{3} + \frac{1}{3} \left(-\frac{1}{2}\right)^{n-3} \right\} = \frac{1}{6} + \frac{1}{12} \left(-\frac{1}{2}\right)^{-3} \left(-\frac{1}{2}\right)^n = \frac{1}{6} - \frac{2}{3} \left(-\frac{1}{2}\right)^n $$

$n=2$ のとき、1番目が $A$ であれば表が出ているため必ず2番目も $A$ となり、条件を満たすことは起こり得ない（確率$0$）。求めた式に $n=2$ を代入すると $\frac{1}{6} - \frac{2}{3} \cdot \frac{1}{4} = 0$ となり、一致する。したがって、求める確率は $\frac{1}{6} - \frac{2}{3} \left(-\frac{1}{2}\right)^n$ である。

解説

文字の追加という規則的な操作に対して、漸化式を立てて確率を求める典型的な問題である。解法1のように文字の「状態」に着目してマルコフ連鎖（推移確率）の連立漸化式を立てるアプローチと、解法2のように文字の長さ（区切りの位置）に着目して漸化式を立てるアプローチがあり、どちらもよく用いられる有効な手法である。 (2)において、「$n-1$ 番目が $A$ かつ $n$ 番目が $B$」という条件を、定義した状態や区切りの位置を用いて正しく言い換えられるかがポイントとなる。