トップ› 名古屋大学› 1995年› 理系第4問

名古屋大学 1995年理系第4問解説

方針・初手

問題文の移動ルールから、4地点を結ぶ4本の道の配置を特定し、各地点からの遷移確率を漸化式で表す。 $A$ からは $B$ へのみ移動できるため、$A$ と $B$ は1本の道で結ばれている。 $B$ からは $A$ へ確率 $1/3$、$C$ へ確率 $2/3$ で移動するため、$B$ と $A$ は1本、$B$ と $C$ は2本の道で結ばれている。この時点で道は合計3本であり、残り1本は $D$ につながる道となる。$D$ へ移動できるのは $C$ からのみと考えられるため、$C$ と $D$ は1本の道で結ばれている。したがって、$C$ からは $B$ へ確率 $2/3$、$D$ へ確率 $1/3$ で移動する。これらを用いて確率の連立漸化式を立てる。

解法1

動点 $X$ が $n$ ステップ後に地点 $A, B, C, D$ にある確率をそれぞれ $a_n, b_n, c_n, d_n$ とする。出発点は $A$ であるから、初期状態は以下の通りである。

$$ a_0 = 1, \quad b_0 = 0, \quad c_0 = 0, \quad d_0 = 0 $$

方針で考察した道の繋がりから、各地点での移動確率は次のようになる。

$A$ にいるとき：確率 $1$ で $B$ へ移動する。
$B$ にいるとき：確率 $\frac{1}{3}$ で $A$ へ、確率 $\frac{2}{3}$ で $C$ へ移動する。
$C$ にいるとき：確率 $\frac{2}{3}$ で $B$ へ、確率 $\frac{1}{3}$ で $D$ へ移動する。
$D$ にいるとき：確率 $1$ で $D$ にとどまる。

これより、$n \geqq 1$ において以下の漸化式が成り立つ。

$$ \begin{cases} a_n = \frac{1}{3} b_{n-1} \\ b_n = a_{n-1} + \frac{2}{3} c_{n-1} \\ c_n = \frac{2}{3} b_{n-1} \\ d_n = d_{n-1} + \frac{1}{3} c_{n-1} \end{cases} $$

(1)

漸化式を用いて、$n=1, 2, 3, 4$ のときの各確率を順に計算する。

$n=1$ のとき

$$ \begin{aligned} a_1 &= \frac{1}{3} b_0 = 0 \\ b_1 &= a_0 + \frac{2}{3} c_0 = 1 + 0 = 1 \\ c_1 &= \frac{2}{3} b_0 = 0 \\ d_1 &= d_0 + \frac{1}{3} c_0 = 0 \end{aligned} $$

$n=2$ のとき

$$ \begin{aligned} a_2 &= \frac{1}{3} b_1 = \frac{1}{3} \\ b_2 &= a_1 + \frac{2}{3} c_1 = 0 + 0 = 0 \\ c_2 &= \frac{2}{3} b_1 = \frac{2}{3} \\ d_2 &= d_1 + \frac{1}{3} c_1 = 0 \end{aligned} $$

$n=3$ のとき

$$ \begin{aligned} a_3 &= \frac{1}{3} b_2 = 0 \\ b_3 &= a_2 + \frac{2}{3} c_2 = \frac{1}{3} + \frac{2}{3} \cdot \frac{2}{3} = \frac{7}{9} \\ c_3 &= \frac{2}{3} b_2 = 0 \\ d_3 &= d_2 + \frac{1}{3} c_2 = 0 + \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{9} \end{aligned} $$

$n=4$ のとき

$$ \begin{aligned} a_4 &= \frac{1}{3} b_3 = \frac{7}{27} \\ b_4 &= a_3 + \frac{2}{3} c_3 = 0 + 0 = 0 \\ c_4 &= \frac{2}{3} b_3 = \frac{14}{27} \\ d_4 &= d_3 + \frac{1}{3} c_3 = \frac{2}{9} + 0 = \frac{2}{9} \end{aligned} $$

よって、$b_1 = 1, b_2 = 0, b_3 = \frac{7}{9}, b_4 = 0$ である。

(2)

すべての非負整数 $k$ について、「$b_{2k} = 0$ かつ $a_{2k+1} = 0$ かつ $c_{2k+1} = 0$」が成り立つことを数学的帰納法で示す。

