这是一个关于二维随机游动的小系列，整理自我研究生时的读书笔记，每篇文章会从一个有趣直观的问题出发，介绍随机游动理论中的一个相关知识。这些问题是我精心挑选的，总体上都比较基础，并不涉及多么复杂的知识。但是请你也不要期待很快就可以看完问题的解答，因为它们不是那种用个什么巧办法三两下就能搞定的急转弯！

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

我们把问题分解为以下步骤来解决：

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)=\mathop{\mathrm{\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)\)。

用特征函数我们可以非常方便地表示 \(n\) 步以后醉汉位于任意 \(y\in\mathbb{Z}^2\) 的概率 \(\mathbb{P}(S_n=y)\)： \[ \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.\label{eq:sn}\tag{1} \] 其中 \(\mathbb{T}=[-\pi,\pi]\times[-\pi, \pi]\)。这是因为根据特征函数定义有 \[ \phi^n(\theta)=\mathop{\mathrm{\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{aligned} \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{aligned} \] 这里我们利用了级数 \(\sum_{x\in\mathbb{Z}^2}\mathbb{P}(S_n=x)\mathrm{e}^{i\theta\cdot(x-y)}\) 绝对收敛（从而可以交换求和顺序），以及对 \(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}{d}\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\mathbb{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\) 的概率。显然此概率满足如下两条性质：

1. \(\mathbb{P}_n(x, y)=\mathbb{P}_n(0, y-x)=\mathbb{P}_n(x-y,0)\).
2. \(\lim_{n\to\infty}\mathbb{P}_n(x,y)=0\).

定义二维随机游动的势核 (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. \] 以及根据 \((\ref{eq:sn})\) \[ \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.\label{eq:an}\tag{2} \] 由于 \(|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.}\) 的话，就可以使用控制收敛定理对 \((\ref{eq:an})\) 两边取极限，即得 \[ 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 <\infty. \] 由于 \(\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}\) 上几乎处处成立。

为了证明 \(\dfrac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\) 在 \(\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\) 即可），所以 \[ \left|\frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\right|\leq\frac{|x|}{\lambda|\theta|}. \] 而 \(1/|\theta|\) 在二维的情形是 \(\mathbb{T}\) 上 Lebesgue 可积的：将积分区域 \(\mathbb{T}=[-\pi,\pi]\times[-\pi,\pi]\) 放大为圆形区域 \(|\theta|\leq\sqrt{2}\pi\)，并用极坐标换元 \(\theta\to(r,\alpha)\) 得到 \[\int_{\mathbb{T}}\frac{1}{|\theta|}\,\mathrm{d}\theta \leq \int_{|\theta|\leq\sqrt{2}\pi}\frac{1}{|\theta|}\,\mathrm{d}\theta=\int_0^{2\pi} \,\mathrm{d}\alpha \int_0^{\sqrt{2}\pi}\frac{1}{r}\cdot r\,\mathrm{d}r = 2\sqrt{2}\pi^2<\infty.\]

所以 \(\dfrac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\) 是 Lebesgue 可积的，这就证明了 \(a(x)\) 对任何 \(x\in\mathbb{Z}^2\) 都有定义。

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

