確率論の問題

方針. $(X_1,\dots ,X_{10})$ の $2^{10}=1024$ 通りの符号列は同様に確からしく、それぞれが点 $(k,S_k)$ を結んだ折れ線（経路）に $1$ 対 $1$ に対応する。そこで、最大値が $4$ 以上になる経路の本数を反射原理で数える。

手順 1：終点で分ける. 経路の終点 $S_{10}$ は偶数で、$S_{10}=j$ となる経路の本数は、上向きの歩数が $\frac{10+j}{2}$ なので ${}_{10}{\mathrm{C}}_{\frac{10+j}{2}}$ である。

• $S_{10}\ge 4$ の経路は、必ず高さ $4$ に到達しているので、すべて数える。
• $S_{10}<4$ の経路のうち、高さ $4$ に到達するものを数える必要がある。

手順 2：反射原理. $S_{10}=j<4$ で高さ $4$ に到達する経路について、初めて高さ $4$ に到達した時刻以降の部分を直線 $y=4$ に関して折り返す。すると終点は $8-j>4$ となる経路が得られる。逆に終点が $4$ より大きい経路は必ず高さ $4$ を通るので、初めて $4$ に達した時刻以降を折り返せばもとに戻る。したがって
$$\#\{S_{10}<4\text{ かつ高さ }4\text{ に到達}\}=\#\{S_{10}>4\}$$
が成り立つ。

手順 3：数える.
- $\#\{S_{10}=4\}={}_{10}{\mathrm{C}}_7=120$
- $\#\{S_{10}>4\}={}_{10}{\mathrm{C}}_8+{}_{10}{\mathrm{C}}_9+{}_{10}{\mathrm{C}}_{10}=45+10+1=56$

最大値が $4$ 以上の経路の本数は
$$\#\{S_{10}\ge 4\}+\#\{S_{10}>4\}=(120+56)+56=232$$
である。

手順 4：確率にする.
$$P\left(\underset{0\le k\le 10}{\max }{S}_k\ge 4\right)=\frac{232}{1024}=\frac{29}{128}$$

（一般に $P({\max }_{k\le n}{S}_k\ge a)=P(S_n=a)+2P(S_n>a)$ が成り立つ。）

反射原理を使う。最大値 $M={\max }_{0\le k\le 10}{S}_k$ について、$a=4$ のとき $P(M\ge a)=P(S_{10}\ge a)+P(S_{10}>a)$ が成り立つ。

$S_{10}=2j-10$ である（$j$ は $+1$ の個数）。$S_{10}$ は偶数値のみをとり、$P(S_{10}=2j-10)=\left(\genfrac{}{}{0ex}{}{10}{j}\right)/2^{10}$ である。

• $S_{10}=4$ ($j=7$): $\left(\genfrac{}{}{0ex}{}{10}{7}\right)=120$
• $S_{10}=6$ ($j=8$): $\left(\genfrac{}{}{0ex}{}{10}{8}\right)=45$
• $S_{10}=8$ ($j=9$): $\left(\genfrac{}{}{0ex}{}{10}{9}\right)=10$
• $S_{10}=10$ ($j=10$): $1$

よって $P(S_{10}>4)=(45+10+1)/1024=56/1024$、$P(S_{10}\ge 4)=(120+56)/1024=176/1024$ である。

$P(M\ge 4)=(176+56)/1024=232/1024=\frac{29}{128}$。

検算: 初めて水準 4 に達するまでの道は、$S_{10}>4$ の道と $S_{10}=4$ の道と、反射した $S_{10}<4$ の道（$S_{10}>4$ の道と 1 対 1 対応）に分かれる。したがって $56+120+56=232$ となり一致する。