这是一个关于二维随机游动的小系列，整理自我研究生时的读书笔记，每篇文章会从一个有趣直观的问题出发，介绍随机游动理论中的一个相关知识。整个系列的内容都比较基础，涉及的知识在 Durrett 的教材 ¹ 中都可以找到。

今天的问题依然有趣，但是并不简单。

问题：假设某醉汉以太阳系的中心为原点出发，在一个固定的平面内，以恒为 1 米的步长作随机行走。每次醉汉等概率地随机选择东、南、西、北中任一方向，然后向此方向移动 1 米的距离。如果某个时刻醉汉回到了原点，或者离开了太阳系则过程结束。

现在有 A, B 两个旁观者打赌哪一种情形先发生，A 认为醉汉会先回到原点，B 认为醉汉会先离开太阳系。请问 A, B 获胜的概率分别是多少？

作为参考，太阳系半径约为 45 亿千米，看作一个中心在原点的圆形区域。

显然醉汉的行为是 \(\mathbb{Z}^2\) 上的简单随机游动，而我们熟知 \(\mathbb{Z}^d\) 上的随机游动在 \(d=1,2\) 时是常返的，在 \(d>2\) 时是暂态的，所以醉汉以概率 1 会走遍平面上的所有角落，即 A, B 这场赌局是必然可以分出胜负的。从直观上，\(A\) 的获胜概率应该更大，因为醉汉回到原点显然是个更容易发生的事件：醉汉的路径可能是选择一个方向一步迈出去再一步迈回来，或者干脆绕一个圈子，而走出太阳系那么远的距离则困难得多。事实也是如此，实际上 A, B 获胜概率的“分水岭”大约在 \(R\approx 4.2\) 米处左右 ²，随着逃逸半径 \(R\) 的增大，A 获胜的概率也随之增大，常返性保证了当 \(R\to+\infty\) 时 A 获胜的概率趋于 1。这里有趣的地方在于，A 的获胜概率随逃逸半径 \(R\) 的增加而增长的速度相当缓慢，其近似值约为 \[1-(\frac{2}{\pi}\ln R + 1.0293737)^{-1},\] 所以当 \(R\) 取为太阳系半径时，B 的获胜概率大约为 1/20，进一步当 \(R\) 扩大为银河系的半径 (5 万光年) 时，B 仍然有大约 1/30 的获胜概率！是不是很反直觉呢？想象一下你写了一个程序，通过模拟随机游动来计算返回原点的时间，那可要小心了：程序会有一个不小的概率让你在有生之年都等不到结果！

本文下面就来介绍怎样得出上面获胜概率的渐进公式，这里的讲述主要参考了 Spitzer 的教材 ³，好处是比较简单易懂，稍微麻烦点的地方也只是一些普通的微积分计算，缺点是没有给出势核误差项的渐进估计。使用局部中心极限定理的话可以给出势核误差项的渐进估计 ⁴，但是会让文章变得比较艰涩，所以本文没有采用。

问题的解决方法属于随机游动中的基础知识，大致分以下步骤：

1. 构造一个叫做势核 (potential kernel) 的调和函数。
2. 使用特征函数估计势核的渐进阶。
3. 使用势核的调和性质构造对应的随机游动的鞅。
4. 使用鞅的可料停时定理给出逃逸概率的估计。

二维随机游动的特征函数

我们把醉汉在 \(n\) 时刻的位置 \(S_n\) 表示为 \(S_n=X_1+\cdots+X_n\)，其中 \(X_i\) 表示单步移动的随机向量，它们独立且与随机向量 \(X\) 同分布： \[\mathbb{P}(X=e_1)=\mathbb{P}(X=e_2)=\mathbb{P}(X=-e_1)=\mathbb{P}(X=-e_2)=\frac{1}{4}.\] 这里 \(e_1=(1, 0), e_2=(0, 1)\) 为平面上的正交单位向量。 记 \(\phi(\theta)=\mathbb{E}\mathrm{e}^{i\theta\cdot X}\) 为 \(X\) 的特征函数，其中 \(\theta=(\theta_1,\theta_2)\)，则 \[ \phi(\theta)=\frac{1}{4}\sum_{x\in\{\pm e_1,\pm e_2\}}\mathrm{e}^{i(\theta_1x_1+\theta_2x_2)}=\frac{1}{2}(\cos\theta_1 + \cos\theta_2). \] 于是 \(S_n\) 的特征函数为 \(\phi^n(\theta)\)。