我们接下来证明势核 \(a(x)\) 在除去原点之外都是调和的： \[ a(x)=\frac{1}{4}\sum_{y\sim x}a(y),\quad \forall x\in\mathbb{Z}^2\setminus\{0\}. \] 为此记 \(N_x^n\) 为从 \(x\) 出发的随机游动在前 \(n\) 步到访原点的次数，即 \(N_x^{n}=\sum\limits_{k=0}^n\mathbb{1}_{\{S_k=0\}}\)，则 \[ a(x)=\lim_{n\to\infty}(\mathop{\mathrm{\mathbb{E}}}{N_0^n}-\mathop{\mathrm{\mathbb{E}}}{N_x^n}). \] 对任何从 \(x\in\mathbb{Z}^2\setminus\{0\}\) 出发的随机游动，使用单步转移概率，我们有 \[\mathop{\mathrm{\mathbb{E}}}{N_x^n}=\frac{1}{4}\sum_{y\sim x}\mathop{\mathrm{\mathbb{E}}}{N_y^{n-1}}.\] 此外 \[\mathop{\mathrm{\mathbb{E}}}{N_0^n}=\mathop{\mathrm{\mathbb{E}}}{N_0^{n-1}}+\mathop{\mathrm{\mathbb{E}}}{\mathbb{1}_{\{S_n=0\}}}=\mathop{\mathrm{\mathbb{E}}}{N_0^{n-1}}+\mathbb{P}_0(S_n=0),\] 所以当 \(x\ne0\) 时， \[\begin{aligned} \mathop{\mathrm{\mathbb{E}}}{N_0^n}-\mathop{\mathrm{\mathbb{E}}}{N_x^n} &= \mathbb{P}_0(S_n=0)+\mathop{\mathrm{\mathbb{E}}}{N_0^{n-1}}-\frac{1}{4}\sum_{y\sim x}\mathop{\mathrm{\mathbb{E}}}{N_y^{n-1}}\\&= \mathbb{P}_0(S_n=0)+\frac{1}{4}\sum_{y\sim x}[\mathop{\mathrm{\mathbb{E}}}{N_0^{n-1}}-\mathop{\mathrm{\mathbb{E}}}{N_y^{n-1}}]. \end{aligned} \] 两边令 \(n\to\infty\) 并注意 \(\mathbb{P}_0(S_n=0)\to 0\) 即得 \[ a(x)=0+\frac{1}{4}\sum_{y\sim x}a(y)=\frac{1}{4}\sum_{y\sim x}a(y). \] 即 \(a(x)\) 在任何 \(x\ne 0\) 处是调和的。

由定义我们已经知道 \(a(0)=0\)，其实稍微花点力气也不难得出 \(a(\pm e_i)=1\) 来：根据对称性 \(a(x)\) 在原点的四个邻居 \(\{\pm e_1,\pm e_2\}\) 处的值应该相等，这次我们对 \(\mathop{\mathrm{\mathbb{E}}}{N_0^n}\) 进行分解并注意初始时刻 \(S_0=0\) 也算一次，所以有 \[ \mathop{\mathrm{\mathbb{E}}}{N_0^n} = 1 + \frac{1}{4}\sum_{y\sim 0}\mathop{\mathrm{\mathbb{E}}}{N_y^{n-1}} = 1 + \mathop{\mathrm{\mathbb{E}}}{N_{e_1}^{n-1}}. \] 把 \(\mathop{\mathrm{\mathbb{E}}}{N_{e_1}^n}\) 拆成 \(\mathop{\mathrm{\mathbb{E}}}{N_{e_1}^{n-1}}+\mathbb{P}_{e_1}(S_n=0)\)，得到 \[\mathop{\mathrm{\mathbb{E}}}{N_0^n}-\mathop{\mathrm{\mathbb{E}}}{N_{e_1}^n}=1-\mathbb{P}_{e_1}(S_n=0).\] 两边令 \(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\) 时的渐进大小，为此我们有如下定理：

当你看到这个定理的时候，是不是感觉已经快要接近证明文章开头的结论了呢？那可太抱歉了，真正麻烦的地方才刚开始。这个定理的证明非常棘手，我们需要首先论证 \(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)\) 的积分表示 \[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)=\underbrace{\frac{1}{(2\pi)^2}\int_{\mathbb{T}}\frac{1-\mathrm{e}^{i\theta\cdot x}}{g(\theta)}\,\mathrm{d}\theta}_{I(x)}+\underbrace{\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}_{J(x)}. \] 根据 Riemann-Lebesgue 引理，\(\lim\limits_{|x|\to\infty}J(x)=c\)，即 \(J(x)\) 与 \(x\) 的方向是无关的。

