名古屋大学 2017年 理系 第2問 解説

方針・初手

頂点を点 A からの最短距離（辺をたどる回数）によって以下の4つのグループに分ける。

• グループ 0: 頂点 A
• グループ 1: 頂点 B, D, E （条件の $p_n$ に対応）
• グループ 2: 頂点 C, F, H （条件の $q_n$ に対応）
• グループ 3: 頂点 G （条件の $r_n$ に対応）

点 P は1回の移動で隣り合う頂点に等確率 $\frac{1}{3}$ で移動する。一度も A に戻らないという条件のもとで、各グループ間の推移確率を考え、連立漸化式を立てることから始める。

解法1

(1)

時刻 $n$ において点 P がグループ 1, 2, 3 にいる確率がそれぞれ $p_n, q_n, r_n$ である。 時刻 0 では頂点 A にいるため、時刻 1 で頂点 B, D, E にいる確率はそれぞれ $\frac{1}{3}$ であり、合計して $p_1 = 1$ である。 また、$q_1 = 0, r_1 = 0$ である。

自然数 $n \geqq 1$ に対して、時刻 $n$ から時刻 $n+1$ への推移を考える。

• グループ 1 (B, D, E) からは、確率 $\frac{1}{3}$ で頂点 A に戻り、確率 $\frac{2}{3}$ でグループ 2 (C, F, H) へ移動する。
• グループ 2 (C, F, H) からは、確率 $\frac{2}{3}$ でグループ 1 (B, D, E) へ移動し、確率 $\frac{1}{3}$ でグループ 3 (G) へ移動する。
• グループ 3 (G) からは、確率 1 でグループ 2 (C, F, H) へ移動する。

したがって、以下の連立漸化式が成り立つ。

$$ \begin{cases} p_{n+1} = \frac{2}{3} q_n \\ q_{n+1} = \frac{2}{3} p_n + r_n \\ r_{n+1} = \frac{1}{3} q_n \end{cases} $$

これを用いて順次計算する。 $n=1$ のとき、

$$ \begin{aligned} p_2 &= \frac{2}{3} q_1 = 0 \\ q_2 &= \frac{2}{3} p_1 + r_1 = \frac{2}{3} \cdot 1 + 0 = \frac{2}{3} \\ r_2 &= \frac{1}{3} q_1 = 0 \end{aligned} $$

$n=2$ のとき、

$$ \begin{aligned} p_3 &= \frac{2}{3} q_2 = \frac{2}{3} \cdot \frac{2}{3} = \frac{4}{9} \\ q_3 &= \frac{2}{3} p_2 + r_2 = 0 + 0 = 0 \\ r_3 &= \frac{1}{3} q_2 = \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{9} \end{aligned} $$

(2)

漸化式より、$n \geqq 1$ に対して以下の式が成り立つ。

$$ q_{n+2} = \frac{2}{3} p_{n+1} + r_{n+1} = \frac{2}{3} \left( \frac{2}{3} q_n \right) + \frac{1}{3} q_n = \frac{7}{9} q_n $$

$q_1 = 0$ であるから、奇数番目の項はすべて 0 となる。すなわち、自然数 $k \geqq 1$ に対して

$$ q_{2k-1} = 0 $$

また、$q_2 = \frac{2}{3}$ であるから、偶数番目の項は公比 $\frac{7}{9}$ の等比数列となり、自然数 $k \geqq 1$ に対して

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

これらを $p_{n+1} = \frac{2}{3} q_n$, $r_{n+1} = \frac{1}{3} q_n$ に代入する。 $n$ が偶数（$n=2k$、$k \geqq 1$）のとき、

$$ p_{2k} = \frac{2}{3} q_{2k-1} = 0 $$

$$ r_{2k} = \frac{1}{3} q_{2k-1} = 0 $$

$n$ が奇数（$n=2k+1$、$k \geqq 1$）のとき、

$$ p_{2k+1} = \frac{2}{3} q_{2k} = \frac{4}{9} \left( \frac{7}{9} \right)^{k-1} $$

$$ r_{2k+1} = \frac{1}{3} q_{2k} = \frac{2}{9} \left( \frac{7}{9} \right)^{k-1} $$

(3)

点 P が時刻 $2m$ で頂点 A に初めて戻る事象は、時刻 $2m-1$ まで一度も A に戻らずにグループ 1 (B, D, E) におり、時刻 $2m$ に確率 $\frac{1}{3}$ で A に移動する事象である。 したがって、

$$ s_m = p_{2m-1} \times \frac{1}{3} $$

となる。 $m=1$ のとき、$s_1 = p_1 \times \frac{1}{3} = 1 \times \frac{1}{3} = \frac{1}{3}$。 $m \geqq 2$ のとき、(2) の結果より $p_{2m-1} = \frac{4}{9} \left( \frac{7}{9} \right)^{m-2}$ であるから、

$$ s_m = \frac{4}{9} \left( \frac{7}{9} \right)^{m-2} \times \frac{1}{3} = \frac{4}{27} \left( \frac{7}{9} \right)^{m-2} $$

(4)

