ランダムウォーク

要点：最初に高さ $a$ に達した時刻より後の歩幅の符号をすべて反転する写像が、全単射を与える。

段 1（初めて戻る時刻で分ける）。 $n\ge1$ とする。$S_n=0$ なら $T\le n$ なので、事象 $\{S_n=0\}$ は互いに素な事象 $\{T=k,\ S_n=0\}$（$k=1,\dots,n$）の和である。$T=k$ のとき $S_k=0$ なので $S_n=S_n-S_k=X_{k+1}+\cdots+X_n$ であり
$$ \{T=k,\ S_n=0\}=\{T=k\}\cap\{X_{k+1}+\cdots+X_n=0\} $$
である。$\{T=k\}=\{S_1\ne0,\dots,S_{k-1}\ne0,\ S_k=0\}$ は $X_1,\dots,X_k$ だけで決まり、$X_{k+1}+\cdots+X_n$ は $X_{k+1},\dots,X_n$ だけで決まる。独立な確率変数の互いに素な組の関数は独立なので（Dur19 Theorem 2.1.10, p. 47）、二つの事象は独立である。また $X_{k+1}+\cdots+X_n$ は $n-k$ 個の独立で同じ分布に従う歩幅の和なので、$S_{n-k}$ と同じ分布に従う。よって
$$ P(S_n=0)=\sum_{k=1}^nP(T=k)\,P(S_{n-k}=0) $$
であり、1 を得る。
段 2（母関数の関係式）。 $0\le s<1$ について
$$ U(s):=\sum_{n=0}^\infty u_ns^n,\qquad F(s):=\sum_{n=1}^\infty f_ns^n $$
とおく。$0\le u_n,f_n\le1$ なので、どちらも $\sum s^n<\infty$ を上界にもつ収束級数である。1 の両辺に $s^n$ をかけて $n\ge1$ で足すと、右辺は収束する二つの正項級数の積（Cauchy 積）なので
$$ U(s)-1=\sum_{n=1}^\infty\sum_{k=1}^nf_ks^k\,u_{n-k}s^{n-k}=F(s)\,U(s) $$
となる。$F(s)\le\sum_{n\ge1}f_ns\le s<1$ なので $U(s)=\dfrac1{1-F(s)}$ である。
段 3（$s\to1$ の極限）。 係数が $0$ 以上の級数 $\sum a_ns^n$ について、$s\uparrow1$ で $\sum a_ns^n\to\sum a_n$ である（右辺が $\infty$ でもよい）。実際、どの $N$ についても $\sum_{n\le N}a_ns^n\le\sum a_ns^n\le\sum a_n$ であり、左端は $s\uparrow1$ で $\sum_{n\le N}a_n$ に近づくので、下極限は $\sum_{n\le N}a_n$ 以上である。$N\to\infty$ とすればよい。これを $U$ と $F$ に使うと、$F(s)\to P(T<\infty)$、$U(s)\to\sum_nu_n$ である。$P(T<\infty)<1$ なら $\sum_nu_n=1/(1-P(T<\infty))$ である。$P(T<\infty)=1$ なら $1/(1-F(s))\to\infty$ なので $\sum_nu_n=\infty$ である。これで 2 が示せた。3 は 2 から直ちに従う。$\square$

要点：$j$ 回目に戻る時刻で分けて $P(V\ge j)=P(T<\infty)^j$ を示す。

段 1。 $E[e^{i\langle\theta,S_n\rangle}]=\varphi(\theta)^n$ である。実際 $e^{i\langle\theta,S_n\rangle}=\prod_{k=1}^ne^{i\langle\theta,X_k\rangle}$ で、各因子を実部と虚部に分けて積を展開すると、$2^n$ 個の項はどれも独立な有界実確率変数 $\cos\langle\theta,X_k\rangle$ または $\sin\langle\theta,X_k\rangle$ の積になる。独立な可積分確率変数の積の期待値は期待値の積なので（Dur19 Theorem 2.1.13, p. 49）、展開を戻せば $E[\prod_ke^{i\langle\theta,X_k\rangle}]=\prod_kE[e^{i\langle\theta,X_k\rangle}]=\varphi(\theta)^n$ となる。
段 2。 $S_n$ は $\mathbb{Z}^d$ に値をとるので $\varphi(\theta)^n=\sum_{x\in\mathbb{Z}^d}P(S_n=x)e^{i\langle\theta,x\rangle}$ であり、この級数は $\theta$ について一様に絶対収束する（係数の絶対値の和が $1$）。よって項別に積分できる。整数 $x_j$ について $\int_{-\pi}^{\pi}e^{i\theta_jx_j}d\theta_j$ は $x_j=0$ なら $2\pi$、$x_j\ne0$ なら $0$ なので、$\int_Qe^{i\langle\theta,x\rangle}d\theta$ は $x=0$ のとき $(2\pi)^d$、それ以外は $0$ である。したがって $\int_Q\varphi(\theta)^nd\theta=(2\pi)^dP(S_n=0)$ である。$\square$

