殷勤昨夜三更雨 又得浮生一日凉

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

赵亮 / 2020-10-01


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

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

问题: 假设某人以太阳系的中心为原点出发,在一个固定的平面内,以恒为 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.59\) 米处,随着逃逸半径 \(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 的获胜概率!是不是很反直觉呢?想象一下你写了一个程序,通过模拟随机游动来计算返回原点的时间,那可要小心了:虽然程序会以概率 1 在有限时间内结束,但它也有一个不小的概率让你在有生之年都等不到结果!

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

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

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

其中用到的一些随机变量的特征函数和离散鞅的预备知识可以参考 3

二维随机游动的特征函数

我们把某人在 \(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. \label{eq:sny} \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)\) \(\eqref{eq:sny}\) 的类似表达式仍然成立。

二维随机游动的势核

势核可以看作是 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}\) 成立 (函数 \(\dfrac{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 可积的 (极坐标换元即可),从而 \(\dfrac{1-\mathrm{e}^{i\theta\cdot x}}{1-\phi(\theta)}\) 是 Lebesgue 可积的,这就证明了极限 \(a(x)\) 对任何 \(x\) 几乎处处存在。

注意在这个证明中我们用到了 \(1/|\theta|\)\(\mathbb{T}\) 上的可积性,这一点是二维简单随机游动独有的。总结一下:

定理 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\),我们来验证它使得积分 \(\eqref{eq:decompose}\) 有限。 \[ \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}\) 上存在正数 \(\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 的在线积分计算器 里面输入

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 获胜概率的渐进表达式。

\(\tau_{x,0}^+=\min\{n\geq1: S_n=0\}\) 是从 \(x\) 出发的随机游动首次访问原点的时刻,注意这是一个正的随机变量。记 \(B(r)\) 是以原点为中心,半径为 \(r\) 的圆盘区域,\(\partial B(r)\) 是其边界。记 \(\tau_{\partial B(r)}\) 是从 \(x\) 出发的随机游动首次到达 \(\partial B(r)\) 的时刻。最后滥用一点记号,记 \(a(r)=\frac{2}{\pi}\ln r + \frac{2\gamma+\ln8}{\pi}\),则根据定理 3,当 \(|x|=r\) 时有 \(a(x)=a(r)+O(r^{-2})\)

OK,以上就是一点记号上的准备工作,可以表述本节的主要结论了:

定理 4: 设 \(x\in B(r)\)\(x\ne 0\),考虑从 \(x\) 出发的简单随机游动,则 \[ \mathbb{P}_x(\tau_{\partial B(r)} < \tau_{x,0}^+) = \frac{a(x)}{a(r)+O(r^{-1})}. \]

本文开头的赌局的答案就蕴含在这个定理的结论中。实际上从原点出发的随机游动必然第一步走到其某个邻居 \(x\in\{\pm e_1,\pm e_2\}\) 上,而这时 \(a(x)=1\),所以从 \(x\) 出发继续走的话先走到 \(\partial B(r)\) 的概率是 \(1/(a(r)+O(r^{-1}))\),这正是 B 获胜的概率!

证明:记定理中左边的概率为 \(p\)。考虑过程 \(\{a(S_{n\wedge \tau_{x,0}^+}),n\geq0\}\),由于 \(a(x)\) 在原点之外处处调和,此过程是一个鞅。对 \(\tau_{\partial B(r)}\) 使用可料停时定理得到 \[ \begin{align*} a(x)&= a(S_0)=\mathbb{E}_xa(S_{\tau_{\partial B(r)}\wedge \tau_{x,0}^+})\\ &= p\cdot\mathbb{E}_x\left[a(S_{\tau_{\partial B(r)}})|\tau_{\partial B(r)}<\tau_{x,0}^+\right]+(1-p)\cdot\mathbb{E}_x\left[a(S_{\tau_{x,0}^+})|\tau_{\partial B(r)}>\tau_{x,0}^+\right]. \end{align*} \]\[ \begin{align*} g_1&= \mathbb{E}_x\left[a(S_{\tau_{\partial B(r)}})|\tau_{\partial B(r)}<\tau_{x,0}^+\right],\\ g_2&=\mathbb{E}_x\left[a(S_{\tau_{x,0}^+})|\tau_{\partial B(r)}>\tau_{x,0}^+\right]. \end{align*} \] 注意当随机游动走到 \(\partial B(r)\) 时它与圆周 \(|x|=r\) 的距离至多差一个单位向量 \(e\),而 \[ a(x+e)-a(x)=O\left(\ln\frac{|x+e|}{|x|}\right)=O\left(\ln (1+\frac{1}{|x|})\right)= O(|x|^{-1}), \] 所以 \(g_1=a(r)+O(r^{-1})\)。另一方面显然 \(g_2=0\) (因为 \(a(0)=0\)),所以 \[ p=\frac{a(x) - g_2}{g_1 - g_2}=\frac{a(x)}{g_1}=\frac{a(x)}{a(r)+O(r^{-1})}. \] 证毕。

结语

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


  1. Spitzer, F. 1976. Principles of random walk. Second edn. New York: Springer-Verlag. Graduate Texts in Mathematics, Vol. 34.

  2. Lawler, G. F., and Limic, V. 2010. Random walk: a modern introduction. Cambridge Studies in Advanced Mathematics, vol. 123.

  3. Durrett, R. 2019. Probability: theory and examples. Fifth edn. Cambridge Series in Statistical and Probabilistic Mathematics.