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

方針・初手

番号 $0$ の人と番号 $n$ の人が同じ色の旗をあげる確率 $P_n$ を求めるため、$n$ 番目の状態から $n+1$ 番目の状態への推移を考え、漸化式を立てる。各人が直前の人と同じ色をあげる確率が $p$、異なる色をあげる確率が $1-p$ であり、色は赤と白の2色のみであることに注目する。

解法1

番号 $0$ の人と番号 $n$ の人が同じ色の旗をあげる確率が $P_n$ である。このとき、番号 $0$ の人と番号 $n$ の人が異なる色の旗をあげる確率は $1 - P_n$ と表される。

次に、番号 $0$ の人と番号 $n+1$ の人が同じ色の旗をあげる場合について考える。これは以下の2つの排反な事象のいずれかが起こる場合である。

（i） 番号 $0$ の人と番号 $n$ の人が同じ色であり、かつ番号 $n+1$ の人が番号 $n$ の人と同じ色をあげる場合

（ii） 番号 $0$ の人と番号 $n$ の人が異なる色であり、かつ番号 $n+1$ の人が番号 $n$ の人と異なる色をあげる場合

それぞれの事象が起こる確率は、

（i） の確率は $P_n \times p$

（ii） の確率は $(1 - P_n) \times (1-p)$

これらは排反であるから、番号 $0$ の人と番号 $n+1$ の人が同じ色をあげる確率 $P_{n+1}$ は、これらの和となる。

$$ P_{n+1} = pP_n + (1-p)(1 - P_n) $$

これを整理する。

$$ P_{n+1} = pP_n + 1 - p - P_n + pP_n $$

$$ P_{n+1} = (2p - 1)P_n + 1 - p $$

この漸化式を変形するために、特性方程式 $\alpha = (2p - 1)\alpha + 1 - p$ を解くと $\alpha = \frac{1}{2}$ を得る。これを用いて漸化式を変形すると、以下のようになる。

$$ P_{n+1} - \frac{1}{2} = (2p - 1) \left( P_n - \frac{1}{2} \right) $$

ここで、初期条件として $n=0$ のときを考える。番号 $0$ の人と番号 $0$ の人は同一人物であるため、必ず同じ色になる。よって $P_0 = 1$ である。

数列 $\left\{ P_n - \frac{1}{2} \right\}$ は、初項 $P_0 - \frac{1}{2} = 1 - \frac{1}{2} = \frac{1}{2}$、公比 $2p - 1$ の等比数列である。

$$ P_n - \frac{1}{2} = \frac{1}{2} (2p - 1)^n $$

したがって、求める確率 $P_n$ は次のようになる。

$$ P_n = \frac{1}{2} \{ 1 + (2p - 1)^n \} $$

解法2

隣り合う2人の間で、旗の色が変わらないという事象を「同色」、旗の色が変わるという事象を「異色」と呼ぶことにする。問題の条件から、各ステップにおいて「同色」となる確率は $p$、「異色」となる確率は $1-p$ であり、各ステップは独立である。

番号 $0$ の人から番号 $n$ の人まで、合計 $n$ 回の推移が行われる。この $n$ 回の推移のうち、「異色」となった回数を $k$ 回とする。番号 $0$ の人と番号 $n$ の人が同じ色の旗をあげるのは、色が切り替わった回数 $k$ が偶数回（$0, 2, 4, \cdots$）のときである。

$n$ 回の推移で「異色」が $k$ 回起こる確率は、反復試行の確率により以下のように表される。

$$ {}_n\mathrm{C}_{k} (1-p)^k p^{n-k} $$

求める確率 $P_n$ は、$k$ が偶数となる確率の和である。

$$ P_n = \sum_{k\text{は偶数}} {}_n\mathrm{C}_{k} p^{n-k} (1-p)^k $$

ここで、二項定理を用いて $(p + (1-p))^n$ と $(p - (1-p))^n$ を展開する。

$$ 1^n = (p + 1 - p)^n = \sum_{k=0}^n {}_n\mathrm{C}_{k} p^{n-k} (1-p)^k $$

$$ (2p - 1)^n = (p - (1-p))^n = \sum_{k=0}^n {}_n\mathrm{C}_{k} p^{n-k} (-(1-p))^k = \sum_{k=0}^n {}_n\mathrm{C}_{k} p^{n-k} (1-p)^k (-1)^k $$

これら2つの式の辺々を加えると、$k$ が奇数の項は打ち消し合い、$k$ が偶数の項は2倍になって残る。

$$ 1 + (2p - 1)^n = 2 \sum_{k\text{は偶数}} {}_n\mathrm{C}_{k} p^{n-k} (1-p)^k $$

右辺のシグマの部分がまさに $P_n$ であるから、次が成り立つ。

$$ 1 + (2p - 1)^n = 2 P_n $$

よって、求める確率 $P_n$ は以下のようになる。

$$ P_n = \frac{1 + (2p - 1)^n}{2} $$

解説

状態遷移（マルコフ連鎖）に関する確率の典型問題である。本問のように「1つ前の状態のみに依存して次の状態が決まる」という設定では、確率の漸化式を立てる解法（解法1）が最も自然で確実である。

漸化式を立てる際は、番号 $0$ の人が赤をあげるか白をあげるかにかかわらず、その後の「色が一致するかどうか」の推移ルールが対称であることに気づくことがポイントである。そのため、それぞれの色に分けて考える必要はなく、「番号 $0$ と同じ色か、異なる色か」という2状態の推移のみを追えばよい。

また、解法2のように二項分布の偶数回の事象として捉える視点も、確率漸化式の問題でしばしば有効なアプローチである。二項定理を用いた奇偶の分離（偶数番目の項の和を求める手法）は難関大の入試で頻出であるため、定石として押さえておきたい。

答え

$$ P_n = \frac{1 + (2p - 1)^n}{2} $$