東京大学 1993年 理系 第5問 解説

方針・初手

列 $S$ の各文字（桁）はそれぞれ独立に書き写されると考えられる。したがって、列全体が一致する確率を直接考えるのではなく、ある1つの文字に注目し、それが $n$ 回目の書き写しにおいて元の文字と一致する確率を求めるのが定石である。 $S$ は $1$ が3個、$0$ が2個からなる列であるため、初期状態が $1$ である文字が $n$ 回後に $1$ である確率と、初期状態が $0$ である文字が $n$ 回後に $0$ である確率をそれぞれ漸化式を用いて求め、極限をとればよい。

解法1

列の各文字が書き写される過程は互いに独立であるとする。

ある文字に注目したとき、$n$ 回目の書き写しでその文字が $1$ である確率を $x_n$、$0$ である確率を $y_n$ とする。 問題の条件より、$n+1$ 回目の確率は $n$ 回目の確率を用いて次のように表される。

$$ \begin{cases} x_{n+1} = (1-q)x_n + p y_n \\ y_{n+1} = q x_n + (1-p)y_n \end{cases} $$

また、常に $x_n + y_n = 1$ が成り立つ。

（i） 最初が $1$ である文字について

$n$ 回目に $1$ である（すなわち元の文字と一致する）確率を $p_n$ とおくと、$x_n = p_n, y_n = 1 - p_n$ である。上の漸化式より、

$$ p_{n+1} = (1-q)p_n + p(1-p_n) = (1-p-q)p_n + p $$

これが成り立つ。変形して、

$$ p_{n+1} - \frac{p}{p+q} = (1-p-q) \left( p_n - \frac{p}{p+q} \right) $$

最初の状態は $1$ であるから $p_0 = 1$ とする。よって、

$$ p_n - \frac{p}{p+q} = (1-p-q)^n \left( 1 - \frac{p}{p+q} \right) = (1-p-q)^n \frac{q}{p+q} $$

ここで、$0 < p < 1$ かつ $0 < q < 1$ より $0 < p+q < 2$ であるから、$-1 < 1-p-q < 1$ となる。 したがって、$\lim_{n \to \infty} (1-p-q)^n = 0$ であり、

$$ \lim_{n \to \infty} p_n = \frac{p}{p+q} $$

（ii） 最初が $0$ である文字について

$n$ 回目に $0$ である（すなわち元の文字と一致する）確率を $q_n$ とおく。（i） と同様に漸化式を立てると、

$$ q_{n+1} = (1-p)q_n + q(1-q_n) = (1-p-q)q_n + q $$

変形して、

$$ q_{n+1} - \frac{q}{p+q} = (1-p-q) \left( q_n - \frac{q}{p+q} \right) $$

初期状態は $0$ であるから $q_0 = 1$ であり、

$$ q_n - \frac{q}{p+q} = (1-p-q)^n \left( 1 - \frac{q}{p+q} \right) = (1-p-q)^n \frac{p}{p+q} $$

（i） と同様に $\lim_{n \to \infty} (1-p-q)^n = 0$ であるから、

$$ \lim_{n \to \infty} q_n = \frac{q}{p+q} $$

$S_n$ が $S$ と完全に一致するのは、元の $S$ に含まれる $1$（3個）と $0$（2個）のすべてが $n$ 回目に元の文字と一致する場合である。 各文字の書き間違えは独立に起こるため、$S_n$ が $S$ に一致する確率 $C(n)$ は、

$$ C(n) = (p_n)^3 (q_n)^2 $$

と表される。極限の性質より、

$$ \lim_{n \to \infty} C(n) = \lim_{n \to \infty} \left( p_n^3 q_n^2 \right) = \left( \lim_{n \to \infty} p_n \right)^3 \left( \lim_{n \to \infty} q_n \right)^2 $$

これに上で求めた極限値を代入して、

$$ \lim_{n \to \infty} C(n) = \left( \frac{p}{p+q} \right)^3 \left( \frac{q}{p+q} \right)^2 = \frac{p^3 q^2}{(p+q)^5} $$

を得る。

解説

2状態（$0$ と $1$）の推移を扱う、マルコフ連鎖の典型的な問題である。全体を一つの事象と捉えるのではなく、各文字が独立に変化することを見抜き、1文字ごとの確率の漸化式に帰着させることが最大のポイントである。 十分な回数を経た後における特定の桁が $1$ または $0$ になる確率は、初期状態に依存せず推移確率のみで定まる。これは $\lim_{n \to \infty} p_n$ や $\lim_{n \to \infty} q_n$ の値が、推移の割合で按分された形になっていることからも見て取れる。

答え

$$ \frac{p^3 q^2}{(p+q)^5} $$