東京大学 2000年 文系 第3問 解説

方針・初手

動点 X が1秒後に他の頂点へ移動する確率がそれぞれ等しいことから、状態遷移に関する漸化式を立てる。すべての頂点に存在する確率の和が $1$ であることを利用すると、特定の頂点に存在する確率のみを用いた隣接2項間漸化式に帰着できる。

解法1

動点 X は $1$ 秒ごとに他の $3$ つの頂点へ等確率で移動するため、ある頂点から別の特定の頂点へ移動する確率はすべて $\frac{1}{3}$ である。

$n+1$ 秒後に動点 X が頂点 $A_i$ ($i = 1, 2, 3, 4$) に存在する事象は、$n$ 秒後に $A_i$ 以外の $3$ つの頂点のいずれかに存在し、そこから $A_i$ へ移動することである。したがって、次が成り立つ。

$$ P_i(n+1) = \frac{1}{3} \sum_{j \neq i} P_j(n) $$

また、動点 X は常に $4$ つの頂点のいずれかに存在するため、すべての確率の和は常に $1$ である。

$$ P_1(n) + P_2(n) + P_3(n) + P_4(n) = 1 $$

これを用いると、$\sum_{j \neq i} P_j(n) = 1 - P_i(n)$ となるから、先ほどの漸化式は次のように変形できる。

$$ P_i(n+1) = \frac{1}{3} \{ 1 - P_i(n) \} $$

$$ P_i(n+1) = -\frac{1}{3} P_i(n) + \frac{1}{3} $$

この漸化式を変形すると、以下のようになる。

$$ P_i(n+1) - \frac{1}{4} = -\frac{1}{3} \left( P_i(n) - \frac{1}{4} \right) $$

よって、数列 $\left\{ P_i(n) - \frac{1}{4} \right\}$ は、初項が $P_i(0) - \frac{1}{4}$、公比が $-\frac{1}{3}$ の等比数列であるから、一般項は次のように表される。

$$ P_i(n) - \frac{1}{4} = \left( P_i(0) - \frac{1}{4} \right) \left( -\frac{1}{3} \right)^n $$

$$ P_i(n) = \frac{1}{4} + \left( P_i(0) - \frac{1}{4} \right) \left( -\frac{1}{3} \right)^n $$

ここで、$i = 1$ のとき、与えられた初期条件 $P_1(0) = \frac{1}{4}$ を代入する。

$$ P_1(n) = \frac{1}{4} + \left( \frac{1}{4} - \frac{1}{4} \right) \left( -\frac{1}{3} \right)^n $$

$$ P_1(n) = \frac{1}{4} $$

次に、$i = 2$ のとき、初期条件 $P_2(0) = \frac{1}{2}$ を代入する。

$$ P_2(n) = \frac{1}{4} + \left( \frac{1}{2} - \frac{1}{4} \right) \left( -\frac{1}{3} \right)^n $$

$$ P_2(n) = \frac{1}{4} + \frac{1}{4} \left( -\frac{1}{3} \right)^n $$

解説

正多面体上のランダムウォーク（動点の移動）に関する典型問題である。頂点間の移動確率が対称であることを利用し、$P_1(n) + P_2(n) + P_3(n) + P_4(n) = 1$ を用いて自分自身だけの漸化式を作るのが定石の処理である。

$P_1(0) = \frac{1}{4}$ の場合、定常状態（極限としての確率）である $\frac{1}{4}$ と初期状態が一致しているため、時間 $n$ が経過しても確率が変化せず常に $\frac{1}{4}$ となることが計算結果からも確認できる。

答え

$$ P_1(n) = \frac{1}{4} $$

$$ P_2(n) = \frac{1}{4} + \frac{1}{4} \left( -\frac{1}{3} \right)^n $$