トップ› 京都大学› 1985年› 文系第5問

京都大学 1985年文系第5問解説

方針・初手

正六角形の頂点を移動するランダムウォークの問題である。まず、移動回数の偶奇によって到達可能な頂点が決まること（パリティ）に着目する。また、図形の対称性から、$A_1$ と $A_5$、$A_2$ と $A_4$ はそれぞれ $A_0$ や $A_3$ に対する条件が等しいため、同一の状態として扱うことができる。奇数回移動後の状態に注目し、$2$ 回の移動を $1$ つのステップと捉えて確率の漸化式を立てる。

解法1

出発点 $A_0$ からの移動回数を $k$ とすると、各頂点への到達可能性は以下のようになる。

$k$ が偶数のとき：頂点 $A_0, A_2, A_4$ のいずれかにいる。
$k$ が奇数のとき：頂点 $A_1, A_3, A_5$ のいずれかにいる。

ゲームが終了するのは頂点 $A_3$ に到達したときであるから、ゲームが終了する移動回数は必ず奇数回である。したがって、$k = 2n+1$ ($n \geqq 0$) 回移動してゲームが終了していない場合、点は必ず $A_1$ または $A_5$ にいる。この確率が $p_n$ である。

ここで、$n \geqq 1$ のとき、$(2n-1)$ 回目の移動後にゲームが終了していない状態から、さらに $2$ 回（$(2n)$ 回目、$(2n+1)$ 回目）移動した後の状態を考える。 $(2n-1)$ 回目の移動後、点は $A_1$ または $A_5$ にいる。図形の対称性から、どちらにいても以後の推移確率は同じであるため、$A_1$ にいる場合を考える。

$A_1$ から $2$ 回移動して、ゲームが終了しない（$A_1$ または $A_5$ にいる）確率を求める。

$1$ 回目に $A_0$ に移動（確率 $\frac{1}{2}$）した場合：次の移動で必ず $A_1$ か $A_5$ に行くため、確実にゲームは継続する。この遷移の確率は $\frac{1}{2} \times 1 = \frac{1}{2}$ である。
$1$ 回目に $A_2$ に移動（確率 $\frac{1}{2}$）した場合：次の移動で $\frac{1}{2}$ の確率で $A_1$ に戻りゲーム継続、$\frac{1}{2}$ の確率で $A_3$ に到達しゲーム終了となる。ゲームが継続する確率は $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ である。

よって、$A_1$ から $2$ 回移動してゲームが終了しない確率は $\frac{1}{2} + \frac{1}{4} = \frac{3}{4}$ である。ゆえに、以下の漸化式が成り立つ。

$$ p_n = \frac{3}{4} p_{n-1} \quad (n \geqq 1) $$

初期条件 $p_0$ は、$1$ 回の移動後にゲームが終了しない確率である。出発点 $A_0$ から $1$ 回移動すると必ず $A_1$ か $A_5$ に着くため、$p_0 = 1$ である。数列 $\{p_n\}$ は初項 $1$、公比 $\frac{3}{4}$ の等比数列となるから、

$$ p_n = \left(\frac{3}{4}\right)^n \quad (n \geqq 0) $$

次に、ちょうどゲームが終了する（$A_3$ に到達する）確率 $q_n$ を求める。

$(2n-1)$ 回目の移動後に $A_1$ にいる状態から、続く $2$ 回の移動でちょうど $A_3$ に到達するのは、$A_1 \to A_2 \to A_3$ と進む場合のみであり、その確率は $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ である。よって、$n \geqq 1$ のとき、ちょうど $(2n+1)$ 回目にゲームが終了する確率 $q_n$ は、

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

一方、$n=0$ のとき、$q_0$ はちょうど $1$ 回目の移動で $A_3$ に到達する確率である。$A_0$ から $1$ 回の移動で $A_3$ には到達できないため、

$$ q_0 = 0 $$

解説

等確率で隣接する頂点に移動するランダムウォークの典型問題である。本問のようにゴール（吸収状態）が決まっている場合、偶数回・奇数回での存在可能領域の絞り込み（パリティチェック）が非常に有効である。また、対称な位置にある頂点をグループ化して同一状態とみなすことで、考えるべき状態遷移を大幅に減らすことができる。今回は $(A_1, A_5)$ というグループにいる状態から、2ステップ後の状態を直接計算することで、連立漸化式を立てることなく簡潔に解答できる。$q_n$ において $n=0$ と $n \geqq 1$ で場合分けが生じる点に注意したい。