返回分节阅读
第十八章：随机游走为什么有时回来，有时消失？
向左一步，向右一步，平均起来没有离开的方向。然而，在三维格点中，一个每一步都不偏向任何方向的行者，仍有正概率从此再也不回到出发点。
这不是第四章缩放图像所能回答的问题。那里把很多微小步子压进有限的时间窗口；这里固定每一步的大小，让时间无限延长。我们要数的不是最后站在哪里，而是同一个地方究竟还会被看见多少次。
18.1 能走回来，与会走回来
对可数状态Markov链，从 i 出发，定义首次正时间返回
T_i=\inf\{n\ge1:X_n=i\},\qquad f_i=P_i(T_i<\infty).若 f_i=1，称 i 常返；若 f_i<1，称其暂留，也称暂态。这里返回规则从1开始，否则初始位置会使返回概率恒为1而抹去全部问题。
记 N_i=\sum_{n\ge0}\mathbf1_{\{X_n=i\}}，包括初始访问。第十七章的离散强Markov性质使每次返回后的下一次返回概率仍为 f_i。对逐次返回时刻归纳得到
P_i(N_i\ge k)=f_i^{k-1},\qquad
E_iN_i=\sum_{k\ge1}f_i^{k-1}.于是常返时访问无穷次几乎必然；暂留时访问有限次几乎必然，且平均访问次数为 1/(1-f_i)。无限平均在一般随机变量上未必推出几乎必然无限，但这里几何重启的结构使它成为等价。
18.2 一个无穷级数，记录一个位置的命运
定义Green核
G(i,j)=\sum_{n=0}^\infty p^{(n)}_{ij}=E_i\sum_{n\ge0}\mathbf1_{\{X_n=j\}}.最后的等式由非负积分的Tonelli得到。因此
G(i,i)=\infty\ \Longleftrightarrow\ f_i=1,\qquad
G(i,i)=\frac1{1-f_i}\quad(f_i<1).若 H_j 是包括时刻0的首次命中 j，强Markov还给出 G(i,j)=P_i(H_j<\infty)G(j,j)，作为非负扩展积分理解；概率为0时右边按0解释，不写未定义的 0\cdot\infty。先在命中事件分片，再用单调收敛累计所有后续访问，即可证明这一式。
所以一系列固定时刻的概率，可以合起来回答一条无限路径的问题。这与仅知道某个固定时刻的边缘不同：我们同时利用了返回后的再生关系。
18.3 首次返回把所有返回拆成周期
令 u_n=P_i(X_n=i)，a_k=P_i(T_i=k)。对首次返回时间分片，得到
u_0=1,\qquad u_n=\sum_{k=1}^na_ku_{n-k}\quad(n\ge1).在 0\le z<1 上所有级数绝对收敛，故母函数满足 U(z)=1+A(z)U(z)，即 U(z)=1/(1-A(z))。令 z\uparrow1 就恢复Green判别。首次返回分布可以有缺失质量：总和小于1，恰好表示某些路径根本没有下一周期。
这个更新方程将成为下一章的起点。此刻我们先用另一种读数计算 u_n，看看空间维度怎样改变级数。
18.4 Fourier读数为什么能挑出原点
考虑 \mathbb Z^d 上的简单对称最近邻游走，每一步从 2d 个方向等概率选择，独立重复。单步特征函数为
\phi(\theta)=\frac1d\sum_{j=1}^d\cos\theta_j,
\qquad\theta\in[-\pi,\pi]^d.对任何整数向量 k，各坐标指数积分相乘给出
(2\pi)^{-d}\int_{[-\pi,\pi]^d}e^{i\theta\cdot k}\,d\theta
=\mathbf1_{\{k=0\}}.先对随机位置取期望再用有界Fubini，便得到 u_n=(2\pi)^{-d}\int\phi(\theta)^n\,d\theta。这里无需借用一般局部中心极限定理，也不把弱极限当作单点概率近似。
18.5 先给无穷时间加一个折扣
直接把可能有负号的 \phi^n 无限求和，不能随意交换积分。先取 0<r<1，其绝对和由 1/(1-r) 控制，于是
G_r(0,0)=\sum_{n\ge0}r^nu_n
=(2\pi)^{-d}\int_{[-\pi,\pi]^d}\frac{d\theta}{1-r\phi(\theta)}.这个折扣处理同时解决两个不同的困难。交换求和与积分时，使用的是
\sum_{n\ge0}\int_{[-\pi,\pi]^d}|r^n\phi(\theta)^n|\,d\theta
\le\frac{(2\pi)^d}{1-r}<\infty.随后去掉折扣，不能在整个区域直接声称被积函数随 r 增大：在负读数区域，它反而减小。把正负区域分开，才能让单调收敛处理可能的无穷奇性，让控制收敛处理有共同有限预算的其余部分。
左边随 r\uparrow1 单调趋于Green和。积分右边在 \phi\ge0 区域用单调收敛，在 \phi<0 区域被1控制而用DCT。因此作为允许无穷的等式，
G(0,0)=(2\pi)^{-d}\int_{[-\pi,\pi]^d}\frac{d\theta}{1-\phi(\theta)}.折扣没有改变最终的问题，却使每一步极限交换都有正当依据。我们现在只需判断一个确定积分是否有限。
18.6 原点附近，维度改变了积分预算
在这块周期区域内，\phi=1 只可能发生在所有坐标为0之处。由 1-\cos t 与 t^2 在0附近的双边比较，存在正数 c,C,\delta，使
c|\theta|^2\le1-\phi(\theta)\le C|\theta|^2
\qquad(|\theta|<\delta).离开原点小球，连续函数 1-\phi 有严格正的下界。小球内的可积性则与 \int_0^\delta \rho^{d-3}\,d\rho 相同；也可以不用球坐标，分成尺度 2^{-k} 的环带，其体积与 2^{-kd} 比较，函数大小与 2^{2k} 比较，得到同一几何级数。
也可以把上述维度判别完全写成尺度求和。由
\frac{2t^2}{\pi^2}\le1-\cos t\le\frac{t^2}{2}
\quad(|t|\le\pi)可取得所需二阶比较；下界来自 1-\cos t=2\sin^2(t/2) 和半周期上正弦的弦下界。取足够大的 k，使立方环带
C_k=\{\theta:2^{-k-1}<\|\theta\|_\infty\le2^{-k}\}都在小球中。它的体积为 2^d(1-2^{-d})2^{-kd}，且其上的欧氏范数介于 2^{-k-1} 与 \sqrt d\,2^{-k} 之间。因此有与 k 无关的正数 a_d,b_d，满足
a_d\,2^{-k(d-2)}
\le\int_{C_k}\frac{d\theta}{1-\phi(\theta)}
\le b_d\,2^{-k(d-2)}.二维的每一个更小尺度都贡献一份同阶预算，累积仍然无穷；三维起每缩小一半，预算便按几何速度下降。这个分界不依赖把Gaussian弱极限替换成局部概率，也不需要预先知道返回概率的精细渐近。
因此一维、二维积分发散，三维及更高维积分有限。结合18.2，我们完整得到Pólya判别：
P_0(T_0<\infty)=1\quad(d=1,2),\qquad
P_0(T_0<\infty)<1\quad(d\ge3).每个坐标没有平均漂移，仍不足以决定是否回来。更多维度提供了更多可逃离的方向；数学上，它表现为原点附近同一个二阶奇性，要由多少维体积来承担。
18.7 奇偶性没有消失，只是没有决定常返性
最近邻游走每走一步都改变坐标和的奇偶性，因此奇数时刻不可能返回。第十三章已经说明，单点Gaussian近似必须把允许格点与跨度计入。
在这里，\phi=-1 的角点不使 1-\phi 产生奇性，所以Green判别只由 \phi=1 附近控制。这不表示偶数步概率可以忽略另一个角点：若直接估计 u_{2n}，正负两处峰都会参与。累计访问判别与逐时局部近似是两件不同的事。
加入独立概率 h\in(0,1) 的原地等待后，新读数为 h+(1-h)\phi，故新Green积分恰为原来的 1/(1-h) 倍。周期变为1，常返或暂留分类却不变。等待改变了时钟，没有增加空间上的逃离机会。
18.8 一点漂移就足以改变一维答案
这里仍取独立最近邻步子，明确记 p=P(\Delta S=1)、q=P(\Delta S=-1)=1-p。改变的是左右机会，不是步长、状态空间或时钟。
在直线游走中若 p>q，从1命中0的概率为 q/p：在 [0,a] 使用第十六章的赌博破产公式，再令 a\to\infty 即得。有限时间命中0的路径必有有限最大值，所以这些有限区间事件的并正是最终命中事件。
从−1命中0的概率为1。可以同样扩大左边界，也可由第十二章强大数律看出位置最终向右趋于无穷，最近邻路径必先经过0。于是首次一步分片给出
f_0=p(q/p)+q=2q<1.当 p<q 时对称地得到 f_0=2p。所以一维常返结论对无偏性很敏感；不能只凭空间是一条线，就断言一切随机运动都会回来。
18.9 常返是一个沟通类的性质
若 i 常返，并且 i\to j，每次返回 i 都有同一个正概率沿固定有限路径到达 j。按不重叠的尝试分块，失败概率至多几何下降，因此从 i 最终命中 j 的概率为1。
不重叠尝试可以具体安排。选一条长度为 \ell\ge1 的正概率路线，成功概率记为 \eta>0。在 i 常返的记录上令 \tau_0=0，并令 \tau_{r+1} 是 \tau_r+\ell 以后第一次到达 i 的时刻，允许恰在该时刻到达。它们都是有限停止时刻；第 r 次尝试的整段路线，在下一次尝试之前已经揭示。若 A_r 表示前 r 次尝试全部失败的事件，强Markov性质给出
P_i(A_r)\le(1-\eta)^r.这才是几何界的依据。若每到 i 就立刻开始一个可能重叠的长路线尝试，却直接把成功机会相乘，条件信息未必处在正确时刻。这里无须声称各尝试事件无条件独立，只需每次给定过去的成功概率仍为 \eta。
从 j 也必须以概率1命中 i。否则取一条从 i 首次抵达 j 而中间不再经过 i 的正概率路径，再接上从 j 避开 i 的正概率事件，便使 i 有正概率不返回，矛盾。重复使用强Markov，便知 j 也被无限访问。因此与常返状态沟通的所有状态常返；常返沟通类必闭。
暂留链从任意初始状态访问指定暂留状态的次数也几乎必然有限：若命中，就从首次命中以后使用几何访问次数；若不命中，次数为0。对可数多个状态取共同零集，路径最终离开每一个固定有限集合。这是暂留的一种精确“消失”，不是位置必有一个方向性的极限。
18.10 回来无穷次，仍可能没有平均返回时间
常返状态进一步按 E_iT_i<\infty 或 E_iT_i=\infty 分成正常返与零常返。若从 i 出发的一个完整返回周期中，状态 j 的平均访问次数为
\nu_j=E_i\sum_{n=0}^{T_i-1}\mathbf1_{\{X_n=j\}},则 \nu_i=1，且 \nu P=\nu。证明是把一步转移后的计数改成时刻1至 T_i 的计数：起点与终点都为 i，两端恰好抵消。所有交换先按非负积分理解。
一步平移中，停止规则发挥作用的位置也可以明确写出。事件 \{n<T_i\} 属于 \mathcal F_n，所以Markov条件平均和Tonelli给出
\sum_k\nu_kp_{kj}
=E_i\sum_{n\ge0}\mathbf1_{\{n<T_i\}}p_{X_nj}
=E_i\sum_{n\ge0}\mathbf1_{\{n<T_i\}}\mathbf1_{\{X_{n+1}=j\}}
=E_i\sum_{n=1}^{T_i}\mathbf1_{\{X_n=j\}}
=\nu_j.最后一步先在每条有限返回路径上比较两份计数：它们只交换了同为 i 的首尾，并没有对两个无穷期望作减法。Green和数的是无限多个周期的全部访问，周期测度数的却是一个周期内部的访问；前者发散，只能保证常返，不能保证后一份总预算有限。
不可约常返时每项 \nu_j 有限。因为从 j 有一条在返回 j 之前命中 i 的正概率路径，故到达 j 后、命中 i 前的访问次数被一个有限均值的几何次数控制。若 E_iT_i<\infty，总质量 \sum_j\nu_j=E_iT_i，于是可归一化成不变概率。
这项构造说明，不变概率不是凭空求出的矩阵特征向量。它可以是一个真实返回周期的占用预算，除以这个周期的平均长度。
18.11 为什么不变概率恰好要求有限平均周期
反过来，设不可约可数链有不变概率 \pi。先选一个正质量状态，再沿正概率路径用不变方程传播，得每项 \pi_i>0。在平稳初始律下，事件“时刻 n 在 i，以后再也不来”对不同 n 互斥；有限块的平稳性再取递减极限，使每个事件的概率都为 \pi_i(1-f_i)。无限相加不超过1，故 f_i=1，且这对每个状态成立。这里没有借用一般遍历定理。
还要让余项真正消失。由18.9，从任意状态 k 都几乎必然命中 i：一条离开 k 后不再经过它的正概率命中路径，可以在逐次返回 k 时重新尝试，连续失败概率受几何尾控制。记 H_i=\inf\{n\ge0:X_n=i\}、D=E\setminus\{i\}，令 K=(p_{k\ell})_{k,\ell\in D} 为杀死于 i 的次随机矩阵，b=(p_{ij})_{j\in D}。不变方程在 D 上给出
\pi_D=\pi_i b+\pi_DK
=\pi_i\sum_{r=0}^{N-1}bK^r+\pi_DK^N.对 j\in D，\sum_{r\ge0}(bK^r)_j=\nu_j：这些恰是从 i 出发、第一次返回以前各时刻的访问概率。余项的总质量则为
\sum_{j\in D}(\pi_DK^N)_j
=\sum_{k\in D}\pi_kP_k(H_i>N)\longrightarrow0.每个命中尾概率趋0，并由可求和的 \pi_k 控制，故这里是有依据的控制收敛；前一项由非负单调收敛趋于 \pi_i\nu_j。加上 \nu_i=1，再对全部状态求和，便得到
\pi_j=\pi_i\nu_j,\qquad E_iT_i=1/\pi_i.周期预算于是唯一地决定不变概率。直线对称游走常返，却由第十七章知道没有不变概率，所以必为零常返。有限不可约链有不变概率，因此每个状态正常返；它仍可能因周期而不逐步收敛。
18.12 上升的新纪录，是另一种再开始
对一般实值独立增量游走 S_n，首次严格超过初值的时刻 L 与高度 H=S_L，可以组成一个有缺失质量的联合分布：有些路径可能永不创造新高。每次新高以后，独立增量与停止分片使下一次新高的时间差、高度差具有同一联合规律。
若 q(z,\theta)=E[z^Le^{i\theta H};L<\infty]，其中 0\le z<1，则所有严格上升纪录的联合变换之和为 \sum_{k\ge0}q(z,\theta)^k=1/(1-q(z,\theta))。因为 |q(z,\theta)|\le z<1，交换与求和有绝对控制。这是离散梯级更新结构的实质证明。
它还不是把整个游走分成上升、下降两部分的完整Wiener–Hopf因子分解；严格与弱梯级的边界约定及完整乘积分解仍须另外证明。我们保留这个准确边界，不用一个名称宣告已经建立全部离散或Lévy因子分解。
第十八章结语：位置反复出现，时间开始分成周期
没有漂移的步子，在二维与三维之间跨过了一条真正的边界。区别并不来自一次跳跃，而来自无穷次可能返回所需要的总预算。Green和把这个预算写出来，Fourier积分则把它化成原点附近体积与奇性的竞争。
一旦返回发生，未来又从同一个状态出发。沿着一条记录，时间便被切成一个个周期。有的周期永远等不到，有的总会结束却没有有限均值。若要把这些重新开始合起来计算长期等待，下一步就不再只是判断回来与否，而是研究周期怎样填满时间。
史料与范围
Pólya的论文《Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz》刊于1921年的《Mathematische Annalen》84卷，149–160页。本章的折扣Fourier证明使用已经建立的特征函数和积分工具，是现代重建，不声称复制原论文证明。原文与出版元数据见 Pólya论文。本章完整判别的是简单对称最近邻格点游走；任意步长、相关步子或一般群上的常返性不能由维度口号代替证明。