ランダムウォークの原点への復帰

$S_n$ は $+1$ を $a$ 個、$-1$ を $b$ 個足したものなので $S_n=a-b$ であり、動きの個数を数えて $n=a+b$ である。$S_n=0$ なら $a=b$ で、$n=a+b=2a$ は偶数、$a=b=\dfrac n2$ である。$n$ が奇数なら $a=b$ となることはないので、$S_n=0$ となる歩みは 1 つもなく、確率は $0$ である。$\square$

方針：(1) は並べ方を数えるだけである。(2) は、まず「原点に戻らない歩みは、ずっと正か、ずっと負か」に分ける。ずっと正の歩みを最後の位置 $S_{2n}=2j$ ごとに投票定理で数え、その和が望遠鏡のように消えて $\dfrac12\dbinom{2n}n$ になることを示す。
段 1（(1) の証明）。prop-rwr-parity により、$S_{2n}=0$ となるのは、$2n$ 回の動きのうち $+1$ がちょうど $n$ 回、$-1$ が $n$ 回のときである。$+1$ を置く $n$ か所の選び方は $\dbinom{2n}n$ 通りある（格子の道で言えば、$(0,0)$ から $(n,n)$ への最短経路の数である）。長さ $2n$ の歩みは $2^{2n}=4^n$ 通りで、どれも同じ確率なので、$u_{2n}=\dbinom{2n}n\Big/4^n$ である。
段 2（ずっと正か、ずっと負か）。$S_1,\ldots,S_{2n}$ がどれも $0$ でない歩みを考える。$S_1$ は $+1$ か $-1$ である。$S_1=1$ なのに、ある $k$ で $S_k<0$ となったとする。位置は整数で、1 回に $1$ ずつしか変わらないので、$1$ 以上の値から $-1$ 以下の値に移る途中で、必ず $0$ を通る。これは「どれも $0$ でない」に反する。よって $S_1=1$ なら $S_1,\ldots,S_{2n}$ はすべて正である。同じように、$S_1=-1$ ならすべて負である。
また、歩みのすべての動きの符号を入れ替える（$X_k$ を $-X_k$ にする）と、位置もすべて符号が入れ替わる。この入れ替えは、ずっと正の歩みとずっと負の歩みを 1 対 1 に対応させる（2 回入れ替えると元に戻る）。したがって
$$ (\text{原点に戻らない歩みの数})=2\times(\text{ずっと正の歩みの数}) $$
である。
段 3（ずっと正の歩みを、最後の位置ごとに数える）。ずっと正の歩みでは $S_{2n}>0$ で、prop-rwr-parity と同じく $S_{2n}=a-b$、$a+b=2n$ なので $S_{2n}$ は偶数である。$S_{2n}=2j$（$j=1,2,\ldots,n$）とおくと、$+1$ の回数は $a=n+j$、$-1$ の回数は $b=n-j$ である。$+1$ を A の票、$-1$ を B の票とみると、「$S_1,\ldots,S_{2n}$ がすべて正」は「最初の 1 票から最後まで、A の票数がつねに B の票数より多い」ことと同じである。$a>b\ge0$ なので、最短経路の数え上げと鏡像原理 の定理「投票定理」が使えて、A と B の並べ方 $\dbinom{2n}{n+j}$ 通りのうち、その割合は $\dfrac{a-b}{a+b}=\dfrac{2j}{2n}=\dfrac jn$ である。よって、$S_{2n}=2j$ となるずっと正の歩みの数は
$$ \frac jn\binom{2n}{n+j} $$
である。
段 4（差の形に書きかえる）。$m=n+j$ とおく（$n+1\le m\le2n$）。階乗で書くと
$$ \binom{2n-1}{m-1}=\frac{(2n-1)!}{(m-1)!\,(2n-m)!}=\frac m{2n}\cdot\frac{(2n)!}{m!\,(2n-m)!}=\frac m{2n}\binom{2n}m $$
である（分母と分子に $2n$ と $m$ を掛けて、$(2n)!=2n\cdot(2n-1)!$、$m!=m\cdot(m-1)!$ を使った）。同じように、$m\le2n-1$ なら
$$ \binom{2n-1}{m}=\frac{(2n-1)!}{m!\,(2n-1-m)!}=\frac{2n-m}{2n}\cdot\frac{(2n)!}{m!\,(2n-m)!}=\frac{2n-m}{2n}\binom{2n}m $$
であり、$m=2n$ のときは両辺とも $0$ である（$\dbinom{2n-1}{2n}=0$ と約束する）。2 つの式を引くと
$$ \binom{2n-1}{m-1}-\binom{2n-1}{m}=\frac{m-(2n-m)}{2n}\binom{2n}m=\frac{2j}{2n}\binom{2n}{n+j}=\frac jn\binom{2n}{n+j} $$
となる（$m-(2n-m)=2m-2n=2j$）。つまり、段 3 の数は
$$ \frac jn\binom{2n}{n+j}=\binom{2n-1}{n+j-1}-\binom{2n-1}{n+j} $$
と差の形に書ける。
段 5（足すと消える）。段 4 の式を $j=1,2,\ldots,n$ について足すと、
$$ \sum_{j=1}^n\left\{\binom{2n-1}{n+j-1}-\binom{2n-1}{n+j}\right\}=\left\{\binom{2n-1}{n}-\binom{2n-1}{n+1}\right\}+\left\{\binom{2n-1}{n+1}-\binom{2n-1}{n+2}\right\}+\cdots+\left\{\binom{2n-1}{2n-1}-\binom{2n-1}{2n}\right\} $$
となり、隣り合う中かっこの間で項が打ち消し合って、最初の項と最後の項だけが残る：
$$ \binom{2n-1}{n}-\binom{2n-1}{2n}=\binom{2n-1}{n} $$
段 4 の 2 つ目の式で $m=n$ とおくと $\dbinom{2n-1}n=\dfrac{2n-n}{2n}\dbinom{2n}n=\dfrac12\dbinom{2n}n$ なので、ずっと正の歩みの数は $\dfrac12\dbinom{2n}n$ である。
段 6（結論）。段 2 より、原点に戻らない歩みの数は $2\times\dfrac12\dbinom{2n}n=\dbinom{2n}n$ である。これを $4^n$ で割ると、確率は $\dbinom{2n}n\Big/4^n=u_{2n}$ で、段 1 の値に等しい。$\square$