段 1（和を一つの積分にする）。 1 歩ごとに座標の和の偶奇が変わるので、$n$ が奇数なら $P(S_n=0)=0$ である。$\varphi$ の値が $\pm1$ になるのは、すべての $\cos\theta_j$ が同時に $1$ か同時に $-1$ のときで、$Q$ の中の有限個の点だけである。それ以外の点では $0\le\varphi^2<1$ なので
$$ \sum_{n=0}^N\varphi(\theta)^{2n}=\frac{1-\varphi(\theta)^{2N+2}}{1-\varphi(\theta)^2}\ \uparrow\ \frac1{1-\varphi(\theta)^2}\qquad(N\to\infty) $$
であり、左辺は $N$ について増加する $0$ 以上の関数である。lem-rw-fourier と 単調収束定理 により
$$ \sum_{n=0}^\infty P(S_n=0)=\sum_{n=0}^\infty P(S_{2n}=0)=\frac1{(2\pi)^d}\int_Q\frac{d\theta}{1-\varphi(\theta)^2}\qquad(\le\infty) $$
である。
段 2（部分分数と平行移動）。 $\frac1{1-\varphi^2}=\frac12\Bigl(\frac1{1-\varphi}+\frac1{1+\varphi}\Bigr)$ である。$\mathbf 1:=(1,\dots,1)$ とすると $\cos(\theta_j+\pi)=-\cos\theta_j$ から $\varphi(\theta+\pi\mathbf 1)=-\varphi(\theta)$ である。各変数について周期 $2\pi$ の $0$ 以上の関数 $g$ では、各座標の区間 $[-\pi,\pi]$ を $[-\pi,0]$ と $[0,\pi]$ に分けて平行移動すれば $\int_Qg(\theta+\pi\mathbf 1)d\theta=\int_Qg(\theta)d\theta$ となる。$g=1/(1-\varphi)$ に使うと $\int_Q\frac{d\theta}{1+\varphi}=\int_Q\frac{d\theta}{1-\varphi}$ なので
$$ \sum_{n=0}^\infty P(S_n=0)=\frac1{(2\pi)^d}\int_Q\frac{d\theta}{1-\varphi(\theta)} $$
である。
段 3（被積分関数の大きさ）。 $\lvert x\rvert\le\pi$ について
$$ \frac{2}{\pi^2}x^2\le1-\cos x\le\frac{x^2}{2} $$
である。右は $1-\cos x=2\sin^2(x/2)$ と $\lvert\sin y\rvert\le\lvert y\rvert$ から、左は $\lvert y\rvert\le\frac\pi2$ での $\lvert\sin y\rvert\ge\frac2\pi\lvert y\rvert$（$\sin$ は $[0,\frac\pi2]$ で上に凸なので、弦 $y\mapsto\frac2\pi y$ より上にある）から従う。$1-\varphi(\theta)=\frac1d\sum_j(1-\cos\theta_j)$ なので、$\lvert\theta\rvert^2=\sum_j\theta_j^2$ と書くと $Q$ の上で
$$ \frac{2d}{\lvert\theta\rvert^2}\le\frac1{1-\varphi(\theta)}\le\frac{d\pi^2}{2}\cdot\frac1{\lvert\theta\rvert^2} $$
である。よって $\sum_nP(S_n=0)$ が有限であることは、$J_d:=\int_Q\lvert\theta\rvert^{-2}d\theta$ が有限であることと同値である。
段 4（$J_d$ と次元）。 $\lvert\theta\rvert_\infty:=\max_j\lvert\theta_j\rvert$ とし、$k\ge0$ について $A_k:=\{\theta\in Q:\ \pi2^{-k-1}<\lvert\theta\rvert_\infty\le\pi2^{-k}\}$ とおく。$Q\setminus\{0\}$ は $A_0,A_1,\dots$ の互いに素な和である。$A_k$ は一辺 $2\pi2^{-k}$ の立方体から一辺 $\pi2^{-k}$ の立方体を除いたものなので、体積は $(2\pi)^d2^{-kd}(1-2^{-d})$ である。$\lvert\theta\rvert_\infty\le\lvert\theta\rvert\le\sqrt d\,\lvert\theta\rvert_\infty$ から、$A_k$ の上で $\pi^24^{-k-1}<\lvert\theta\rvert^2\le d\pi^24^{-k}$ である。したがって
$$ \frac{(2\pi)^d(1-2^{-d})}{d\pi^2}\,2^{k(2-d)}\le\int_{A_k}\frac{d\theta}{\lvert\theta\rvert^2}\le\frac{4(2\pi)^d(1-2^{-d})}{\pi^2}\,2^{k(2-d)} $$
であり、$J_d=\sum_k\int_{A_k}$ は $\sum_k2^{k(2-d)}$ と同時に収束・発散する。これは $d\ge3$ なら有限、$d=1,2$ なら $\infty$ である。
段 5（結論）。 $d=1,2$ なら $\sum_nP(S_n=0)=\infty$ なので、thm-rw-criterion の 3 により再帰的である。$d\ge3$ なら段 2 により $\sum_nP(S_n=0)=G_d<\infty$ なので過渡的であり、thm-rw-criterion の 2 から $1/(1-P(T<\infty))=G_d$、すなわち $P(T<\infty)=1-1/G_d$ である。$\square$