(i) $k=0$ のとき $b_0 = 0$ であり、(1) の結果より $a_1 = 0, c_1 = 0$ であるから成り立つ。

(ii) $k=m$（$m \geqq 0$）のとき $b_{2m} = 0$, $a_{2m+1} = 0$, $c_{2m+1} = 0$ が成り立つと仮定する。 $k=m+1$ のときを考えると、漸化式より

$$ b_{2(m+1)} = b_{2m+2} = a_{2m+1} + \frac{2}{3} c_{2m+1} = 0 + 0 = 0 $$

さらに、

$$ a_{2(m+1)+1} = a_{2m+3} = \frac{1}{3} b_{2m+2} = 0 $$

$$ c_{2(m+1)+1} = c_{2m+3} = \frac{2}{3} b_{2m+2} = 0 $$

となり、$k=m+1$ のときも成り立つ。

(i), (ii) より、すべての非負整数 $k$ に対して $b_{2k} = 0$ が成り立つ。したがって、$n$ が偶数のとき $b_n = 0$ である。

(3)

(2) の結果と漸化式から、$b_n$ についての漸化式を導く。 $n \geqq 2$ に対して、

$$ \begin{aligned} b_n &= a_{n-1} + \frac{2}{3} c_{n-1} \\ &= \frac{1}{3} b_{n-2} + \frac{2}{3} \left( \frac{2}{3} b_{n-2} \right) \\ &= \frac{7}{9} b_{n-2} \end{aligned} $$

が成り立つ。 (2) より $n$ が偶数のときは $b_n = 0$ であるため、$n$ が奇数のときを考える。 $n=2k-1$（$k=1, 2, 3, \dots$）とおくと、

$$ b_{2k-1} = \frac{7}{9} b_{2k-3} $$

となり、数列 $\{b_{2k-1}\}$ は初項 $b_1 = 1$、公比 $\frac{7}{9}$ の等比数列である。よって、

$$ b_{2k-1} = 1 \cdot \left( \frac{7}{9} \right)^{k-1} = \left( \frac{7}{9} \right)^{k-1} $$

となる。次に、$a_n, c_n$ の極限を考える。 $n$ が奇数のときは(2)の証明より $a_n = 0, c_n = 0$ である。 $n$ が偶数（$n=2k$）のとき、

$$ a_{2k} = \frac{1}{3} b_{2k-1} = \frac{1}{3} \left( \frac{7}{9} \right)^{k-1} $$

$$ c_{2k} = \frac{2}{3} b_{2k-1} = \frac{2}{3} \left( \frac{7}{9} \right)^{k-1} $$

となる。ここで、$k \to \infty$ のとき（すなわち $n \to \infty$ のとき）、$\left( \frac{7}{9} \right)^{k-1} \to 0$ であるから、偶奇によらず

$$ \lim_{n \to \infty} a_n = 0, \quad \lim_{n \to \infty} b_n = 0, \quad \lim_{n \to \infty} c_n = 0 $$

が成り立つ。動点 $X$ はいずれかの地点に必ず存在するため、全確率の和は常に $1$ であり、すべての $n$ に対して

$$ a_n + b_n + c_n + d_n = 1 $$

が成り立つ。したがって、極限をとると

$$ \lim_{n \to \infty} d_n = 1 - \lim_{n \to \infty} (a_n + b_n + c_n) = 1 - 0 = 1 $$

となる。

解説

図が与えられていないものの、ルールの記述から道の接続関係を復元する点が最初の関門である。「道の本数に応じて」という条件と、Bからの遷移確率が1/3と2/3であることから、Bには合計3本の道が繋がっていると判断できる。同様に全体で4本の道という条件と吸収状態Dの存在から、A-B（1本）、B-C（2本）、C-D（1本）というグラフ構造が特定できる。 (2)では、偶数ステップと奇数ステップで到達可能な状態が完全に分かれることを数式で示す。帰納法を用いると見通しよく証明できる。 (3)は、1ステップごとのDへの到達確率の無限和（等比級数）を計算しても良いが、全確率の和が1である性質を利用すると、A, B, Cにいる確率が $n \to \infty$ で0に収束することから逆算でき、計算量が大きく減る。