東京工業大学 1987年 理系 第5問 解説

方針・初手

（1） は、境界に達する前の領域内での移動である。ルール(i) のみが適用されるため、原点からの反復試行の確率として処理する。

（2） は、境界に達した後のルール(ii) が関わる。点 $(n,2)$ に到達するためには、直線 $x=n$ 上の $y \le 2$ の領域に初めて到達し、その後まっすぐ上へ進むしかないことに着目する。

解法1

(1)

点 A が点 $(k,l)$ に到達するのは、$k, l \le n-1$ のとき、常にルール(i) が適用される。

原点から $(k,l)$ までの総移動回数は $k+l$ 回であり、そのうち $k$ 回が右方向、$l$ 回が上方向への移動である。

それぞれの移動の確率は独立に $\frac{1}{2}$ であるため、点 $(k,l)$ を通過する確率は反復試行の確率を用いて次のように表される。

$$ P(k,l) = {}_{k+l}\mathrm{C}_{k} \left( \frac{1}{2} \right)^{k+l} $$

(2)

点 A が $(n,2)$ を通過する条件を考える。

$n \ge 3$ であり、ルール(ii) により、A は直線 $x=n$ 上の点に到達すると、その後は確率 $1$ で $y$ 座標が増加する方向のみに進む。

したがって、点 $(n,2)$ を通過するためには、直線 $x=n$ に初めて到達する点が $(n,0), (n,1), (n,2)$ のいずれかでなければならない。

直線 $x=n$ に初めて到達する点ごとに場合分けをする。これらは互いに排反事象である。

（i） 直線 $x=n$ に点 $(n,0)$ で初めて到達する場合

点 $(n-1,0)$ まで移動し、そこから右へ $1$ 回移動すればよい。

その確率は (1) の結果を用いて、

$$ P(n-1,0) \times \frac{1}{2} = {}_{n-1}\mathrm{C}_{0} \left( \frac{1}{2} \right)^{n-1} \times \frac{1}{2} = \left( \frac{1}{2} \right)^n $$

（ii） 直線 $x=n$ に点 $(n,1)$ で初めて到達する場合

点 $(n-1,1)$ まで移動し、そこから右へ $1$ 回移動すればよい。

その確率は、

$$ P(n-1,1) \times \frac{1}{2} = {}_{n}\mathrm{C}_{1} \left( \frac{1}{2} \right)^n \times \frac{1}{2} = n \left( \frac{1}{2} \right)^{n+1} $$

（iii） 直線 $x=n$ に点 $(n,2)$ で初めて到達する場合

点 $(n-1,2)$ まで移動し、そこから右へ $1$ 回移動すればよい。

その確率は、

$$ P(n-1,2) \times \frac{1}{2} = {}_{n+1}\mathrm{C}_{2} \left( \frac{1}{2} \right)^{n+1} \times \frac{1}{2} = \frac{n(n+1)}{2} \left( \frac{1}{2} \right)^{n+2} $$

求める確率 $P(n,2)$ はこれらの和となる。

$$ \begin{aligned} P(n,2) &= \left( \frac{1}{2} \right)^n + n \left( \frac{1}{2} \right)^{n+1} + \frac{n(n+1)}{2} \left( \frac{1}{2} \right)^{n+2} \\ &= \frac{8}{2^{n+3}} + \frac{4n}{2^{n+3}} + \frac{n(n+1)}{2^{n+3}} \\ &= \frac{8 + 4n + n^2 + n}{2^{n+3}} \\ &= \frac{n^2+5n+8}{2^{n+3}} \end{aligned} $$

解説

境界におけるルールの変化を伴うランダムウォークの典型問題である。

(2) において、点 $(n,2)$ の直前の点が $(n-1,2)$ または $(n,1)$ であると考えて単純に和をとろうとすると、$(n,1)$ に到達する経緯によって確率が変わるため計算が複雑になる。直線 $x=n$ に到達した後は確率 $1$ で一直線に進む性質に気づけば、「直線 $x=n$ に侵入する直前の点」である $x=n-1$ 上の点に着目するのが最も見通しがよい。

このように、ルールの変わる境界線の「一歩手前」の状態で場合分けをする手法は、確率の問題で非常に有効な定石である。

答え

(1)

$$ P(k,l) = {}_{k+l}\mathrm{C}_{k} \left( \frac{1}{2} \right)^{k+l} $$

(2)

$$ P(n,2) = \frac{n^2+5n+8}{2^{n+3}} $$