トップ› 東京大学› 2006年› 理系第2問

東京大学 2006年理系第2問解説

方針・初手

直前の記号と同じ記号が続く確率が $p$、異なる記号に変わる確率が $1-p$ である。求める事象は「新たに表示される×が2個に達する前に、新たに表示される◯が $n$ 個になる」ことである。さらに、条件を満たして操作が終了する瞬間、最後に表示される記号は必ず「◯」であることに着目する。途中で×が何回（0回または1回）、どのタイミングで出るかによって排反な事象に分類し、それぞれの確率を求めて足し合わせる直接計算（解法1）と、状態を定義して漸化式を立てる手法（解法2）の2通りで解説する。

解法1

最初に表示されている記号「×」を初期状態とし、それ以降に新たに記号が表示される推移を考える。同じ記号が続く確率は $p$、異なる記号に変わる確率は $1-p$ である。

(1)

$n=2$ のとき、×が2個（初期の1個を含めると3個）になる前に、◯が2個出ればよい。最後に出る記号は必ず◯であるため、新たに出る記号の並びは以下の3つの排反なパターンのいずれかである。

（i）新たに ◯、◯ と出る場合記号の推移は × $\to$ ◯ $\to$ ◯ となる。 ×から◯へ変わる確率が $1-p$、◯が続く確率が $p$ であるから、この確率は

$$ (1-p)p $$

（ii）新たに ×、◯、◯ と出る場合記号の推移は × $\to$ × $\to$ ◯ $\to$ ◯ となる。 ×が続く確率が $p$、×から◯へ変わる確率が $1-p$、◯が続く確率が $p$ であるから、この確率は

$$ p(1-p)p = p^2(1-p) $$

（iii）新たに ◯、×、◯ と出る場合記号の推移は × $\to$ ◯ $\to$ × $\to$ ◯ となる。すべて異なる記号に切り替わるため、この確率は

$$ (1-p)(1-p)(1-p) = (1-p)^3 $$

これらは互いに排反であるから、求める確率 $P_2$ は

$$ \begin{aligned} P_2 &= (1-p)p + p^2(1-p) + (1-p)^3 \\ &= (1-p) \{ p + p^2 + (1-p)^2 \} \\ &= (1-p) (2p^2 - p + 1) \end{aligned} $$

(2)

$n \geqq 3$ のときも同様に、新たに表示される×の個数と位置で場合分けを行う。

（i）新たに×が0個出る場合記号の推移は、初期の×から◯に変わり、その後◯が $n-1$ 回連続する。この確率は

$$ (1-p)p^{n-1} $$

（ii）新たに×が1個出る場合新たに表示される記号は合計 $n+1$ 個であり、そのうち1個が×、$n$ 個が◯である。最後は必ず◯であるため、×は1個目から $n$ 個目のいずれかに出る。

（ii-a） 1個目が×の場合記号の推移は × $\to$ × $\to$ ◯ $\to$ ◯ $\to \cdots \to$ ◯ となる。最初の×から×へ続く確率が $p$、×から◯へ変わる確率が $1-p$、その後◯が $n-1$ 回続く確率が $p^{n-1}$ であるから、この確率は

$$ p(1-p)p^{n-1} = p^n(1-p) $$

（ii-b） $k$ 個目 ($2 \leqq k \leqq n$) が×の場合記号の推移は、最初に◯が $k-1$ 個出た後、×が1個出て、その後◯が $n-k+1$ 個出る形となる。推移における記号の切り替わりと確率は以下のようになる。

×から◯へ変わる（確率 $1-p$）
◯が $k-2$ 回続く（確率 $p^{k-2}$）
◯から×へ変わる（確率 $1-p$）
×から◯へ変わる（確率 $1-p$）
◯が $n-k$ 回続く（確率 $p^{n-k}$）

これらの積をとると、確率は

$$ (1-p) \cdot p^{k-2} \cdot (1-p) \cdot (1-p) \cdot p^{n-k} = (1-p)^3 p^{n-2} $$

この確率は $k$ の値に依存しない。$k$ は $2$ から $n$ までの $n-1$ 通りあるので、これらの確率の和は

$$ (n-1)(1-p)^3 p^{n-2} $$

（i）と（ii）は互いに排反であるから、

