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

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

方針・初手

状態遷移を漸化式の形で整理し、順次計算していく。(1) は定義に従って直接確率を計算する。(2) はすべての自然数 $n$ についての命題であるため、数学的帰納法による証明が有効である。(3) は (2) の結果を利用し、$p_n(0)$ が $q$ の値に依存しないことを踏まえ、計算が容易な特定の $q$ の値を代入して問題を単純化（ランダムウォークに帰着）するのがよい見通しである。

解法1

(1)

初期状態は $n=0$ において $x=0$ であるから、 $$ p_0(0) = 1 $$ $$ p_0(m) = 0 \quad (m \neq 0) $$ である。規則に従い、確率を順次計算する。

$n=1$ のとき、規則(ii)より、 $$ p_1(1) = q $$ $$ p_1(-1) = 1-q $$ これ以外の $m$ では $p_1(m) = 0$ となる。

$n=2$ のとき、規則(i)より $x=\pm 1$ からの遷移を考えて、 $$ p_2(2) = p_1(1) \cdot \frac{1}{2} = \frac{q}{2} $$ $$ p_2(0) = p_1(1) \cdot \frac{1}{2} + p_1(-1) \cdot \frac{1}{2} = \frac{q}{2} + \frac{1-q}{2} = \frac{1}{2} $$ $$ p_2(-2) = p_1(-1) \cdot \frac{1}{2} = \frac{1-q}{2} $$ これ以外の $m$ では $p_2(m) = 0$ となる。

$n=3$ のとき、求めるのは $p_3(1)$ と $p_3(-1)$ である。 $x=1$ へ推移するのは、$n=2$ において $x=0$ または $x=2$ の場合であるから、 $$ p_3(1) = p_2(0) \cdot q + p_2(2) \cdot \frac{1}{2} = \frac{1}{2}q + \frac{q}{4} = \frac{3}{4}q $$ $x=-1$ へ推移するのは、$n=2$ において $x=0$ または $x=-2$ の場合であるから、 $$ p_3(-1) = p_2(0) \cdot (1-q) + p_2(-2) \cdot \frac{1}{2} = \frac{1}{2}(1-q) + \frac{1-q}{4} = \frac{3}{4}(1-q) $$

したがって、求める和は、 $$ p_3(1) + p_3(-1) = \frac{3}{4}q + \frac{3}{4}(1-q) = \frac{3}{4} $$

(2)

すべての自然数 $n$ と、任意の整数 $m$ に対して、「$p_n(m) + p_n(-m)$ が $q$ に依存しない一定値となる」という命題を、$n$ に関する数学的帰納法を用いて証明する。

(I) $n=1$ のとき $m=0$ ならば、$p_1(0) + p_1(-0) = 0 + 0 = 0$ $m=1, -1$ ならば、$p_1(1) + p_1(-1) = q + (1-q) = 1$ $|m| \geqq 2$ ならば、$p_1(m) + p_1(-m) = 0 + 0 = 0$ いずれの整数 $m$ に対しても $q$ に依存しない。よって、$n=1$ のとき命題は成り立つ。

(II) $n=k$ ($k$ は自然数) のとき成り立つと仮定する。すなわち、任意の整数 $l$ に対して、$p_k(l) + p_k(-l)$ が $q$ に依存しないと仮定する。 $n=k+1$ のときを考える。

$m=0$ の場合：状態の推移から、 $$ p_{k+1}(0) = p_k(1) \cdot \frac{1}{2} + p_k(-1) \cdot \frac{1}{2} = \frac{1}{2} \{ p_k(1) + p_k(-1) \} $$ 帰納法の仮定より、$p_k(1) + p_k(-1)$ は $q$ に依存しないため、$p_{k+1}(0)$ も $q$ に依存しない。よって、$p_{k+1}(0) + p_{k+1}(-0) = 2p_{k+1}(0)$ は $q$ に依存しない。