用特征函数我们可以非常方便地表示概率 \(\mathbb{P}(S_n=y),y\in\mathbb{Z}^2\)： \[\begin{equation} \mathbb{P}(S_n=y) = \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\mathrm{e}^{-i\theta\cdot y}\phi^n(\theta)\,\mathrm{d}\theta. \end{equation} \] 其中 \(\mathbb{T}=[-\pi,\pi]\times[-\pi, \pi]\)。这是因为根据特征函数定义有 \[ \phi^n(\theta)=\mathbb{E}\mathrm{e}^{i\theta\cdot S_n}=\sum_{x\in\mathbb{Z}^2}\mathbb{P}(S_n=x)\mathrm{e}^{i\theta\cdot x}. \] 两边同时乘以 \(\mathrm{e}^{-i\theta\cdot y}\) 并在 \(\mathbb{T}\) 上积分即得 \[ \begin{align*} \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\mathrm{e}^{-i\theta\cdot y}\phi^n(\theta)\,\mathrm{d}\theta&= \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\sum_{x\in\mathbb{Z}^2}\mathbb{P}(S_n=x)\mathrm{e}^{i\theta\cdot(x-y)}\,\mathrm{d}\theta\\&= \sum_{x\in\mathbb{Z}^2}\mathbb{P}(S_n=x)\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\mathrm{e}^{i\theta\cdot(x-y)}\,\mathrm{d}\theta\\&= \sum_{x\in\mathbb{Z}^2}\mathbb{P}(S_n=x)\cdot\delta_{x,y}\\&= \mathbb{P}(S_n=y). \end{align*} \] 这里我们利用了对 \(z\in\mathbb{Z}^2\) 的积分 \[ \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\mathrm{e}^{i\theta\cdot z}\,\mathrm{d}\theta \] 在 \(z=(0, 0)\) 处为 1，在其它位置均为 0 这一简单事实。

上面的讨论对任意维数都适用，\(\mathbb{Z}^d\) 上的简单随机游动其特征函数为 \(\frac{1}{2}\sum_{i=1}^d\cos\theta_i\)，关于 \(\mathbb{P}(S_n=y)\) 的类似表达式仍然成立。

二维随机游动的势核

势核可以看作是 Green 函数在二维情形的替代物：在 \(d\geq3\) 时，\(\mathbb{Z}^d\) 上的简单随机游动的 Green 函数 \(G(x,y)\) 定义为从 \(x\) 出发的随机游动访问 \(y\) 的期望次数： \[G(x, y) = \mathbb{E}_x\left(\sum_{k=1}^\infty\mathbf{1}\{S_k=y\}\right)=\sum_{k=1}^\infty \mathbb{P}_x(S_k=y).\] 由于二维随机游动是常返的，上面的级数在 \(d=2\) 时发散，所以上述 Green 函数的定义失效，但是我们还是想定义一个类似 Green 函数的调和函数，结果发现 Green 函数的"差"对应的级数是收敛的，这就引出了下面势核的定义。

用记号 \(\mathbb{P}_n(x, y)\) 表示从点 \(x\) 出发的随机游动，经过 \(n\) 步以后到达 \(y\) 的概率。显然此概率具有平移不变的性质： \[ \mathbb{P}_n(x, y)=\mathbb{P}_n(0, y-x). \] 定义二维随机游动的势核 (potential kernel) 为 \[ a(x)=\sum_{k=0}^\infty\left[\mathbb{P}_k(0, 0) - \mathbb{P}_k(x, 0)\right]. \] 即 \(a(x)\) 是极限 \[ a(x)=\lim_{n\to\infty}\sum_{k=0}^n\left[\mathbb{P}_k(0, 0) - \mathbb{P}_k(x, 0)\right]=\lim_{n\to\infty}a_n(x). \] 由定义可见 \(a(0)=0\)，但是我们还得说明这个级数对任何 \(x\in\mathbb{Z}^2\) 确实是收敛的。为此注意到 \[ \mathbb{P}_k(0, 0)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\phi^k(\theta)\,\mathrm{d}\theta \] 和 \[ \mathbb{P}_k(x, 0)=\mathbb{P}_k(0, -x)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\mathrm{e}^{i\theta\cdot x}\phi^k(\theta)\,\mathrm{d}\theta, \] 于是 \[ a_n(x)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}(1-\phi^{n+1}(\theta))\,\mathrm{d}\theta. \] 由于 \(|1-\phi^{n+1}(\theta)|\leq 2\) 对任何 \(n\geq0\) 和 \(\theta\in\mathbb{T}\) 成立，所以如果我们能证明 \(\dfrac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\) 在 \(\mathbb{T}\) 上可积，并且 \(\phi^{n+1}(\theta)\to0,\mathrm{a.e.}\) 的话，就可以使用控制收敛定理对上式两边取极限，即得 \[ a(x)=\lim_{n\to\infty}a_n(x) = \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\,\mathrm{d}\theta. \] 注意到 \(\phi(\theta)=\frac{1}{2}(\cos\theta_1+\cos\theta_2)\) 只在 \(\mathbb{T}\) 上有限个点处满足 \(|\phi(\theta)|=1\)，其余均为 \(|\phi(\theta)|<1\)，所以 \(\phi^n(\theta)\to0\) 在 \(\mathbb{T}\) 上几乎处处成立。