$$ \begin{aligned} P_n &= (1-p)p^{n-1} + p^n(1-p) + (n-1)(1-p)^3 p^{n-2} \\ &= p^{n-2}(1-p) \{ p + p^2 + (n-1)(1-p)^2 \} \\ &= p^{n-2}(1-p) \{ p + p^2 + (n-1)(1 - 2p + p^2) \} \\ &= p^{n-2}(1-p) \{ np^2 - (2n-3)p + n - 1 \} \end{aligned} $$

解法2

事象の推移を状態に分けて漸化式を立てる。ある時点での「新たに表示された◯の個数」を $k$ とし、その時点での状態に対する確率を以下のように定義する。

$A_k$ : 新たに出た×が0個で、◯が $k$ 個出ており、直前の記号が◯である確率
$B_k$ : 新たに出た×が1個で、◯が $k$ 個出ており、直前の記号が×である確率
$C_k$ : 新たに出た×が1個で、◯が $k$ 個出ており、直前の記号が◯である確率

求める確率 $P_n$ は、$k=n$ となり終了条件を満たす確率であるため、$P_n = A_n + C_n$ となる。

初期状態（$k=0$）から最初の◯が出る（$k=1$）までの遷移を考える。 $A_1$ は、初期の×から直接◯に変わる場合であるため、

$$ A_1 = 1-p $$

$B_0$ は、初期の×から続けて×が出る場合であるため、

$$ B_0 = p $$

$C_1$ は、$B_0$ の状態から次に◯に変わる場合のみであるため、

$$ C_1 = B_0 \times (1-p) = p(1-p) $$

$k \geqq 1$ のときの推移について、以下の漸化式が成り立つ。 $A_{k+1}$ は $A_k$ から◯が続く場合なので、

$$ A_{k+1} = p A_k $$

$B_k$ は $A_k$ から×に変わる場合なので、

$$ B_k = (1-p) A_k $$

$C_{k+1}$ は、$C_k$ から◯が続く場合、または $B_k$ から◯に変わる場合であるため、

$$ C_{k+1} = p C_k + (1-p) B_k $$

これらの漸化式を解く。 $A_{k+1} = p A_k$ と $A_1 = 1-p$ より、

$$ A_k = (1-p)p^{k-1} $$

これより $B_k$ は、

$$ B_k = (1-p)^2 p^{k-1} $$

これを $C_{k+1}$ の漸化式に代入すると、

$$ C_{k+1} = p C_k + (1-p)^3 p^{k-1} $$

両辺を $p^{k+1}$ で割ると、

$$ \frac{C_{k+1}}{p^{k+1}} = \frac{C_k}{p^k} + \frac{(1-p)^3}{p^2} $$

よって、数列 $\left\{ \frac{C_k}{p^k} \right\}$ は初項 $\frac{C_1}{p} = 1-p$、公差 $\frac{(1-p)^3}{p^2}$ の等差数列であるから、

$$ \begin{aligned} \frac{C_n}{p^n} &= (1-p) + (n-1) \frac{(1-p)^3}{p^2} \\ C_n &= p^n(1-p) + (n-1)p^{n-2}(1-p)^3 \end{aligned} $$

したがって、求める確率 $P_n$ は

$$ \begin{aligned} P_n &= A_n + C_n \\ &= (1-p)p^{n-1} + p^n(1-p) + (n-1)p^{n-2}(1-p)^3 \\ &= p^{n-2}(1-p) \{ p + p^2 + (n-1)(1-2p+p^2) \} \\ &= p^{n-2}(1-p) \{ np^2 - (2n-3)p + n - 1 \} \end{aligned} $$

$n=2$ のとき、この式は $(1-p)(2p^2 - p + 1)$ となり、(1) の結果と一致する。

解説

記号が変化するかどうかに依存して確率が決まるマルコフ連鎖の問題である。終了条件である「×が3個出るよりも前に、◯が $n$ 個出る」という事象は、言い換えると「新たに表示される×が0個または1個の状態で、◯が $n$ 個出る」となる。また、その条件を満たして終了する瞬間の記号は必ず「◯」であることに気づくことが最大のポイントである。場合分けをして直接確率を計算する解法と、状態遷移図を描いて漸化式を立てる解法の2つが考えられる。本問程度であれば直接計算が手早いが、より複雑な条件になった場合は漸化式を立てる解法が強力な武器となる。