トップ› 北海道大学› 2003年› 理系第4問

北海道大学 2003年理系第4問解説

方針・初手

$n$ 回の移動において、正の向きに移動する回数を $k$ 回とすると、負の向きには $n-k$ 回移動することになる。このときの点 $P$ の座標 $X(n)$ を $k$ と $n$ で表すことから始める。各移動は独立であり、正の向き、負の向きに進む確率はともに $\frac{1}{2}$ であるため、反復試行の確率を用いる。

解法1

(1)

$8$ 回の移動のうち、正の向きに $k$ 回（$0 \leqq k \leqq 8$）移動したとする。負の向きには $8-k$ 回移動するので、点 $P$ の座標 $X(8)$ は $$ X(8) = k \cdot 1 + (8-k) \cdot (-1) = 2k - 8 $$ と表される。

$X(8) = 2$ となるとき、 $$ 2k - 8 = 2 $$ $$ 2k = 10 $$ $$ k = 5 $$ したがって、正の向きに $5$ 回、負の向きに $3$ 回移動すればよい。

求める確率は、反復試行の確率より $$ {}_{8}\mathrm{C}_{5} \left( \frac{1}{2} \right)^5 \left( \frac{1}{2} \right)^3 = 56 \times \left( \frac{1}{2} \right)^8 = \frac{56}{256} = \frac{7}{32} $$

(2)

$7$ 回の移動のうち、正の向きに $k$ 回（$0 \leqq k \leqq 7$）移動したとすると、点 $P$ の座標 $X(7)$ は $$ X(7) = k \cdot 1 + (7-k) \cdot (-1) = 2k - 7 $$ となる。この事象が起こる確率は $$ {}_{7}\mathrm{C}_{k} \left( \frac{1}{2} \right)^7 $$ である。

$|X(7)| = |2k - 7|$ の取り得る値と、そのときの確率を計算する。

$k=0$ のとき $|-7| = 7$, 確率は ${}_{7}\mathrm{C}_{0} \left( \frac{1}{2} \right)^7$
$k=1$ のとき $|-5| = 5$, 確率は ${}_{7}\mathrm{C}_{1} \left( \frac{1}{2} \right)^7$
$k=2$ のとき $|-3| = 3$, 確率は ${}_{7}\mathrm{C}_{2} \left( \frac{1}{2} \right)^7$
$k=3$ のとき $|-1| = 1$, 確率は ${}_{7}\mathrm{C}_{3} \left( \frac{1}{2} \right)^7$
$k=4$ のとき $|1| = 1$, 確率は ${}_{7}\mathrm{C}_{4} \left( \frac{1}{2} \right)^7$
$k=5$ のとき $|3| = 3$, 確率は ${}_{7}\mathrm{C}_{5} \left( \frac{1}{2} \right)^7$
$k=6$ のとき $|5| = 5$, 確率は ${}_{7}\mathrm{C}_{6} \left( \frac{1}{2} \right)^7$
$k=7$ のとき $|7| = 7$, 確率は ${}_{7}\mathrm{C}_{7} \left( \frac{1}{2} \right)^7$

${}_{7}\mathrm{C}_{k} = {}_{7}\mathrm{C}_{7-k}$ であり、$|2k-7| = |2(7-k)-7|$ が成り立つため、確率は対称になる。

求める期待値 $E$ は、 $$ \begin{aligned} E &= \sum_{k=0}^{7} |2k - 7| \cdot {}_{7}\mathrm{C}_{k} \left( \frac{1}{2} \right)^7 \\ &= 2 \sum_{k=4}^{7} (2k - 7) \cdot {}_{7}\mathrm{C}_{k} \left( \frac{1}{2} \right)^7 \\ &= 2 \left( 1 \cdot {}_{7}\mathrm{C}_{4} + 3 \cdot {}_{7}\mathrm{C}_{5} + 5 \cdot {}_{7}\mathrm{C}_{6} + 7 \cdot {}_{7}\mathrm{C}_{7} \right) \left( \frac{1}{2} \right)^7 \end{aligned} $$ 組み合わせの値を計算すると、${}_{7}\mathrm{C}_{4} = 35, {}_{7}\mathrm{C}_{5} = 21, {}_{7}\mathrm{C}_{6} = 7, {}_{7}\mathrm{C}_{7} = 1$ であるから、 $$ \begin{aligned} E &= 2 (1 \cdot 35 + 3 \cdot 21 + 5 \cdot 7 + 7 \cdot 1) \times \frac{1}{128} \\ &= 2 (35 + 63 + 35 + 7) \times \frac{1}{128} \\ &= 2 \times 140 \times \frac{1}{128} \\ &= \frac{280}{128} \\ &= \frac{35}{16} \end{aligned} $$

(3)

$6$ 回の移動が終わった時点で、一度も $O$ （座標 $0$）に戻らない確率を求める。各回の移動方向を順に並べた場合の数は全部で $2^6 = 64$ 通りあり、これらは同様に確からしい。

一度も原点に戻らないのは、「常に正の領域にいる（$X(1) > 0, \cdots, X(6) > 0$）」または「常に負の領域にいる（$X(1) < 0, \cdots, X(6) < 0$）」のいずれかである。この2つの事象の確率は対称性により等しい。

