二维随机游动 (一):逃出太阳系可没有你想象的那么难!

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

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

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

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

题目其实是在说,醉汉的行为是 \(\mathbb{Z}^2\) 上的简单随机游动,而我们熟知 \(\mathbb{Z}^d\) 上的随机游动在 \(d=1,2\) 时是常返的,所以醉汉以概率 1 会走遍平面上的所有角落,即 A, B 这场赌局是以概率 1 可以分出胜负的。从直观上,\(A\) 的获胜概率应该更大,因为醉汉回到原点显然是个更容易发生的事件:醉汉的路径可能是选择一个方向一步迈出去再一步迈回来,或者干脆绕一个圈子,而走出太阳系那么远的距离则困难得多。事实也是如此,实际上 A, B 获胜概率的“分水岭”大约在 \(R\approx 4.2\) 米处 1,随着逃逸半径 \(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 的概率获胜!是不是很反直觉呢?

本文下面就来介绍怎样得出上面获胜概率的渐进公式。这里的讲述主要参考了 Spitzer 的教材 2,好处是比较简单易懂,缺点是没有给出势核误差项的渐进估计。使用局部中心极限定理的话可以给出势核误差项的渐进估计 3,但是我想本文还是克制一点,尽量保持在初等的范围内比较好。

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

  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)\)\[\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.\label{eq:sn}\tag{1} \end{equation} \] 其中 \(\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{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*} \] 这里我们利用了级数 \(\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}{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\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\) 即可),所以 \[ \frac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\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_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\) 都有定义。

定理 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\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\}\) 出发的随机游动,使用单步转移概率,我们有 \[N_x^n=\frac{1}{4}\sum_{y\sim x}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{align*} \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{align*} \] 两边令 \(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\) 时的渐进大小,为此我们有如下定理:

定理 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)\) 的积分表示 \[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\),我们来验证这一点: \[\frac{1}{1-\phi(\theta)}-\frac{1}{g(\theta)}= \frac{1}{1-\phi(\theta)}-\frac{4}{|\theta|^2} = \underbrace{\frac{4|\theta|^2}{1-\phi(\theta)}}_{\chi(\theta)}\cdot\underbrace{\frac{1}{|\theta|^4}\left[\phi(\theta)-1+\frac{|\theta|^2}{4}\right]}_{\psi(\theta)}. \] 我们要证明乘积 \(\chi(\theta)\psi(\theta)\)\(\mathbb{T}\) 上可积。注意到我们之前已经证明了存在 \(\lambda>0\) 使得在 \(\mathbb{T}\) 上有 \(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}=\mathop{\mathrm{\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{T}\) 是关于原点对称的区域,以及 \(X^2\equiv(1,1)\),所以 \[\begin{align*} \mathop{\mathrm{\mathbb{E}}}{(\theta\cdot X)}&=\mathop{\mathrm{\mathbb{E}}}{(x_1\theta_1 + x_2\theta)}=0,\\ \mathop{\mathrm{\mathbb{E}}}{(\theta\cdot X)^2}&=\mathop{\mathrm{\mathbb{E}}}{(x_1\theta_1+x_2\theta_2)^2}=\mathop{\mathrm{\mathbb{E}}}{(\theta_1^2+\theta_2^2)}=\mathop{\mathrm{\mathbb{E}}}{|\theta|^2}. \end{align*}\] 由于对任何实数 \(z\) 都有不等式 4 \[ \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}\mathop{\mathrm{\mathbb{E}}}{|\theta\cdot X|^3}\leq\frac{1}{6}\mathop{\mathrm{\mathbb{E}}}{|\theta|^3|X|^3}=\frac{|\theta|^3}{6}\mathop{\mathrm{\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}\mathop{\mathrm{\mathbb{E}}}{|X|^3}=\frac{M}{|\theta|}. \] 这里 \(0< M=\frac{\mathop{\mathrm{\mathbb{E}}}{|X|^3}}{6} <\infty\) 是正数。而前面已经看到 \(1/|\theta|\)\(\mathbb{T}\) 上是可积的,所以 \(\psi(\theta)\) 也是可积的,这就说明了 \(\lim\limits_{|x|\to\infty}J(x)=c\) 确实成立。

我们还需要说明 \(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\) 方向的极限值。

\(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\),由于 \(A\) 是正交矩阵所以 \(|\theta'|=|\theta|\) 并且变换的 Jacobian 值是 +1,所以积分不变。

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

由于 \(I_1(x)\) 的值与 \(x\) 方向无关,我们可以取 \(x\) 为实轴正方向 \((|x|, 0)\) 来计算积分的值。作极坐标代换 \(\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{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 常数的另一种等价表示形式),它给出的外层积分值是 \(\frac{2}{\pi}\gamma\);第二个求和项等于 \[\ln\pi + \ln |x| + \ln\sin\alpha,\] 它给出的外层积分值是 \[\frac{2}{\pi}\left(\ln\pi + \ln |x|-\ln 2 \right).\] 第三个求和项满足 5 \[ \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. \] 此积分的区域是 \(\mathbb{T}\) 中满足 \(|u|+|v|\leq \pi\) 的部分,它等于整个 \(\mathbb{T}\) 上积分的一半,如图所示:

所以 \[ a(n,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. \] 我们用留数来计算上面的积分。设 \(k=\cos u\)

\[\begin{aligned}\int_{-\pi}^{\pi}\frac{1}{1-k\cos v}\,\mathrm{d}v&=\oint_{|z|=1} \frac{1}{1-\frac{k}{2}\left(z+\frac{1}{z}\right)} \frac{\mathrm{d} z}{i z}\quad(z=e^{iv})\\ &=\oint_{|z|=1} \frac{2i}{kz^2-2z+k} \mathrm{d}z\\ &=\oint_{|z|=1} \frac{2i}{k(z-z_1)(z-z_2)} \mathrm{d}z\quad\left(z_{1,2}=\frac{1\pm\sqrt{1-k^2}}{k}\right)\\ &=\frac{2 i}{k}2\pi i\;\mathrm{Res}_{z=z_2}\left(\frac{1}{(z-z_1)(z-z_2)}\right)\\ &=-\frac{4\pi}{k}\frac{1}{z_2-z_1}\\ &=\frac{2\pi}{\sqrt{1-k^2}}. \end{aligned} \]

外层同样使用围道积分,

\[\begin{aligned}&\frac{1}{4\pi^2}\int_{-\pi}^{\pi}(1-\cos(2nu))\int_{-\pi}^{\pi}\frac{1}{1-\cos u\cos v}\,\mathrm{d}u\,\mathrm{d}v \\&=\frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{1-\cos(2nu)}{|\sin\left(u\right)|}\,\mathrm{d}u\\ &=\frac{1}{\pi}\mathrm{Re}\int_{0}^{\pi}\frac{1-e^{2inu}}{\sin u}\,\mathrm{d}u\quad(z=e^{iu})\\ &=\frac{1}{\pi}\mathrm{Re}\int_{C}\frac{1-z^{2n}}{\frac{1}{2i}\left(z-z^{-1}\right)}\, \frac{\mathrm{d} z}{i z}\quad\text{(形变半圆路径} C \text{为直线)}\\ &=\frac{2}{\pi}\mathrm{Re}\int_{1}^{-1}\frac{1-z^{2n}}{z^2-1}\, \mathrm{d} z\\ &=\frac{2}{\pi}\int_{-1}^1\sum_{k=0}^{n-1}x^{2k}\, \mathrm{d}x\\ &=\frac{4}{\pi}\sum_{k=1}^{n}\frac{1}{2k-1}. \end{aligned}\] 从而 \[ \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 节。下文要用到这个渐进估计的一个推论:

推论:对任何 \(x\in\mathbb{Z}^2\setminus\{0\}\) 和单位向量 \(|e|=1\)\[a(x + e) - a(x) = O(|x|^{-1}).\] 特别地存在常数 \(M>0\) 使得 \(|a(x+e)-a(x)|\leq M\) 对任何 \(x\) 恒成立。

证明

\[\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\left(1+\frac{2\langle x,e\rangle+1}{|x|^2}\right)+O(|x|^{-2})\\ &\leq\frac{1}{\pi}\ln\left(1+\frac{2}{|x|}+\frac{1}{|x|^2}\right)+O(|x|^{-2})\\&=O(|x|^{-1}).\end{align*}\]

最后一击

到目前为止我们已经完成了所有的准备工作,只要再用一点点离散鞅的知识 (可料停时定理) 就可以得出 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})\}\) 是一个鞅是没有问题的。

注意到 \(\{S_{n\wedge\tau}\}\) 是一个限制在 \(B(r)\) 内的随机游动,它访问其中任何一点的期望步数都是有限的,所以 \(\mathop{\mathrm{\mathbb{E}}}{\tau}<\infty\)。其次根据上一节的 推论\(|a(x+e)-a(x)|\) 是一致有界的,所以停时 \(\tau\) 满足 可料停时定理的条件,从而

\[\begin{align*} a(x)&=a(S_0)=\mathbb{E}_x\,a(S_{\tau})\\&= p\cdot\mathbb{E}_x\,\left[a(S_{\tau_{\partial B(r)}})\mid\tau_{\partial B(r)}<\tau_{0}\right]+(1-p)\cdot\mathbb{E}_x\,\left[a(S_{\tau_{0}})\mid\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)}})\mid\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|\)。当随机游动刚好走到 \(\partial B(r)\) 时,其位置 \(y\) 未必正好落在圆周上,但是满足 \(r-1< |y|\leq r\)。我们滥用一点记号,对任意的实数 \(r>0\),记 \[a(r) = \frac{2}{\pi}\ln r + \frac{2\gamma+\ln8}{\pi},\] 则根据上一节推论同样的道理,当 \(r-1<|y|\leq r\) 时有 \[|a(y) - a(r)| = O(1/r).\] 所以 \(g\) 作为 \(a(\cdot)\)\(\partial B(r)\) 附近的一些 \(y\) 在一个条件概率下的加权组合,其值等于 \[\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(x)\)\(x\ne 0\) 时才是调和的,从而 \(a(S_{n\wedge \tau})\) 是鞅。

结语

洋洋洒洒一大篇,总算回答了开头提出的一个小问题。你可能要问了:这只是二维的情形呀,如果是三维太阳系中的随机游动,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\) 情形讨论是因为它更有趣,而且这里的结论在后面的文章中会用到。下篇文章见!

 | 

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器