另一方面初等不等式 \(|1-\mathrm{e}^{i\theta\cdot x}|\leq |x||\theta|\) 总是成立的，并且存在正数 \(\lambda>0\) 使得 \[ 1-\phi(\theta)=1-\frac{1}{2}(\cos\theta_1+\cos\theta_2)\geq\lambda(\theta_1^2+\theta_2^2)=\lambda|\theta|^2 \] 对任何 \(\theta\in\mathbb{T}\) 成立 (函数 \((1-\cos t)/t^2\) 在 \([-\pi, \pi]\) 上具有正的最小值 \(c\)，取 \(\lambda=c/2\) 即可)，所以 \[ \frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\leq\frac{|x|}{\lambda|\theta|}. \] 而 \(1/|\theta|\) 在二维的情形是 \(\mathbb{T}\) 上 Lebesgue 可积的: \[\int_T\frac{1}{|\theta|}\,\mathrm{d}\theta \leq \int_0^{\sqrt{2}\pi}\int_0^{2\pi}\frac{1}{|\theta|}\cdot|\theta|\,\mathrm{d}\theta\,\mathrm{d}\alpha = 2\sqrt{2}\pi^2<\infty.\]

所以 \(\dfrac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\) 是 Lebesgue 可积的，这就证明了极限 \(a(x)\) 对任何 \(x\) 几乎处处存在。

定理 1： 势核 \(a(x)=\sum\limits_{k=0}^\infty\left[\mathbb{P}_k(0, 0) - \mathbb{P}_k(x, 0)\right]\) 几乎处处有限且等于 \[a(x)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\,\mathrm{d}\theta.\]

势核在除去原点之外是调和的

我们接下来证明势核 \(a(x)\) 在除去原点之外都是调和的： \[ a(x)=\frac{1}{4}\sum_{y\sim x}a(y),\quad \forall x\in\mathbb{Z}^2\backslash\{0\}. \] 为此记随机变量 \(N_x^n\) 为从 \(x\) 出发的随机游动在前 \(n\) 步到访原点的次数，即 \(N_x^{n}=\sum_{k=0}^n\mathbf{1}\{S_k=0\}\)，则 \[ a(x)=\lim_{n\to\infty}(\mathbb{E}N_0^n-\mathbb{E}N_x^n). \] 注意到对任何 \(x\in\mathbb{Z}^2\backslash\{0\}\) 有 \[ N_x^n=\frac{1}{4}\sum_{y\sim x}N_y^{n-1}, \] 所以 \[\begin{align*} \mathbb{E}N_0^n-\mathbb{E}N_x^n&= \mathbb{P}_0(S_n=0)+\mathbb{E}N_0^{n-1}-\frac{1}{4}\sum_{y\sim x}\mathbb{E}N_y^{n-1}\\&= \mathbb{P}_0(S_n=0)+\frac{1}{4}\sum_{y\sim x}[\mathbb{E}N_0^{n-1}-\mathbb{E}N_y^{n-1}]. \end{align*} \] 两边令 \(n\to\infty\) 并注意 \(\mathbb{P}_0(S_n=0)\to 0\) 即得所证。

我们已经知道 \(a(0)=0\)，其实也不难得出 \(a(\pm e_i)=1\) 来：根据对称性 \(N_y^{n}\) 在原点的四个邻居 \(\{\pm e_1,\pm e_2\}\) 处的值应该相等，这次我们对 \(\mathbb{E}N_0^n\) 进行分解并注意初始时刻 0 也算一次，所以有 \[ \mathbb{E}N_0^n = 1 + \frac{1}{4}\sum_{y\sim 0}N_y^{n-1} = 1 + N_{e_1}^{n-1}. \] 从而 \[\begin{align*} \mathbb{E}N_0^n-\mathbb{E}N_{e_1}^n&=(1 + N_{e_1}^{n-1})-(\mathbb{P}_{e_1}(S_n=0) + N_{e_1}^{n-1})\\&=1-\mathbb{P}_{e_1}(S_n=0). \end{align*} \] 两边令 \(n\to\infty\) 即得 \(a(e_1)=1\)。