\(g(\theta)\) 可以取为 \(|\theta|^2/4\)，我们来验证这一点：由于 \[1-\phi(\theta)= \frac{|\theta|^2}{4} + O(|\theta|^4).\] 于是当 \(\theta\to0\) 时， \[\frac{1}{1-\phi(\theta)}-\frac{4}{|\theta|^2} = \frac{|\theta|^2-4(1-\phi(\theta))}{|\theta|^2(1-\phi(\theta))}=\frac{O(|\theta|^4)}{O(|\theta|^4)}=O(1). \] 因此这个函数在原点附近有界；在远离原点的紧集上连续有界，所以 在 \(\mathbb{T}\) 上可积。

我们还需要说明 \(I(x)\) 的极限也是与 \(x\) 的方向无关的。把 \(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\) 为在剩下的 \(\{\theta\in\mathbb{T},\, |\theta|>\pi\}\) 区域上的积分。

\(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\) 方向的极限值。

至此我们把 \(a(x)\) 的积分表示为了 \(I_1+I_2+J\) 的形式，并且论证了 \(x\to\infty\) 时后两者的值有限，所以 \(a(x)\) 的渐进主项藏在 \(I_1(x)\) 当中。

记 \(R=|x|\)。由于积分区域是圆盘，可以旋转坐标，可以取 \(x=(R, 0)\)。于是 \[I_1(R)=\frac{1}{\pi^2}\int_{|\theta|\le\pi}\frac{1-\cos(R\theta_1)}{|\theta|^2}\,\mathrm{d}\theta.\] 使用极坐标 \(\theta=(r\cos\alpha,r\sin\alpha)\)，得到 \[\begin{aligned} I_1(R)&=\frac{1}{\pi^2}\int_0^\pi \frac{\mathrm{d}r}{r} \int_{0}^{2\pi} (1-\cos(Rr \cos\alpha))\,\mathrm{d}\alpha\\ &=\frac{2}{\pi}\int_0^\pi\frac{1-J_0(Rr)}{r}\,\mathrm{d}r\\ &=\frac{2}{\pi}\int_0^{\pi R}\frac{1-J_0(t)}{t}\,\mathrm{d}t. \end{aligned}\] 其中 \(J_0(t)\) 是零阶第一类 Bessel 函数。

于是 \[I_1(R)-\frac{2}{\pi}\log R = \frac{2}{\pi}\left[\int_0^1\frac{1-J_0(t)}{t}\,\mathrm{d}t+\log\pi -\int_1^{\pi R}\frac{J_0(t)}{t}\,\mathrm{d}t\right].\] 第一项有限，这是因为 \[1 - J_0(t) = O(t^2),\quad t\to 0.\] 最后一项在 \(R\to\infty\) 时收敛，因为 \[J_0(t) = O(t^{-1/2}).\] 从而 \[\frac{J_0(t)}{t} = O(t^{-3/2})\] ​ 在 \([1,+\infty)\) 上可积。 所以我们有 \[I_1(R)=\frac{2}{\pi}\log R + C_1 + O(R^{-1/2}).\] 其中 \(C_1\) 是某个有限常数。

至此我们证明了在分解 \[a(x)=I(x)+J(x)=I_1(x)+I_2(x)+J(x)\] 中，当 \(|x|\to\infty\) 时，\(I_1-\frac{2}{\pi}\ln|x|\)，\(I_2\) 和 \(J\) 都趋近于有限的极限值，于是极限 \[\lim_{|x|\to\infty}\left(a(x)-\frac{2}{\pi}\ln|x|\right)\] 也存在且有限。为了计算这个极限，我们选择对角线方向 \(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. \] 记 \(A_n=a(n,n)\)，作变元代换 \(u=\frac{\theta_1+\theta_2}{2},v=\frac{\theta_1-\theta_2}{2}\)，此变换的 Jacobian 为 \(1/2\)，于是 \[ A_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. \] 此积分的区域是 \(\mathbb{T}\) 中满足 \(|u|+|v|\leq \pi\) 的部分，它等于整个 \(\mathbb{T}\) 上积分的一半，如图所示：

