N维随机游走的常返性模拟实验验证

引子

最近痴迷于用Python进行各种随机实验（概率与统计真的太好玩了），甚至尝试用一些蒙特卡洛和数值模拟的方法验证一些数学Theorem。本文将记录我对随机游走定理的实验验证。

先简单介绍一下这个定理。随机游走定理指出，在一维或二维空间中，从起始点出发进行随机运动的点会无限次回到起始点，也就是具有“常返性”；而在大于等于三维的空间中，随机运动的点不具有“常返性”。不具有常返性，不是指不会回来，而是每回来一次，再次回来的概率就会越来越小，直至趋于0。直观上看，就是这个点在回到起始点若干次（也有可能一次都没有）之后，它再也不会回来，而是往原理起始点的方向“扩散”开去。

匈牙利数学家P´olya在1921年证明了该定理，所以这个定理有时候被称为P´olya’s Random Walk Theorem或Po´lya’s Recurrence Theorem。日本著名数学家角谷静夫通俗形象地将Po´lya随机游走定理表述为：喝醉的酒鬼总能找到回家的路，但是喝醉的鸟不能。虽然这个描述有失准确，但是深入人心，因此也有人称该定理为“酒鬼回家定理”。
我在阅读了随机游走定理的一个证明¹之后，萌生了通过Python进行模拟实验验证的想法。本文记录了验证的方法和实验结果。

模型建立

随机游走问题的深入分析

我们首先需要建立一个可以准确表述和分析随机游走定理的数学模型。在一个N维空间中有一个点，称其为“粒子”（仅仅只是数学上的点），不妨设这个点的起始坐标为（有N个点），即坐标系的原点。粒子从原点出发进行随机的运动，具体来说，每次往随机一个坐标轴的方向或反方向移动一个单位的距离。在一维空间中，就是随机往左或往右走一步（每一步都是一样长的），在二维空间中就是上下左右四个方向选一个走。上述这种离散的随机运动模式可以简单地概括为“N维晶格上的随机游走”，因为粒子的每个可能位置是离散的，把相邻的点连接起来（注意这些连线其实就是粒子可能行走路径），就形成了一个类似晶格的空间。

随机游走定理的一个前提是，粒子具有无限长的运动时间，也就是粒子可以移动无限步。随机游走定理指出，在一维和二维晶格中，粒子出发后会以100%的概率回到原点，然后再次离开，那么根据随机游走定理，它一定会第二次回来……它会无限次回到原点。而在大于等于三维的空间中，随机游走的点回到原点的概率小于1。假设粒子出发后第一次回到原点的概率是，那么第二次回来的概率就是。这个概率随着回归次数（粒子回到原点的次数）的增加而指数衰减。所以对于N（）维的情况，粒子回到原点的次数有一个有限的期望。

假设我们能进行N维晶格上随机游走的实验，能够观察无限长的时间并记录粒子的回归次数。而且我们可以进行无限次独立的实验观测。对这无限次观测的结果求平均（其实就得到了期望），我们会发现在一维和二维空间中，回归次数是无限大，而在大于等于三维的空间中回归次数的平均值是一个有限的正实数。当然我们不可能实现这样的理想实验，因为这里有两个“无限”，但是我们可以用较长的时间和较大量的实验次数去近似理想实验。并且从实验结果中观察到“趋于无穷”或“收敛于有限”的趋势。

有限的模型

在计算机中，很容易实现一个有限步随机游走的模拟实验。把N维晶格中的粒子抽象成一个整数数组，这个数组代表了粒子的坐标。每次移动就是对数组中的随机一个数加1或减1。在每次实验中让坐标从原点开始“移动”步，并且进行次这样的实验。其中和会设为一个较大的整数。

一个较困难的问题是，要对这样的模拟实验进行怎样的统计，并从统计结果中观察出随机游走定理的结论。如果直接统计回归次数并取平均，那么存在一个问题，随着实验次数的增加，我们得到的平均值其实是在接近步内的回归次数的期望，而不是上一小节所述的理论上的回归次数期望，所以无论是几维的随机游走，我们得到的期望都会是一个有限的数值，而且从这个数值结果中难以观察到什么趋势。综上，在有限的实验中，步内的回归次数并不是一个很好的统计量。

于是我设计了这样一个统计量，对一次有限随机游走实验，统计一个数值序列，是中的第个元素，它的值等于本次实验中前步内，粒子回到原点的次数。所以是一个有个元素的数值序列，它记录了一次实验中，随着时间的推移，回归次数的增长情况。我们对次实验得到的序列的个样本求平均得到，然后画出的曲线（纵轴表示元素的值，横轴表示元素的序号）。这个曲线描述了（前步内的回归次数）的均值随（时间）的变化情况。
在足够大的情况下，将会非常接近前步内的回归次数的期望随时间变化的曲线，至少已经能体现出它的变化趋势了。我们期望得到的结果是，在一维和二维情况下，我们能观察到一个发散的曲线（无上界），而在三维及更高维度的情况，我们能看到一个收敛的曲线（有上界）。

实验

首先给出实验的代码

import numpy as np
import random

def random_walk(N, T=10000):
    """
        @N: 晶格空间的维数
        @T: 实验步数
    """
    p = np.zeros((N, ))
    origin = np.zeros((N, ))
    moves = [1, -1]
    dims = [*range(N)]
    count = 0
    A = []
    for i in range(T):
        move = random.choice(moves)
        dim = random.choice(dims)
        p[dim] += move
        if (p == origin).all():
            count += 1
        A.append(count)
    return np.array(A)

M = int(1e4) # 重复实验次数
A_sum = 0
for i in range(M):
    A_sum += random_walk(1) # 进行一维情况下的实验
A_bar = A_sum / M

上述代码省略了画图的部分，并只展示了一维情况下的实验。对一二三维情况下的统计情况的可视化如下（因为只要证明了三维是收敛的，四维就是同理可得了，所以我没有做更高维度的实验）

可以看到一维情况下，曲线明显是发散的。但是肉眼难以判断二维和三维的曲线变化趋势。我把二维和三维的曲线图单独拉出来对比如下

二维的曲线增长接近对数曲线，即二维的是类似这样的曲线，因此是发散的；而三维的曲线明显保持平坦的模式，所以可以判断它应该是收敛的，而且从图可知三维随机游走运动的回归次数的期望应该在0.5左右。

上述实验分析验证了我们的猜想。

总结

本文通过模拟实验验证了P´olya随机游走定理，和理论证明相比，实验验证的优势是直观易懂，无需高等的数学知识和技巧，而且能估计得到大于等于三维情况下的回归次数期望的数值结果。

参考

• [1] 喝醉的酒鬼能找到回家的路吗？
• [2] 理论证明