点 P は偶数時刻にしか頂点 A に存在し得ない。 時刻 $2m$ で頂点 A に戻るのがちょうど 2 回目となるためには、ある自然数 $k$ ($1 \leqq k \leqq m-1$) が存在して、時刻 $2k$ で初めて A に戻り、その後 $2(m-k)$ ステップ後に再出発して初めて A に戻ればよい。 このような確率は $s_k s_{m-k}$ であるから、求める確率 $t_m$ は

$$ t_m = \sum_{k=1}^{m-1} s_k s_{m-k} $$

である。

$m=2$ のとき、

$$ t_2 = s_1 s_1 = \frac{1}{3} \cdot \frac{1}{3} = \frac{1}{9} $$

このとき $s_2 = \frac{4}{27}$ であり、$\frac{1}{9} = \frac{3}{27} < \frac{4}{27}$ なので $t_2 < s_2$ は成立する。

$m=3$ のとき、

$$ t_3 = s_1 s_2 + s_2 s_1 = 2 \cdot \frac{1}{3} \cdot \frac{4}{27} = \frac{8}{81} $$

このとき $s_3 = \frac{4}{27} \left( \frac{7}{9} \right)^1 = \frac{28}{243}$ であり、$\frac{8}{81} = \frac{24}{243} < \frac{28}{243}$ なので $t_3 < s_3$ は成立する。

$m \geqq 4$ のとき、

$$ \begin{aligned} t_m &= s_1 s_{m-1} + s_{m-1} s_1 + \sum_{k=2}^{m-2} s_k s_{m-k} \\ &= 2 \cdot \frac{1}{3} \cdot \frac{4}{27} \left( \frac{7}{9} \right)^{m-3} + \sum_{k=2}^{m-2} \left\{ \frac{4}{27} \left( \frac{7}{9} \right)^{k-2} \cdot \frac{4}{27} \left( \frac{7}{9} \right)^{m-k-2} \right\} \\ &= \frac{8}{81} \left( \frac{7}{9} \right)^{m-3} + \sum_{k=2}^{m-2} \frac{16}{729} \left( \frac{7}{9} \right)^{m-4} \\ &= \frac{56}{729} \left( \frac{7}{9} \right)^{m-4} + (m-3) \frac{16}{729} \left( \frac{7}{9} \right)^{m-4} \\ &= \frac{16m+8}{729} \left( \frac{7}{9} \right)^{m-4} \\ &= \frac{8(2m+1)}{729} \left( \frac{7}{9} \right)^{m-4} \end{aligned} $$

一方、$s_m$ は

$$ s_m = \frac{4}{27} \left( \frac{7}{9} \right)^{m-2} = \frac{4}{27} \left( \frac{7}{9} \right)^2 \left( \frac{7}{9} \right)^{m-4} = \frac{196}{2187} \left( \frac{7}{9} \right)^{m-4} $$

$t_m < s_m$ となる条件を求めると、

$$ \frac{8(2m+1)}{729} \left( \frac{7}{9} \right)^{m-4} < \frac{196}{2187} \left( \frac{7}{9} \right)^{m-4} $$

両辺に $\frac{2187}{4} \left( \frac{9}{7} \right)^{m-4} > 0$ を掛けると、

$$ 6(2m+1) < 49 $$

$$ 12m < 43 $$

これを解くと $m < \frac{43}{12} = 3.58\dots$ となる。$m \geqq 4$ を満たす自然数 $m$ は存在しない。

以上より、$t_m < s_m$ を満たす自然数 $m \geqq 2$ は $m = 2, 3$ である。

解説

対称性を持つ立体図形上のランダムウォークの問題である。特定の頂点からの距離で状態をまとめ、吸収壁（頂点 A に戻ったらそこで追跡をやめる）を持つマルコフ連鎖として立式するのが定石である。 (4) では、マルコフ性（過去の履歴に関わらず、頂点 A にいるという現在の状態のみでその後の推移確率が定まること）を利用し、途中で A に戻る時刻で場合分けして積の和をとる。計算ミスを防ぐため、数列の初項の扱いや、和をとる範囲（$m=2, 3$ と $m \geqq 4$ でシグマの項が存在するかどうかの違い）に注意して場合分けを行うことが重要である。

答え

(1) $p_2 = 0, \quad q_2 = \frac{2}{3}, \quad r_2 = 0$ $p_3 = \frac{4}{9}, \quad q_3 = 0, \quad r_3 = \frac{2}{9}$

(2) $n$ が偶数（$n=2k, k=1,2,3,\dots$）のとき、 $p_{2k} = 0, \quad q_{2k} = \frac{2}{3} \left( \frac{7}{9} \right)^{k-1}, \quad r_{2k} = 0$

$n$ が奇数（$n=2k+1, k=1,2,3,\dots$）のとき、 $p_{2k+1} = \frac{4}{9} \left( \frac{7}{9} \right)^{k-1}, \quad q_{2k+1} = 0, \quad r_{2k+1} = \frac{2}{9} \left( \frac{7}{9} \right)^{k-1}$

(3) $m=1$ のとき $s_1 = \frac{1}{3}$ $m \geqq 2$ のとき $s_m = \frac{4}{27} \left( \frac{7}{9} \right)^{m-2}$

(4) $m = 2, 3$