采用下一节的方法，我们可以通过计算积分得出 \(a(e_1+e_2)=\frac{4}{\pi}\)，\(a(2e_1)=4-\frac{8}{\pi}\)，等等，其示意图如下：

势核的渐进估计

我们关心的是势核 \(a(x)\) 当 \(|x|\to\infty\) 时的渐进大小，为此我们有如下定理：

定理 2： \[\lim_{|x|\to\infty} a(x) - \frac{2}{\pi}\ln |x| = \frac{2}{\pi}\gamma+\frac{\ln 8}{\pi}\approx 1.0293737.\] 其中 \(\gamma\approx 0.5772156649\) 是 Euler 常数。

我想当你看到这个定理的时候，应该发现我们已经快要触摸到文章开头的结论了吧？想多了，真正麻烦的地方才刚开始。 这里我们需要首先论证 \(a(x)\) 的渐进行为只与长度 \(|x|\) 有关，与 \(x\) 方向无关，然后用一个特殊的方向 \(x=(n, n)\) 代入 \(a(x)\) 的表达式计算积分值。

证明： 第一步是论证 \(a(x)\) 的渐进行为不依赖于 \(x\) 方向。我们的思路是取一个函数 \(g(\theta)\)，使得积分 \[\begin{equation} 0 < \frac{1}{(2\pi)^2}\int_{\mathbb{T}}\left[\frac{1}{1-\phi(\theta)}-\frac{1}{g(\theta)}\right]\,\mathrm{d}\theta=c < \infty, \label{eq:decompose} \end{equation} \] 然后把 \(a(x)\) 的积分表示改写为 \[ \begin{align*} a(x)&=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{g(\theta)}\,\mathrm{d}\theta+\frac{1}{(2\pi)^2}\int_{\mathbb{T}}(1-\mathrm{e}^{i\theta\cdot x})\left[\frac{1}{1-\phi(\theta)}-\frac{1}{g(\theta)}\right]\,\mathrm{d}\theta\\&=I(x)+J(x). \end{align*} \] 根据 Riemann-Lebesgue 引理，第二个积分 \(\lim\limits_{|x|\to\infty}J(x)=c\)，只要再分析积分 \(I(x)\) 即可。

这里的 \(g(\theta)\) 可以取为 \(|\theta|^2/4\)，我们来验证这一点。注意到 \[\frac{1}{1-\phi(\theta)}-\frac{1}{g(\theta)}= \frac{1}{1-\phi(\theta)}-\frac{4}{|\theta|^2} = \frac{4|\theta|^2}{1-\phi(\theta)}\cdot\frac{1}{|\theta|^4}\left[\phi(\theta)-1+\frac{|\theta|^2}{4}\right]. \] 记右边的两个乘积项分别为 \(\chi(\theta)=\frac{4|\theta|^2}{1-\phi(\theta)}\) 和 \(\psi(\theta)=|\theta|^{-4}\left[\phi(\theta)-1+\frac{|\theta|^2}{4}\right]\)。 为了证明 \(\chi(\theta)\psi(\theta)\) 在 \(\mathbb{T}\) 上可积，注意到我们之前已经证明了在 \(\mathbb{T}\) 上存在正数 \(\lambda>0\) 使得 \(1-\phi(\theta)\geq \lambda|\theta|^2\)，所以 \(\chi(\theta)\leq 4/\lambda\) 在 \(\mathbb{T}\) 上是有界的，只要再证明 \(\psi(\theta)\) 在 \(\mathbb{T}\) 上可积即可。而 \[\begin{equation} \phi(\theta)-1+\frac{|\theta|^2}{4}=\mathbb{E}\left[\mathrm{e}^{i\theta\cdot X} - 1 - i\theta\cdot X - \frac{1}{2}(i\theta\cdot X)^2\right]. \end{equation} \] 注意这里使用了 \(\mathbb{E}(\theta\cdot X)=0\) 和 \(\mathbb{E}(\theta\cdot X)^2=\dfrac{|\theta|^2}{2}\)。 由于对任何实数 \(z\) 都有不等式 (见 Durrett 教材引理 3.3.19) \[ \left|\mathrm{e}^{iz} - 1 - iz - \frac{(iz)^2}{2}\right|\leq\frac{|z|^3}{6}, \] 所以 \[ \phi(\theta)-1+\frac{|\theta|^2}{4}\leq\frac{1}{6}\mathbb{E}|\theta\cdot X|^3\leq\frac{1}{6}\mathbb{E}|\theta|^3|X|^3=\frac{|\theta|^3}{6}\mathbb{E}|X|^3, \] 从而 \[ \psi(\theta)=|\theta|^{-4}\left[\phi(\theta)-1+\frac{|\theta|^2}{4}\right]\leq|\theta|^{-4}\cdot\frac{|\theta|^3}{6}\mathbb{E}|X|^3=\frac{M}{|\theta|}. \] 这里 \(0< M=\dfrac{\mathbb{E}|X|^3}{6} <\infty\) 是正数。由于我们已经看到 \(|\theta|^{-1}\) 在 \(\mathbb{T}\) 上是可积的，所以 \(\psi(\theta)\) 也是可积的，这就说明了 \(\lim\limits_{|x|\to\infty}J(x)=c\) 确实成立。

