Shun Li's Notes

随机游走与波利亚常返性定理

477 words
概率论

我们考虑一维格点 上的简单对称随机游走。 设初值位置为原点，每一步等概率地移动到邻近的 个格点之一，记 为第 步后的位置。 我们关心的问题是：游走者是否几乎必然（概率为1）无限次返回原点？

  1. 若概率为 ，称为常返。

  2. 否则称为非常返。

我们考虑的一维情况最简单，考虑 即 发生的概率，显然 ，对于所有奇数 都有 ，因此只需要考虑偶数，记作 。 注意到 意味着要有 步向左， 步向右，总的可选路径为 ，满足要求的路径数为 ，因此

记返回次数为 （不包括初始状态的一次），我们关注 ， 可以定义指示变量 ，那么

根据期望的线性性质：

设 为从原点出发，最终至少回到原点一次的概率（不包括起点本身），那么 和 之间有如下关系：

  1. 如果 ，意味着游走者几乎肯定会在某个有限时间回到原点。回到原点后，整个过程会“重启”。于是它会再次以概率 再次返回，以此类推。所以几乎必然返回无限多次，

  2. 如果 ，那么直接有 概率永不返回，记总返回次数为 ，则

    即使返回之后进行重启，仍然有 的概率永不返回，因此

    计算期望

因此 等价于 。 由于 ，因此

求和发散，即 ，一维对称随机游走是常返的。

Remark

类似的推导可得：二维随机游走也是常返的，但三维及以上的情况是非常返的，核心差异就体现在对应级数求和的敛散性。

Theorem (波利亚常返性定理)

在 上的简单对称随机游走当且仅当 时是常返的。

Remark

一个更通俗形象的说法是：酒鬼总能回家；醉鸟永远回不了家。

概率论