常に正の領域にいる経路の数を数える。 $t$ 回目の移動後の座標を $x$ としたとき、そのような状態に至る経路の数を $N(t, x)$ とする。 $t=1$ のとき、正の領域にいるので $x=1$。$N(1, 1) = 1$。以降、$N(t+1, x) = N(t, x-1) + N(t, x+1)$ （ただし $x > 0$）を用いて計算する。

$t=2$: $N(2, 2) = N(1, 1) = 1$
$t=3$: $N(3, 1) = N(2, 2) = 1$ $N(3, 3) = N(2, 2) = 1$
$t=4$: $N(4, 2) = N(3, 1) + N(3, 3) = 1 + 1 = 2$ $N(4, 4) = N(3, 3) = 1$
$t=5$: $N(5, 1) = N(4, 2) = 2$ $N(5, 3) = N(4, 2) + N(4, 4) = 2 + 1 = 3$ $N(5, 5) = N(4, 4) = 1$
$t=6$: $N(6, 2) = N(5, 1) + N(5, 3) = 2 + 3 = 5$ $N(6, 4) = N(5, 3) + N(5, 5) = 3 + 1 = 4$ $N(6, 6) = N(5, 5) = 1$

よって、常に正の領域にいる経路の総数は $5 + 4 + 1 = 10$ 通りである。

同様に、常に負の領域にいる経路も $10$ 通りあるため、一度も原点に戻らない経路の総数は $$ 10 + 10 = 20 \text{ （通り）} $$ 求める確率は、 $$ \frac{20}{64} = \frac{5}{16} $$

解法2

(3) の別解

余事象「$6$ 回の移動のうちに、一度でも $O$ に戻る」確率を求める。 $n$ 回目の移動後に初めて $O$ に戻るとする。移動距離の和が偶数にならないと原点に戻れないため、$n$ は偶数、すなわち $n=2, 4, 6$ のいずれかである。

全事象の数は $2^6 = 64$ 通りである。

(i) 初めて $O$ に戻るのが $2$ 回目のとき

$2$ 回目までの移動は（正、負）か（負、正）の $2$ 通りである。 $3$ 回目から $6$ 回目までの移動は制限がないため $2^4 = 16$ 通り。よって、この場合の数は $$ 2 \times 16 = 32 \text{ （通り）} $$

(ii) 初めて $O$ に戻るのが $4$ 回目のとき

$2$ 回目では $O$ に戻らず、$4$ 回目で初めて $O$ に戻る経路を考える。 $1$ 回目は正・負の $2$ 通り。対称性から $1$ 回目が正の場合を考えると、$X(1)=1$ であり、途中で $0$ にならないためには $X(2)=2, X(3)=1, X(4)=0$ となる経路の $1$ 通りのみである。よって、$4$ 回目で初めて $O$ に戻る経路は $1$ 回目が負の場合と合わせて $2$ 通りである。残りの $5, 6$ 回目の移動は自由なので $2^2 = 4$ 通り。よって、この場合の数は $$ 2 \times 4 = 8 \text{ （通り）} $$

(iii) 初めて $O$ に戻るのが $6$ 回目のとき

$2, 4$ 回目で $O$ に戻らず、$6$ 回目で初めて $O$ に戻る経路を考える。 $1$ 回目が正の向きであると仮定する（後で $2$ 倍する）。 $X(1)=1$ から出発し、$X(2), \cdots, X(5)$ がすべて正で、$X(6)=0$ となる経路を数える。

$X(1)=1$
$X(2)=2$ （$0$ にならないため）
$X(3)=1$ または $3$
$X(4)=2$ または $4$ （$0$ にならないため）
$X(5)=1$ または $3$ または $5$

$X(6)=0$ になるためには $X(5)=1$ でなければならず、そこに至る経路は $X(3)=1 \to X(4)=2 \to X(5)=1$ と $X(3)=3 \to X(4)=2 \to X(5)=1$ の $2$ 通りである。負の向きから出発した場合も同様に $2$ 通りあるので、この場合の数は $$ 2 \times 2 = 4 \text{ （通り）} $$

(i), (ii), (iii) の事象は互いに排反であるから、一度でも $O$ に戻る経路の総数は $$ 32 + 8 + 4 = 44 \text{ （通り）} $$

したがって、一度も $O$ に戻らない経路の数は余事象を考えて $$ 64 - 44 = 20 \text{ （通り）} $$

よって、求める確率は $$ \frac{20}{64} = \frac{5}{16} $$

解説

ランダムウォーク（点の移動）に関する典型的な確率問題である。(1) は反復試行の確率の基本であり、確実に得点したい。(2) は絶対値がついた変数の期待値計算である。対称性をうまく利用すると、計算の手間を半分に減らすことができる。(3) は「一度も〜しない」という条件の扱い方がポイントになる。直接書き上げる（解法1）か、余事象を用いて「初めて条件を満たすタイミング」で場合分けして数え上げる（解法2）のが定石である。6回程度であれば経路を順に追って求めたほうがミスが少なく安全である。