所以 \[ A_n=\frac{1}{4\pi^2}\int_{-\pi}^\pi\mathrm{d}u\int_{-\pi}^\pi\frac{1-\cos(2nu)}{1-\cos u\cos v}\,\mathrm{d}v. \] 首先计算内层关于 \(v\) 的积分。设 \(k=\cos u\)，

\[\int_{-\pi}^{\pi}\frac{1}{1-k\cos v}\,\mathrm{d}v\stackrel{t=\tan(v/2)}{=}2\int_{-\infty}^\infty\frac{\mathrm{d}t}{(1-k) + (1+k)t^2}=\frac{2\pi}{\sqrt{1-k^2}}=\frac{2\pi}{|\sin u|}.\] 从而 \[A_n = \frac{1}{2\pi}\int_{-\pi}^\pi\frac{1-\cos(2nu)}{|\sin u|}\,\mathrm{d}u=\frac{1}{\pi}\int_0^\pi\frac{1-\cos(2nu)}{\sin u}\,\mathrm{d}u.\]

并且 \[\begin{aligned} A_n - A_{n-1}&=\frac{1}{\pi}\int_{0}^\pi\frac{\cos(2(n-1)u)-\cos(2nu)}{\sin u}\,\mathrm{d}u\\ &=\frac{2}{\pi}\int_{0}^\pi\sin((2n-1)u)\,\mathrm{d}u\\ &=\frac{4}{\pi(2n-1)}. \end{aligned}\] 又因为 \(A_0=0\)，得到 \[A_n = \frac{4}{\pi}\sum_{k=1}^{n}\frac{1}{2k-1}=\frac{4}{\pi}H_{2n}-\frac{2}{\pi}H_n.\] 其中 \[H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}=\log n + \gamma + o(1).\] 是调和数。

从而

\[\begin{aligned}&\lim_{n\to\infty}\left[a(n,n)-\frac{2}{\pi}\ln\sqrt{2}n\right]=\lim_{n\to\infty}\left[\frac{4}{\pi}H_{2n}-\frac{2}{\pi}H_n-\frac{2}{\pi}\ln\sqrt{2}n\right]\\&= \frac{2}{\pi}\gamma+\frac{\ln 8}{\pi}\\&\approx 1.0293737056545709. \end{aligned}\] 定理 4.1 得证。\(\blacksquare\)

最后一击

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

先做一些记号的约定。

1. 记 \(B(r)=\{z\in\mathbb{Z}^2\mid |z|<r\}\) 是平面上半径为 \(r\) 的圆盘内部的格点，定义 \[\partial B(r) = \{y\in\mathbb{Z}^2\mid y\notin B(r),\,\exists z\in B(r),\, y\sim z\}.\]
2. 设 \(x\) 满足 \(0<|x|<r\) 是\(B(r)\) 内一点，\(S_n\) 是从 \(x\) 出发的随机游动在 \(n\) 时刻的位置，\(S_0=x\)。
3. 记 \(\tau_{0}=\min\{n\geq1:\, S_n=0\}\)，\(\tau_r=\min\{n\geq1:\, S_n\notin B(r)\}\)。于是 \(\tau_{0}\) 和 \(\tau_r\) 分别是 \(S_n\) 首次到达原点的时刻和首次走出 \(B(r)\) 的时刻。记 \(\tau=\min\{\tau_{0},\tau_r\}\)，则 \(\tau_{0},\,\tau_r,\,\tau\) 都是停时。