对于 \(I(x)\) 我们通过极坐标变换来计算它，由于 \(I(x)\) 的积分区域 \(\mathbb{T}\) 是矩形，所以我们把 \(I(x)\) 分解成两部分： \[ I(x)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{|\theta|^2/4}\,\mathrm{d}\theta = \frac{1}{\pi^2}\int_{\mathbb{T}}\frac{1-\cos(\theta\cdot x)}{|\theta|^2}\,\mathrm{d}\theta=I_1+I_2. \] 其中 \(I_1\) 为在圆形区域 \(|\theta|\leq\pi\) 上的积分，\(I_2\) 为在矩阵区域剩下部分上的积分。

\(I_2\) 是比较好处理的，这是因为在其区域上 \(1/|\theta|^2\) 可积，所以根据 Riemann-Lebesgue 引理， \[ \lim_{|x|\to\infty}\frac{1}{\pi^2}\int_{\theta\in\mathbb{T},|\theta|>\pi}\frac{1-\cos(\theta\cdot x)}{|\theta|^2}\,\mathrm{d}\theta=\frac{1}{\pi^2}\int_{\theta\in\mathbb{T},|\theta|>\pi}\frac{1}{|\theta|^2}\,\mathrm{d}\theta < \infty. \] 所以 \(I_2(x)\) 有一个不依赖于 \(x\) 方向的极限值。

