東京大学 2015年度
文系数学 第4問

解答

(1)

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

まず初期値を求める。1番目の文字が $A$ であるのは、最初に表が出て $AA$ が書かれる場合であるから $a_1=\frac{1}{2}$ である。2番目の文字が $A$ であるのは、最初に $AA$ が書かれる場合、または最初に $B$ が書かれ次に $AA$ が書かれる場合である。よって $a_2=\frac{1}{2}+\frac{1}{2}\cdot \frac{1}{2}=\frac{3}{4}$ である。

$n\geqq 3$ とする。最初に $AA$ が書かれた場合、全体の $n$ 番目は残りの文字列の $n-2$ 番目に対応する。最初に $B$ が書かれた場合、全体の $n$ 番目は残りの文字列の $n-1$ 番目に対応する。したがって $a_n=\frac{1}{2}{a}_{n-2}+\frac{1}{2}{a}_{n-1}(n\geqq 3)$ である。

この漸化式の定数解を $a_n=c$ とおくと $c=\frac{1}{2}c+\frac{1}{2}c$ だけでは $c$ は決まらないが、特性方程式は $2{\lambda }^2=\lambda +1,(\lambda -1)(2\lambda +1)=0$ である。よって $a_n=A+B{\left(-\frac{1}{2}\right)}^n$ と表せる。初期値から $A-\frac{1}{2}B=\frac{1}{2},A+\frac{1}{4}B=\frac{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文字目の直後が切れ目になるのは最初に $B$ が書かれる場合なので $u_1=\frac{1}{2}$ である。また $k\geqq 2$ では、最初に $B$ が書かれた場合は残りの $k-1$ 番目の直後、最初に $AA$ が書かれた場合は残りの $k-2$ 番目の直後を見ればよい。したがって $u_k=\frac{1}{2}{u}_{k-1}+\frac{1}{2}{u}_{k-2}(k\geqq 2)$ である。$u_0=1,u_1=1/2$ から、(1)と同じ形を解いて $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$、最初が $B$ なら1番目が $A$ でない。

$n\geqq 3$ とする。$AB$ という並びは、$AA$ の2文字目の直後に $B$ が続く場合に限って現れる。したがって、左から $n-1$ 番目が $A$、$n$ 番目が $B$ となるには、左から $n-3$ 番目の直後でいったん切れ、その後に $AA$、さらに $B$ が続けばよい。この確率は $u_{n-3}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}{u}_{n-3}$ である。ゆえに

である。

以上より求める確率は

である。