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

方針・初手

点 $Q$ の移動は、直前の位置のみによって次の位置が決まるため、状態遷移図を描いて漸化式を立てるのが基本方針です。 $n$ 秒後に各頂点にいる確率をそれぞれ文字でおき、確率の和が $1$ であることや、図形の対称性（あるいは連立漸化式の和と差）を利用して一般項を求めます。 また、本問では「$x$ 軸方向の移動」と「$y$ 軸方向の移動」が独立に行われていると解釈できるため、各方向の移動回数に着目し、二項定理を用いて直接確率を求める別解も有効です。

解法1

$n$ 秒後に点 $Q$ が頂点 $A, B, C, D$ にいる確率をそれぞれ $a_n, b_n, c_n, d_n$ とする。 点 $Q$ は最初に頂点 $A$ にいるので、初期条件は以下の通りである。

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

また、任意の自然数 $n$ について、点 $Q$ はいずれかの頂点にいるため、以下の式が成り立つ。

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

点 $Q$ は $1$ 秒ごとに隣の頂点に移動する。 問題の条件より、$x$ 軸と平行な移動の確率は $p$、$y$ 軸と平行な移動の確率は $1-p$ である。 各頂点の座標から、隣接する頂点への移動確率は次のようになる。

• $x$ 軸に平行な移動（確率 $p$）：$A \leftrightarrow D$、および $B \leftrightarrow C$
• $y$ 軸に平行な移動（確率 $1-p$）：$A \leftrightarrow B$、および $C \leftrightarrow D$

したがって、$n+1$ 秒後の状態について、以下の連立漸化式が得られる。

$$ \begin{cases} a_{n+1} = (1-p)b_n + p d_n & \cdots \text{①} \\ b_{n+1} = (1-p)a_n + p c_n & \cdots \text{②} \\ c_{n+1} = p b_n + (1-p)d_n & \cdots \text{③} \\ d_{n+1} = p a_n + (1-p)c_n & \cdots \text{④} \end{cases} $$

和の漸化式を作る

①と③の辺々を加えると、次のようになる。

$$ a_{n+1} + c_{n+1} = (1-p+p)b_n + (p+1-p)d_n = b_n + d_n $$

ここで、$b_n + d_n = 1 - (a_n + c_n)$ であるから、

$$ a_{n+1} + c_{n+1} = 1 - (a_n + c_n) $$

これを変形すると、

$$ a_{n+1} + c_{n+1} - \frac{1}{2} = -\left( a_n + c_n - \frac{1}{2} \right) $$

となる。数列 $\left\{ a_n + c_n - \frac{1}{2} \right\}$ は、初項が $a_0 + c_0 - \frac{1}{2} = 1 + 0 - \frac{1}{2} = \frac{1}{2}$、公比が $-1$ の等比数列である。したがって、

$$ a_n + c_n - \frac{1}{2} = \frac{1}{2} \cdot (-1)^n $$

$$ a_n + c_n = \frac{1 + (-1)^n}{2} \quad \cdots \text{⑤} $$

差の漸化式を作る

次に、①と③の辺々を引き算すると、次のようになる。

$$ a_{n+1} - c_{n+1} = (1-2p)b_n - (1-2p)d_n = (1-2p)(b_n - d_n) \quad \cdots \text{⑥} $$

同様に、②と④の辺々を引き算すると、次のようになる。

$$ b_{n+1} - d_{n+1} = (1-2p)a_n - (1-2p)c_n = (1-2p)(a_n - c_n) \quad \cdots \text{⑦} $$

⑥の添字を $1$ つ進めた $a_{n+2} - c_{n+2} = (1-2p)(b_{n+1} - d_{n+1})$ に、⑦を代入する。

$$ a_{n+2} - c_{n+2} = (1-2p)^2 (a_n - c_n) $$

この漸化式は $n$ の偶奇によって分かれるため、場合分けを行う。

(i) $n$ が偶数のとき $n = 2m$ ($m$ は $0$ 以上の整数) とおく。 数列 $\{a_{2m} - c_{2m}\}$ は、初項が $a_0 - c_0 = 1 - 0 = 1$、公比が $(1-2p)^2$ の等比数列である。

$$ a_{2m} - c_{2m} = 1 \cdot \{ (1-2p)^2 \}^m = (1-2p)^{2m} $$

すなわち、$n$ が偶数のとき、

$$ a_n - c_n = (1-2p)^n \quad \cdots \text{⑧} $$

(ii) $n$ が奇数のとき $n = 2m+1$ ($m$ は $0$ 以上の整数) とおく。 数列 $\{a_{2m+1} - c_{2m+1}\}$ は、初項が $a_1 - c_1$、公比が $(1-2p)^2$ の等比数列である。 ここで、⑥に $n=0$ を代入すると $a_1 - c_1 = (1-2p)(b_0 - d_0) = 0$ となる。

$$ a_{2m+1} - c_{2m+1} = 0 \cdot \{ (1-2p)^2 \}^m = 0 $$

すなわち、$n$ が奇数のとき、

$$ a_n - c_n = 0 \quad \cdots \text{⑨} $$

以上より、$a_n, c_n$ を求める。

(ア) $n$ が偶数のとき ⑤より $a_n + c_n = 1$、⑧より $a_n - c_n = (1-2p)^n$ である。 これらを辺々加えて $2$ で割ると $a_n$ が、引いて $2$ で割ると $c_n$ が得られる。

$$ a_n = \frac{1 + (1-2p)^n}{2}, \quad c_n = \frac{1 - (1-2p)^n}{2} $$