而对 \(I_1(x)\) 从表达式明显可见它是与 \(x\) 方向无关的： \[ I_1(x)=\frac{1}{\pi^2}\int_{|\theta|\leq\pi}\frac{1-\cos(\theta\cdot x)}{|\theta|^2}\,\mathrm{d}\theta. \] 事实上用一个旋转矩阵 \(A\) 乘以 \(x\) 等同于对 \(\theta\) 作变元代换 \(\theta'=A^{-1}\theta\)，这显然保持积分不变。所以取 \(x\) 为实轴正方向，并作极坐标代换 \(\theta=(r,\alpha)\) 即得 \[ \begin{align*} I_1(x)&= \frac{1}{\pi^2}\int_{|\theta|\leq\pi}\frac{1-\cos(\theta\cdot x)}{|\theta|^2}\,\mathrm{d}\theta\\&= \frac{1}{\pi^2}\int_0^{2\pi}\mathrm{d}\alpha\int_0^\pi\frac{1-\cos(|x|r\cos\alpha)}{r}\,\mathrm{d}r\\&= \frac{2}{\pi^2}\int_0^{\pi}\mathrm{d}\alpha\int_0^{\pi}\frac{1-\cos(|x|r\cos\alpha)}{r}\,\mathrm{d}r\\&= \frac{4}{\pi^2}\int_0^{\frac{\pi}{2}}\mathrm{d}\alpha\int_0^{\pi}\frac{1-\cos(|x|r\sin\alpha)}{r}\,\mathrm{d}r\\&= \frac{4}{\pi^2}\int_0^{\frac{\pi}{2}}\mathrm{d}\alpha\int_0^{\pi |x|\sin\alpha}\frac{1-\cos u}{u}\,\mathrm{d}u. \end{align*} \] 其中内层的积分可以改写为 \[ \left(\int_0^1 \frac{1-\cos u}{u}\,\mathrm{d}u-\int_1^\infty\frac{\cos u}{u}\,\mathrm{d}u\right)+\int_1^{\pi |x|\sin\alpha}\frac{1}{u}\,\mathrm{d}u+\int_{\pi |x|\sin\alpha}^\infty\frac{\cos u}{u}\,\mathrm{d}u. \] 注意第一个积分 \[ \int_0^1 \frac{1-\cos u}{u}\,\mathrm{d}u-\int_1^\infty\frac{\cos u}{u}\,\mathrm{d}u=\gamma \] 是 Euler 常数 (Euler 常数的另一种等价表示形式)，第二个积分等于 \[\ln\pi + \ln |x| + \ln\sin u,\] 以及第三个积分满足 \[ \lim_{|x|\to\infty}\int_0^{\frac{\pi}{2}}\mathrm{d}\alpha\int_{\pi |x|\sin\alpha}^\infty\frac{\cos u}{u}\,\mathrm{d}u=0. \] 所以 \[ \lim_{|x|\to\infty} I_1(x)-\frac{2}{\pi}\ln|x|=\frac{2}{\pi}(\gamma+\ln\pi-\ln2). \] 这就证明了 \(a(x)\) 在渐进意义下确实等于 \(\dfrac{2}{\pi}\ln|x|\) 加上一个常数。

为了计算这个常数的值，我们选择对角线方向上的特殊值 \(x=(n,n)\) 并代入 \(a(x)\) 的表达式中： \[ a(n,n)=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\cos n(\theta_1+\theta_2)}{1-\frac{1}{2}(\cos\theta_1+\cos\theta_2)}\,\mathrm{d}\theta=\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\cos n(\theta_1+\theta_2)}{1-\cos\frac{\theta_1+\theta_2}{2}\cos\frac{\theta_1-\theta_2}{2}}\,\mathrm{d}\theta. \] 作变元代换 \(u=\frac{\theta_1+\theta_2}{2},v=\frac{\theta_1-\theta_2}{2}\)，此变换的 Jacobian 为 \(1/2\)，于是 \[ a(n,n)=\frac{2}{(2\pi)^2}\int_{|u|+|v|\leq\pi}\frac{1-\cos 2nu}{1-\cos u\cos v}\,\mathrm{d}u\mathrm{d}v. \] 显然此积分在四个象限内的值都相等，所以它等于第一象限内积分值的 4 倍： \[ a(n,n)=\frac{2}{\pi^2}\int_{\substack{0\leq u,v\leq\pi,\\u+v\leq\pi}}\frac{1-\cos 2nu}{1-\cos u\cos v}\,\mathrm{d}u\mathrm{d}v. \] 注意如果把上式的积分区域放大为 \(0\leq u,v\leq \pi\) 的话积分值也会放大 2 倍 (作代换 \(u\to\pi-u,v\to\pi- v\) 会把积分区域变为 \(0\leq u,v\leq\pi, u+v\geq\pi\) 并保持积分值不变)，所以 \[ a(n,n)=\frac{1}{\pi^2}\int_{0\leq u,v\leq\pi}\frac{1-\cos 2nu}{1-\cos u\cos v}\,\mathrm{d}u\mathrm{d}v=\frac{1}{\pi^2}\int_0^\pi\mathrm{d}u\int_0^\pi\frac{1-\cos 2nu}{1-\cos u\cos v}\,\mathrm{d}v. \] 接下来我们要用到的是 \(\frac{1}{1-\cos u\cos v}\) 作为 \(v\) 的函数其不定积分的原函数为 \[ \frac{-2}{\sin u}\tan^{-1}\left(\sin\frac{u-v}{2}\csc\frac{u+v}{2}\right). \] 这一步在所有的文献里都是直接跳过的，我是在 Wolfram Alpha 的在线积分计算器里面输入

1

integrate 1/(1-cos(u)cos(v)) dv