由于 \(S_{n\wedge\tau}\) 的取值是有界区域 \(B(r)\cup\partial B(r)\)，因此存在一个只依赖 \(r\) 的常数 \(C_r\) 使得 \[|a(S_{n\wedge \tau})|\le C_r.\] 又由于势核 \(a(x)\) 在任何 \(x\ne 0\) 处调和，过程 \(\{a(S_{n\wedge\tau})\}\) 是一个鞅。所以 \[a(x) = \mathop{\mathrm{\mathbb{E}}}{a(S_{n\wedge\tau})}.\] 注意到 \(\{S_{n\wedge\tau}\}\) 是一个限制在 \(B(r)\) 内的随机游动，它访问其中任何一点的期望步数都是有限的，所以 \(\mathop{\mathrm{\mathbb{E}}}{\tau}<\infty\)。于是几乎处处有 \[\lim_{n\to\infty}S_{n\wedge \tau}=S_\tau.\] 由控制收敛定理， \[a(x)=\lim_{n\to\infty} \mathop{\mathrm{\mathbb{E}}}{a(S_{n\wedge\tau})} =\mathop{\mathrm{\mathbb{E}}}{a(S_\tau)}=\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau})\mathbb{1}_{\{\tau_0<\tau_r\}}]}+\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau})\mathbb{1}_{\{\tau_r<\tau_0\}}]}.\] 在事件 \(\tau_0<\tau_r\) 上，\(S_\tau=0\)，而 \(a(0)=0\)，所以 \[a(x)=\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau_r})\mathbb{1}_{\{\tau_r<\tau_0\}}]}.\] 令 \(p=\mathbb{P}(\tau_r<\tau_0)\)，利用条件期望的性质，对随机变量 \(X\) 和事件 \(A\) 有 \[\mathop{\mathrm{\mathbb{E}}}{[X\mathbb{1}_A]}=\mathbb{P}(A)\mathop{\mathrm{\mathbb{E}}}{[X|A]}.\] 得 \[a(x) = p\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau_r})|\tau_r<\tau_0]}.\] 从而 \[p = \frac{a(x)}{\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau_r})|\tau_r<\tau_0]}}.\] 我们来估计分母：当随机游动首次走出 \(B(r)\) 的时候，其位置 \(y\) 一定满足 \[y\in\partial B(r),\quad r\le |y| < r+1.\] 由势核的渐进公式， \[a(y) = \frac{2}{\pi}\ln |y| + \frac{2\gamma+\ln 8}{\pi} + o(1).\] 所以 \[0\le \ln|y|-\ln r <\ln(1+\frac{1}{r})=o(1).\] 因此对所有 \(y\in \partial B(r)\) 一致地有 \[a(y) = \frac{2}{\pi}\ln r + \frac{2\gamma+\ln 8}{\pi} + o(1).\] 特别地，取条件期望以后仍然有 \[\mathop{\mathrm{\mathbb{E}}}{[a(S_{\tau_r})|\tau_r<\tau_0]} = \frac{2}{\pi}\ln r + \frac{2\gamma+\ln 8}{\pi} + o(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_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(1)}.\] 而 \(a(x)\) 在这四个点上的值都是 1，所以这个概率值等于 \[\dfrac{1}{\dfrac{2}{\pi}\ln r + \dfrac{2\gamma+\ln8}{\pi} + o(1)}\approx\left(\dfrac{2}{\pi}\ln r + 1.0293737\right)^{-1},\quad r\to\infty,\] 这也正是我们之前介绍的 B 的获胜概率！

我们需要根据第一步将概率进行分解是因为 \(a(x)\) 在 \(x\ne 0\) 时才是调和的，从而 \(a(S_{n\wedge \tau})\) 是鞅。

结语

洋洋洒洒一大篇，总算回答了开头提出的一个小问题。你可能要问了：这只是二维的情形呀，如果是三维太阳系中的随机游动，A 和 B 获胜的概率又该怎么算？这种情形方法其实是类似的，需要估计势核 Green 函数的阶，然后仿照 定理 4.1 进行估计。可以证明在维数 \(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\) 情形讨论是因为它更有趣，而且这里的结论在后面的文章中会用到。下篇文章见！

上一篇：模任何素数都可约的整系数不可约多项式

下一篇：Coupling from the past