thm-rwr-main の (1) から
$$ \frac{u_{2n}}{u_{2n-2}}=\frac{\binom{2n}n}{\binom{2n-2}{n-1}}\cdot\frac{4^{n-1}}{4^n}=\frac{(2n)!\,\{(n-1)!\}^2}{(n!)^2\,(2n-2)!}\cdot\frac14=\frac{2n(2n-1)}{n^2}\cdot\frac14=\frac{2n-1}{2n} $$
である（$(2n)!=2n(2n-1)\cdot(2n-2)!$、$n!=n\cdot(n-1)!$ で約分した）。$n=1$ でも $u_2=\dfrac12=\dfrac12u_0$ で成り立つ。この式を $n,n-1,\ldots,1$ と順に使い、$u_0=1$ とすると積の形を得る。$\square$

方針：積 $u_{2n}=\dfrac12\cdot\dfrac34\cdots\dfrac{2n-1}{2n}$ の 2 乗を考え、各因子の 2 乗を、掛けると約分で消えていく分数で上下からはさむ。
段 1（上からの評価）。$k\ge1$ について、$(2k-1)(2k+1)=4k^2-1<4k^2$ なので、両辺を正の数 $2k(2k+1)$ で割ると
$$ \frac{2k-1}{2k}<\frac{2k}{2k+1} $$
である。両辺に正の数 $\dfrac{2k-1}{2k}$ を掛けると
$$ \left(\frac{2k-1}{2k}\right)^2<\frac{2k-1}{2k}\cdot\frac{2k}{2k+1}=\frac{2k-1}{2k+1} $$
である。これを $k=1,2,\ldots,n$ について掛け合わせると、右辺の積は
$$ \frac13\cdot\frac35\cdot\frac57\cdots\frac{2n-1}{2n+1}=\frac1{2n+1} $$
と、隣り合う分数の分子と分母が約分で消える。よって $u_{2n}^2<\dfrac1{2n+1}$ で、両辺の正の平方根をとって $u_{2n}<\dfrac1{\sqrt{2n+1}}$ である。
段 2（下からの評価）。$k\ge2$ について、$(2k-1)^2=4k^2-4k+1>4k^2-4k=2k(2k-2)$ なので、両辺を正の数 $2k(2k-1)$ で割ると
$$ \frac{2k-1}{2k}>\frac{2k-2}{2k-1} $$
である。両辺に $\dfrac{2k-1}{2k}$ を掛けると
$$ \left(\frac{2k-1}{2k}\right)^2>\frac{2k-1}{2k}\cdot\frac{2k-2}{2k-1}=\frac{2k-2}{2k}=\frac{k-1}k $$
である。$k=1$ の因子は $\left(\dfrac12\right)^2=\dfrac14$ のままにして、$k=2,\ldots,n$ の不等式を掛け合わせると
$$ u_{2n}^2\ge\frac14\cdot\frac12\cdot\frac23\cdots\frac{n-1}n=\frac14\cdot\frac1n=\frac1{4n} $$
である（$n=1$ では右辺の積は $\dfrac14$ だけで、等号が成り立つ）。正の平方根をとって $u_{2n}\ge\dfrac1{2\sqrt n}$ である。$\square$