得到的。于是 \[ \begin{align*} a(n,n)&= \frac{1}{\pi}\int_0^\pi\frac{1-\cos 2nu}{\sin u}\,\mathrm{d}u\\ &= \frac{2}{\pi}\int_0^\pi\frac{\sin^2 nu}{\sin u}\,\mathrm{d}u\\&= \frac{2}{\pi}\int_0^\pi\sum_{k=1}^n\sin (2k-1)u\,\mathrm{d}u\\&= \frac{4}{\pi}\sum_{k=1}^n\frac{1}{2k-1}. \end{align*} \] 从而 \[ \begin{align*}&\lim_{n\to\infty}\left[a(n,n)-\frac{2}{\pi}\ln\sqrt{2}n\right]=\lim_{n\to\infty}\left[\frac{4}{\pi}\sum_{k=1}^n\frac{1}{2k-1}-\frac{2}{\pi}\ln\sqrt{2}n\right]\\&= \lim_{n\to\infty}\left[\frac{4}{\pi}\sum_{k=1}^{2n}\frac{1}{k}-\frac{4}{\pi}\ln 2n\right]+\lim_{n\to\infty}\left[\frac{2}{\pi}\sum_{k=1}^{n}\frac{1}{k}-\frac{2}{\pi}\ln n\right]+\frac{\ln8}{\pi}\\&= \frac{4}{\pi}\gamma-\frac{2}{\pi}\gamma+\frac{\ln 8}{\pi}\\&= \frac{2}{\pi}\gamma+\frac{\ln 8}{\pi}\\&\approx 1.0293737056545709. \end{align*}\] 定理得证。

上面这些讨论基本上是对 Spitzer 著作中内容的重新表述，利用局部中心极限定理可以证明极限的误差项大约是 \(O(|x|^{-2})\) 量级的，即

定理 3：\[a(x) = \frac{2}{\pi}\ln|x| + \frac{2\gamma+\ln8}{\pi} + O(|x|^{-2}).\]

证明见 Lawler 一书的 4.4 节。

最后一击

到目前为止我们已经完成了所有的准备工作，只要再用一点点离散鞅的知识 (可料停时定理足矣) 就可以得出 A, B 获胜概率的渐进表达式。虽然剩下的部分已经没有什么难点，但这个时候要更加耐心点。

先做一些记号的约定。

1. 记 \(B(r)\) 是平面上半径为 \(r\) 的圆盘，\(\partial B(r)\) 是圆周 \(|x|=r\)。
2. 设 \(x\) 满足 \(0<|x|<r\) 是\(B(r)\) 内一点，\(S_n\) 是从 \(x\) 出发的随机游动在 \(n\) 时刻的位置，\(S_0=x\)。
3. 记 \(\tau_{0}=\min\{n\geq1:\, S_n=0\}\)，\(\tau_{\partial B(r)}=\min\{n\geq1:\, |S_n|\geq r\}\)。于是 \(\tau_{0}\) 和 \(\tau_{\partial B(r)}\) 分别是 \(S_n\) 首次到达原点的时刻和首次走出 \(B(r)\) 的时刻。记 \(\tau=\min\{\tau_{0},\tau_{\partial B(r)}\}\)，则 \(\tau_{0},\,\tau_{\partial B(r)},\,\tau\) 都是停时。

为了能够使用可料停时定理，我们首先需要说明 \(\{a(S_{n\wedge\tau})\}\) 是一个鞅，且停时 \(\tau\) 满足可料停时定理的条件。由于 \(a(x)\) 在任何 \(x\ne 0\) 处调和，所以 \(\{a(S_{n\wedge\tau}),n\geq0\}\) 是一个鞅是没有问题的。

注意到 \(\{S_{n\wedge\tau}\}\) 是一个限制在 \(B(r)\) 内的随机游动，它访问其中任何一点的期望步数都是有限的，所以 \(\mathbb{E}\tau<\infty\)。其次根据上一节给出的 \(a(x)\) 的渐进估计，不难证明对任何 \(x\in\mathbb{Z}^2\) 以及单位向量 \(e\in\mathbb{Z^2}\)，\(|a(x+e)-a(x)|\) 是一致有界的，即存在 \(M>0\) 使得总有 \(|a(x+e)-a(x)|\leq M\) 成立。所以停时 \(\tau\) 满足可料停时定理的条件，从而

\[\begin{align*} a(x)&=a(S_0)=\mathbb{E}_xa(S_{\tau})\\&= p\cdot\mathbb{E}_x\left[a(S_{\tau_{\partial B(r)}})|\tau_{\partial B(r)}<\tau_{0}\right]+(1-p)\cdot\mathbb{E}_x\left[a(S_{\tau_{0}})|\tau_{0}<\tau_{\partial B(r)}\right]. \end{align*}\]

其中 \(p=\mathbb{P}(\tau_{\partial B(r)}<\tau_{0})\) 正是随机游动在回到原点之前逃出区域 \(B(r)\) 的概率。但是又注意到 \(a(S_{\tau_{0}})=a(0)=0\)，所以上面式子中第二项恒为 0，即 \[p=\frac{a(x)}{\mathbb{E}_x\left[a(S_{\tau_{\partial B(r)}})|\tau_{\partial B(r)}<\tau_{0}\right]}. \]

