ランダム・ウォーク

(12.6) は定数係数の線形差分方程式である。$h(k)=x^k$ を代入すると、特性方程式 $px^2-x+q=0$ を得る。$p+q=1$ を使うと $px^2-x+q=(x-1)(px-q)$ と因数分解できる。根は 1 と $r=q/p$ である。

• $p\ne q$ なら一般解は $h(k)=A+Br^k$ である。$h(0)=0$ から $A=-B$ である。$h(N)=1$ から $B(r^N-1)=1$。よって $h(k)=(r^k-1)/(r^N-1)$ で、これは (12.7) に等しい。
• $p=q$ なら重根 1 で、一般解は $h(k)=A+Bk$ である。境界条件から $h(k)=k/N$ である。

$D(k)$ も第一歩解析で求める。1歩使ってから $k\pm1$ に移るので

$$D(k)=1+p\,D(k+1)+q\,D(k-1)\qquad(0<k<N),\qquad D(0)=D(N)=0.$$

これは非斉次方程式である。一般解は、斉次方程式の一般解に特解を足したものである。斉次方程式の一般解は $A+Br^k$ である（等確率なら $A+Bk$）。

• $p\ne q$ のとき。$D(k)=ck$ を代入すると

$$ck=1+pc(k+1)+qc(k-1)=1+ck+c(p-q)$$

から $c=1/(q-p)$。一般解は $D(k)=k/(q-p)+A+Br^k$ である。$D(0)=0$ から $A=-B$ である。$D(N)=0$ から $B(r^N-1)=-N/(q-p)$ で、

$$D(k)=\frac{k}{q-p}-\frac{N}{q-p}\cdot\frac{r^k-1}{r^N-1}$$

となり (12.8) を得る。

• $p=q=1/2$ のとき。$D(k)=ck^2$ を代入すると

$$ck^2=1+\tfrac c2\{(k+1)^2+(k-1)^2\}=1+ck^2+c$$

から $c=-1$。一般解は $D(k)=-k^2+A+Bk$ である。境界条件を入れると $A=0$、$B=N$ となる。よって $D(k)=k(N-k)$ である。

$(0,a)$ から出発して高さ 0 に触れる経路を考え、初めて高さ 0 に達する時刻を $\tau$ とする。$\tau$ までの部分を横軸に関して折り返す（高さの符号を反転する）。得られる経路は $(0,-a)$ から出発して $(\tau,0)$ を通る。そのあとは元と同じなので、$(n,b)$ に至る。

逆に $(0,-a)$ から $(n,b)$ への経路は、終点が正なので必ずどこかで高さ 0 を通る。その最初の時刻までの部分を折り返すと、$(0,a)$ から出発して高さ 0 に触れる経路に戻る。この2つの操作は互いに逆なので、2つの経路の集合は1対1に対応し、数が等しい。

$S_n\ge m$ なら当然 $\overline S_n\ge m$ なので、次のように分けられる。

$$P(\overline S_n\ge m)=P(S_n\ge m)+P(\overline S_n\ge m,\ S_n<m).$$

$\overline S_n\ge m$ かつ $S_n=b<m$ の経路を考える。初めて高さ $m$ に達した時刻より後の部分を、高さ $m$ に関して折り返す。すると終点が $2m-b>m$ の経路になる（図 12.1）。

終点が $m$ より上の経路は、必ず高さ $m$ を通る。よってこの対応は1対1であり、

$$P(\overline S_n\ge m,\ S_n=b)=P(S_n=2m-b).$$

$b<m$ について和をとると、$P(\overline S_n\ge m,\ S_n<m)=P(S_n>m)$ を得る。

原点に戻る回数を $R=\sum_{n\ge1}\mathbf 1\{S_{2n}=0\}$ とする。原点に戻った時点から先の歩みは、出発時と同じ確率法則に従う新しいランダム・ウォークである。よって $k$ 回戻ったあと、さらにもう1回戻る確率は $f$ である。これから $P(R\ge k)=f^k$ となり、

$$E[R]=\sum_{k\ge1}P(R\ge k)=\sum_{k\ge1}f^k$$

は、$f<1$ なら $f/(1-f)<\infty$ である。$f=1$ なら発散する。一方 $E[R]=\sum_n P(S_{2n}=0)=\sum_n u_{2n}$ なので、前半の同値性が従う。Stirling の公式 $m!\sim\sqrt{2\pi m}\,(m/\mathrm{e})^m$ を使うと

$$u_{2n}=\frac{(2n)!}{(n!)^2\,4^n}\sim\frac{\sqrt{4\pi n}\,(2n/\mathrm{e})^{2n}}{2\pi n\,(n/\mathrm{e})^{2n}\,4^n}=\frac{1}{\sqrt{\pi n}}$$

で、$\sum 1/\sqrt n$ は発散するので $\sum u_{2n}=\infty$ である。