(イ) $n$ が奇数のとき ⑤より $a_n + c_n = 0$、⑨より $a_n - c_n = 0$ である。 したがって、

$$ a_n = 0, \quad c_n = 0 $$

解法2

点 $Q$ が $1$ 秒ごとに隣の頂点へ移動する操作は、$x$ 座標と $y$ 座標の変化として独立に捉えることができる。 すなわち $1$ 回の移動につき、「$x$ 座標の値が入れ替わる（確率 $p$）」か、「$y$ 座標の値が入れ替わる（確率 $1-p$）」かのいずれかが必ず起こる。

$n$ 秒間の移動において、$x$ 座標が入れ替わる回数を $k$ 回（$0 \leqq k \leqq n$）とすると、$y$ 座標が入れ替わる回数は $n-k$ 回となる。 この事象が起こる確率は、反復試行の確率より

$$ {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

である。

初期位置は $A(0, 1)$ である。 $n$ 秒後に $x$ 座標が $0$ であるのは $x$ 座標の入れ替え回数 $k$ が偶数のときであり、$x$ 座標が $1$ であるのは $k$ が奇数のときである。 同様に、$n$ 秒後に $y$ 座標が $1$ であるのは $y$ 座標の入れ替え回数 $n-k$ が偶数のときであり、$y$ 座標が $0$ であるのは $n-k$ が奇数のときである。

これを踏まえ、$n$ 秒後に頂点 $A, C$ にいるための条件を考える。

(i) 頂点 $A(0, 1)$ にいる確率 $a_n$ について 点 $Q$ が $A(0, 1)$ にいるための条件は、$k$ が偶数かつ $n-k$ が偶数であることである。 これらが同時に成り立つためには、和である $n = k + (n-k)$ が偶数であることが必要である。 よって、$n$ が奇数のとき、条件を満たす $k$ は存在せず $a_n = 0$ となる。 一方、$n$ が偶数のとき、$k$ が偶数であれば自動的に $n-k$ も偶数となる。したがって、$a_n$ は「$k$ が偶数となる確率の和」として求められる。

$$ a_n = \sum_{\substack{0 \leqq k \leqq n \\ k\text{は偶数}}} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

(ii) 頂点 $C(1, 0)$ にいる確率 $c_n$ について 点 $Q$ が $C(1, 0)$ にいるための条件は、$k$ が奇数かつ $n-k$ が奇数であることである。 これらが同時に成り立つためには、和である $n$ が偶数であることが必要である。 よって、$n$ が奇数のとき、条件を満たす $k$ は存在せず $c_n = 0$ となる。 一方、$n$ が偶数のとき、$k$ が奇数であれば自動的に $n-k$ も奇数となる。したがって、$c_n$ は「$k$ が奇数となる確率の和」として求められる。

$$ c_n = \sum_{\substack{0 \leqq k \leqq n \\ k\text{は奇数}}} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

次に、二項定理を用いてこれらの和を計算する。 任意の $x, y$ に対して、二項定理より以下の式が成り立つ。

$$ (x+y)^n = \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} x^k y^{n-k} $$

ここで、$x=p, y=1-p$ とすると、

$$ (p + 1 - p)^n = \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

$$ 1 = \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} \quad \cdots \text{①} $$

また、$x=-p, y=1-p$ とすると、

$$ (-p + 1 - p)^n = \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} (-p)^k (1-p)^{n-k} $$

$$ (1-2p)^n = \sum_{k=0}^{n} {}_{n}\mathrm{C}_{k} (-1)^k p^k (1-p)^{n-k} \quad \cdots \text{②} $$

①と②の辺々を加えると、奇数番目の項が打ち消し合って偶数番目の項が $2$ 倍になって残る。

$$ 1 + (1-2p)^n = 2 \sum_{\substack{0 \leqq k \leqq n \\ k\text{は偶数}}} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

したがって、$n$ が偶数のとき、

$$ a_n = \frac{1 + (1-2p)^n}{2} $$

①から②の辺々を引くと、偶数番目の項が打ち消し合って奇数番目の項が $2$ 倍になって残る。

$$ 1 - (1-2p)^n = 2 \sum_{\substack{0 \leqq k \leqq n \\ k\text{は奇数}}} {}_{n}\mathrm{C}_{k} p^k (1-p)^{n-k} $$

したがって、$n$ が偶数のとき、

$$ c_n = \frac{1 - (1-2p)^n}{2} $$

以上より、$a_n$ と $c_n$ を求めることができた。

解説

状態遷移に基づく確率の問題（いわゆる「マルコフ連鎖」）の典型的な出題です。 解法1のように、$4$ 状態の確率を文字で置いて連立漸化式を立てるのがもっとも確実なアプローチです。和や差をとって特定の項だけを含む式を作る手法は、対称性を持つ図形上のランダムウォークで頻出の処理です。

また、本問の移動の性質に着目すると、解法2のように「$n$ 回の試行のうち、ある事象が起こる回数の偶奇」に帰着させることができます。二項定理を用いた $(x+y)^n \pm (x-y)^n$ の展開は、偶数番目・奇数番目の項だけを取り出して和を求める際の常套手段であり、この計算技術を習得していると見通しよく解き進めることができます。

答え

$n$ が偶数のとき $a_n = \frac{1 + (1-2p)^n}{2}, \quad c_n = \frac{1 - (1-2p)^n}{2}$

$n$ が奇数のとき $a_n = 0, \quad c_n = 0$