$m=1$ の場合：状態の推移から、 $$ p_{k+1}(1) = p_k(0) \cdot q + p_k(2) \cdot \frac{1}{2} $$ $$ p_{k+1}(-1) = p_k(0) \cdot (1-q) + p_k(-2) \cdot \frac{1}{2} $$ 辺々を加えると、 $$ p_{k+1}(1) + p_{k+1}(-1) = p_k(0) (q + 1 - q) + \frac{1}{2} \{ p_k(2) + p_k(-2) \} = p_k(0) + \frac{1}{2} \{ p_k(2) + p_k(-2) \} $$ ここで、$p_k(0) = \frac{1}{2} \{ p_k(0) + p_k(-0) \}$ と見なせるから、帰納法の仮定より $p_k(0)$ は $q$ に依存しない。また、仮定より $p_k(2) + p_k(-2)$ も $q$ に依存しない。したがって、$p_{k+1}(1) + p_{k+1}(-1)$ は $q$ に依存しない。 $m=-1$ の場合も、和は $p_{k+1}(-1) + p_{k+1}(1)$ となり同様に $q$ に依存しない。

$m \geqq 2$ の場合：状態の推移から、 $$ p_{k+1}(m) = p_k(m-1) \cdot \frac{1}{2} + p_k(m+1) \cdot \frac{1}{2} $$ $$ p_{k+1}(-m) = p_k(-m+1) \cdot \frac{1}{2} + p_k(-m-1) \cdot \frac{1}{2} $$ 辺々を加えると、 $$ p_{k+1}(m) + p_{k+1}(-m) = \frac{1}{2} \{ p_k(m-1) + p_k(-(m-1)) \} + \frac{1}{2} \{ p_k(m+1) + p_k(-(m+1)) \} $$ 帰納法の仮定より、右辺の各項である $p_k(m-1) + p_k(-(m-1))$ と $p_k(m+1) + p_k(-(m+1))$ はいずれも $q$ に依存しないため、$p_{k+1}(m) + p_{k+1}(-m)$ も $q$ に依存しない。 $m \leqq -2$ の場合も和の順序が変わるだけで同様である。

以上より、$n=k+1$ のときも命題は成り立つ。

(I), (II) より、すべての自然数 $n$ と任意の整数 $m$ に対して、$p_n(m) + p_n(-m)$ は $q$ によらないことが示された。

(3)

(2) の結果において $m=0$ とすると、$p_n(0) + p_n(0) = 2p_n(0)$ が $q$ に依存しないことが分かる。すなわち、$p_n(0)$ の値は $q$ の値に依存しない。したがって、$p_n(0)$ を求めるにあたり、$q$ を任意の値に設定して計算しても一般性を失わない。ここで、計算を最も単純化できる $q = \frac{1}{2}$ の場合を考える。

$q = \frac{1}{2}$ とすると、規則(i)と(ii)は統合され、「任意の時刻において、1秒後に $+1$ または $-1$ 移動する確率が常にそれぞれ $\frac{1}{2}$ である」という単純な1次元ランダムウォークの問題となる。

$x=0$ から出発して $n$ 秒後に $x=0$ にいる確率は、$n$ 回の移動のうち、正の方向への移動回数と負の方向への移動回数が等しい確率に帰着する。

(i) $n$ が奇数のとき総移動回数が奇数であれば、正の方向と負の方向への移動回数が等しくなることはないため、$x=0$ に戻ることは不可能である。よって、 $$ p_n(0) = 0 $$

(ii) $n$ が偶数のとき $n = 2k$ ($k$ は $0$ 以上の整数) とおく。 $2k$ 回の移動のうち、$k$ 回が正方向、$k$ 回が負方向であればよい。これは反復試行の確率として計算でき、 $$ p_{2k}(0) = {}_{2k}\mathrm{C}_{k} \left( \frac{1}{2} \right)^k \left( \frac{1}{2} \right)^k = {}_{2k}\mathrm{C}_{k} \frac{1}{2^{2k}} $$ したがって、偶数 $n$ に対しては、 $$ p_n(0) = {}_{n}\mathrm{C}_{\frac{n}{2}} \frac{1}{2^n} = \frac{n!}{\left( \frac{n}{2} \right)!^2} \frac{1}{2^n} $$

解説

本問は確率過程（ランダムウォーク）を題材にした問題である。 (1) で具体的な遷移を計算することで問題のルールを把握させると同時に、(2) で証明すべき予想を裏付ける設計となっている。最大のポイントは、(2) で示された「$p_n(0)$ は $q$ に依存しない」という強力な事実を (3) で活用できるかである。まともに漸化式を解いて $p_n(0)$ を求めようとすると非常に煩雑な計算を強いられるが、$q$ に依存しないのであれば、都合の良い $q = \frac{1}{2}$ を代入してしまえばよいという発想に至れば、(3) は教科書レベルの反復試行の基本問題として瞬時に解決する。問題の構成（誘導）の意図を正確に読み取ることが求められる良問である。