東京大学 2015年度
理系数学 第2問

解答

(1)

左から $n$ 番目の文字が $A$ である確率を $a_n$ とする。1回の試行で書かれる文字数は $1$ または $2$ であるから、$n$ 回試行した時点で文字列の長さは少なくとも $n$ であり、左から $n$ 番目の文字はその後の試行に影響されない。

最初に $AA$ が書かれる確率は $\frac{3}{6}=\frac{1}{2}$ であり、長さ1の文字 $B,C,D$ のいずれかが書かれる確率も $\frac{3}{6}=\frac{1}{2}$ である。よって $a_1=\frac{1}{2}$ である。また、2番目の文字が $A$ であるのは、最初に $AA$ が書かれる場合、または最初に長さ1の文字が書かれて次に $AA$ が書かれる場合であるから $a_2=\frac{1}{2}+\frac{1}{2}\cdot \frac{1}{2}=\frac{3}{4}$ である。

$n\geqq 3$ のとき、最初に $AA$ が書かれた場合は残りの文字列の $n-2$ 番目、最初に長さ1の文字が書かれた場合は残りの文字列の $n-1$ 番目を見ればよい。したがって $a_n=\frac{1}{2}{a}_{n-2}+\frac{1}{2}{a}_{n-1}(n\geqq 3)$ である。特性方程式 $2{\lambda }^2=\lambda +1$ の解は $1,-1/2$ であるから $a_n=A+B{\left(-\frac{1}{2}\right)}^n$ と書ける。初期値 $a_1=1/2,a_2=3/4$ を代入して $A=\frac{2}{3},B=\frac{1}{3}$ を得る。したがって $\boxed{a_n=\frac{2}{3}+\frac{1}{3}{\left(-\frac{1}{2}\right)}^n}$ である。

(2)

左から $k$ 番目の文字の直後がブロックの切れ目である確率を $u_k$ とし、開始前も切れ目とみなして $u_0=1$ とする。$k=1$ では、最初のブロックが長さ1であればよいから $u_1=\frac{1}{2}$ である。$k\geqq 2$ では、最初のブロックの長さにより $u_k=\frac{1}{2}{u}_{k-1}+\frac{1}{2}{u}_{k-2}$ である。よって $u_k=\frac{2}{3}+\frac{1}{3}{\left(-\frac{1}{2}\right)}^k(k\geqq 0)$ となる。

$n=2$ のとき、1番目が $A$、2番目が $B$ となることはない。最初のブロックが $AA$ なら2番目は $A$、最初のブロックが長さ1なら1番目は $A$ でないからである。

$n\geqq 3$ とする。左から $n-1$ 番目が $A$、$n$ 番目が $B$ となるには、左から $n-3$ 番目の直後で切れ、その後に $AA$ が書かれ、さらに次に $B$ が書かれる必要がある。またこの条件は十分でもある。したがって求める確率は $u_{n-3}\cdot \frac{1}{2}\cdot \frac{1}{6}=\frac{1}{12}{u}_{n-3}$ である。ゆえに

である。

以上より求める確率は

である。