方針：前半は thm-rwr-main の (2) の余事象である。後半は lem-rwr-bounds の上の評価とはさみうちの原理による。
段 1（前半）。「$2n$ 回目までに少なくとも 1 回原点に戻る」の余事象は「$S_1,\ldots,S_{2n}$ がどれも $0$ でない」である。thm-rwr-main の (2) より余事象の確率は $u_{2n}$ なので、求める確率は $1-u_{2n}$ である。
段 2（後半）。lem-rwr-bounds より $0< u_{2n}\le\dfrac1{\sqrt{2n+1}}$ である。$n\to\infty$ で $\dfrac1{\sqrt{2n+1}}\to0$ なので、はさみうちの原理により $u_{2n}\to0$ であり、$1-u_{2n}\to1$ である。$\square$

方針：$N_{2n}$ を「$k$ 回目に原点にいれば $1$、いなければ $0$」という確率変数の和に分け、期待値の線形性を使う。和の公式は $n$ についての帰納法で示す。
段 1（和に分ける）。$k=1,\ldots,2n$ について、$S_k=0$ なら $1$、そうでなければ $0$ をとる確率変数を $I_k$ とする。$N_{2n}=I_1+I_2+\cdots+I_{2n}$ である。$I_k$ の期待値は $1\cdot P(S_k=0)+0\cdot P(S_k\ne0)=P(S_k=0)$ である。確率変数の期待値と分散 の命題「期待値の線形性」により
$$ E[N_{2n}]=\sum_{k=1}^{2n}P(S_k=0) $$
である。prop-rwr-parity より奇数の $k$ の項は $0$ で、偶数の $k=2j$ の項は $u_{2j}$ なので、$E[N_{2n}]=u_2+u_4+\cdots+u_{2n}$ である。
段 2（和の公式）。$u_2+\cdots+u_{2n}=(2n+1)u_{2n}-1$ を $n$ についての帰納法で示す。$n=1$ では、左辺 $u_2=\dfrac12$、右辺 $3\cdot\dfrac12-1=\dfrac12$ で成り立つ。$n$ で成り立つとすると、$n+1$ では
$$ u_2+\cdots+u_{2n}+u_{2n+2}=(2n+1)u_{2n}-1+u_{2n+2} $$
である。prop-rwr-recur より $u_{2n+2}=\dfrac{2n+1}{2n+2}u_{2n}$、つまり $(2n+1)u_{2n}=(2n+2)u_{2n+2}$ なので、右辺は
$$ (2n+2)u_{2n+2}-1+u_{2n+2}=(2n+3)u_{2n+2}-1=\bigl(2(n+1)+1\bigr)u_{2(n+1)}-1 $$
となり、$n+1$ でも成り立つ。
段 3（限りなく大きくなる）。lem-rwr-bounds の下の評価 $u_{2n}\ge\dfrac1{2\sqrt n}$ から
$$ E[N_{2n}]=(2n+1)u_{2n}-1\ge\frac{2n+1}{2\sqrt n}-1>\frac{2n}{2\sqrt n}-1=\sqrt n-1 $$
である。$n\to\infty$ で $\sqrt n-1$ は限りなく大きくなるので、$E[N_{2n}]$ も限りなく大きくなる。$\square$