记上面的分母为 \(g=\mathbb{E}_x\left[a(S_{\tau_{\partial B(r)}})|\tau_{\partial B(r)}<\tau_{0}\right]\)，则 \(g\) 是势核 \(a(\cdot)\) 在圆周 \(\partial B(r)\) 上关于一个条件概率测度的积分，而我们已经看到势核 \(a(y)\) 是近似球对称的，它只依赖于 \(|y|\)。当随机游动刚好走到 \(B(r)\) 范围之外时，其位置 \(y\) 未必正好落在圆周上，但是必然有 \(r\leq |y|<r+1\)，这个时候 \(a(y)\) 和 \(a(r)\) 只会相差 \(O(r^{-1})\)，这一点可以很容易通过定理 3 得出： \[\begin{align*}a(x+e)-a(x)&=\frac{1}{\pi}\ln\frac{\langle x+e, x+e\rangle}{|x|^2}+O(|x|^{-2})\\ &=\frac{1}{\pi}\ln(1+\frac{2\langle x,e\rangle+1}{|x|^2})+O(|x|^{-2})\\ &=\frac{1}{\pi}\left(\frac{2\langle x,e\rangle}{|x|^2}+\frac{1}{|x|^2}-\frac{2\langle x,e\rangle^2}{|x|^4}\right)+O(|x|^{-2})\\&=O(|x|^{-1}).\end{align*}\] 最后一步中 \(|\langle x,e\rangle|\leq |x|\) 是 \(O(|x|)\) 的。

所以 \(g\) 作为 \(a(y)\) 在 \(\partial B(r)\) 附近的一些值在一个条件概率下的加权组合，其值近似等于 \[\frac{2}{\pi}\ln r + \frac{2\gamma+\ln8}{\pi} + O(r^{-1}).\]

至此我们就证明了如下结论：

定理 4： 设 \(x\in B(r)\) 且 \(x\ne 0\)，考虑从 \(x\) 出发的简单随机游动，则 \[\mathbb{P}_x(\tau_{\partial B(r)} < \tau_0) = \frac{a(x)}{\dfrac{2}{\pi}\ln r + \dfrac{2\gamma+\ln8}{\pi} + O(r^{-1})}.\]

本文开头的赌局的答案就蕴含在这个定理的结论中：由于从原点出发的随机游动第一步必然走到某个邻居 \(x\in\{\pm e_1,\pm e_2\}\) 上，所以从原点出发的随机游动能够逃逸到 \(B(r)\) 之外的概率是 \[\frac{1}{4}\sum_{x\in\{\pm e_1,\pm e_2\}}\mathbb{P}_x(\tau_{\partial B(r)}<\tau_{0})=\frac{1}{4}\sum_{x\in\{\pm e_1,\pm e_2\}}\frac{a(x)}{\dfrac{2}{\pi}\ln r + \dfrac{2\gamma+\ln8}{\pi}+O(r^{-1})}.\] 而 \(a(x)\) 在这四个点上的值都是 1，所以这个概率值等于 \[\dfrac{1}{\dfrac{2}{\pi}\ln r + \dfrac{2\gamma+\ln8}{\pi} + O(r^{-1})}\approx\left(\dfrac{2}{\pi}\ln r + 1.0293737\right)^{-1},\quad r\to\infty,\] 这也正是我们之前介绍的 B 的获胜概率！

结语

洋洋洒洒一大篇，总算回答了开头提出的一个小问题。你可能要问了：诶？这只是二维的情形呀，如果是三维太阳系中的真·随机游动，A 和 B 获胜的概率又该怎么算？这种情形方法其实是类似的，需要估计势核 Green 函数的阶，然后仿照定理 4 进行估计。可以证明在维数 \(d>2\) 时，\(G(x)=G(0,x)\) 的大小近似为 \[ G(x)=\frac{\gamma_d}{|x|^{d-2}} + O(|x|^{-d}). \] 其中 \(\gamma_d\) 是一个只与 \(d\) 相关的常数。详情可见 Lawler 的书 4.3 节。

本文选择 \(d=2\) 情形讨论是因为它更有趣，而且这里的结论在后面的文章中会用到。下篇文章见！

上一篇：二维随机游动 （二）：一个随机的完美迷宫分别有多少死角、直路、拐角、岔路和十字路口？

下一篇：Todd-Coxeter 算法和 3D/4D 均匀多胞体