随机游走问题

引入

这是著名的“随机游走”(Random Walks)问题. 最早是于1905年, 由卡尔·皮尔逊提出.

我们先简单来分析一下, 不妨将管子看成是一个整数轴, 甲虫在数轴上随机游走, 从开始, 每一步都以的概率移动(向左)或(向右). 那么5步以后, 它可能在哪些位置呢？

若步中有步向左, 步向右, 不管先后顺序, 甲虫最终会落在, 根据组合计数原理, 可知总共有种方式即条路径.

具体的是：左右右右右, 右左右右右, 右右左右右, 右右右左右, 右右右右左.

要正式定义甲虫走过的路径, 我们可以采用独立随机变量, 每一个变量分别有的概率为, 或.

更一般的, 一维随机游走问题可定义如下：

根据是否规定边界, 随机游走问题又分为无边界和有边界随机游走问题.

最经典的一维有边界随机游走问题是赌徒输光问题和酒鬼失足问题,

这两个问题都是有边界的随机游走问题, 文章开头的甲虫问题是无边界的随机游走问题.

有边界的随机游走

对于一维有边界的随机游走问题, 我们关心的是游走者最终是否会到达边界点, 以及到达边界点的概率是多少. 下面我们对这个问题做一分析.

假设初始位置为, 先考虑双边界问题, 边界为和, 其中, 、为整数. 游走者每个单位时间移动一次, 向左、向右移动的概率都为, 到达任一边界后停止移动.

若用表示初始位置为时最终落入边界的概率. 显然我们会有, 和, 即初始位置为边界的情况.

若, 则考虑其下一次移动. 有的概率向左到达, 有的概率向右到达.

则由全概率公式可得,

整理得到 .

下面是具体的计算过程.

利用 ,

可得 ,

累加法可得, .

由 , ,

可得 .

同理用 表示初始位置为时最终落入边界的概率,

可得 .

对于单边界情况, 可以令 得到. 即得到. 这意味着单边界的随机游走者最终必然会落入边界.

将这个结论用在“赌徒输光问题”上, 如果赌徒不设止盈目标的话, 那么最终的结局就是输光本金.

进一步我们还可以思考下面这些问题.

• 当向左、右移动的概率不等时, 以上结果会发生哪些改变？

• 在赌本为的情况下, 输光前赌徒可以玩多少把？

• 若设置一个止盈目标, 则赌徒在输光前达到止盈目标的概率为多少？

• 增加赌本, 对赌徒在输光前到达止盈目标的概率影响有多大？

无边界的随机游走

对于一维无边界随机游走问题, 我们关心的是游走者是否能回到初始位置, 以及回到初始位置的概率是多少？

这个问题可以这样思考：

游走者从原点出发一步之后到了1或-1, 根据对称性, 可以只考虑一半, 即从1出发的随机游走会不会回到原点. 根据上面对于有单边界的随机游走问题的分析, 可知最终随机游走者会回到原点. 于是我们说一维随机游走是常返的. [2]

事实上, 对于一维无边界随机游走问题, 匈牙利数学家波利亚在1921年时就证明了甲虫能回到起点的概率是1. 也就意味着一维空间的随机游走几乎是必然可以返回起点的.

除了研究一维随机游走问题, 我们还可以将问题推广, 思考高维随机游走问题.

如果将甲虫放置在两个空间维度即平面的原点处, 然后甲虫向东南西北四个方向随机走一步, 继续无限制地随机游走下去, 那么最终甲虫会回到起点吗？ 波利亚的研究表明, 这种随机游走最终会把甲虫带回到起点的概率也是1.[1]

波利亚的研究还表明, 三维空间是第一种甲虫有可能迷失方向的欧几里得空间. 甲虫在三维空间的宇宙中无限制地随机游走, 最终会回到原点的概率只有34%. 在更高的n维空间中, 甲虫返回原点的机会甚至更小, 大约只有的概率. 值得注意的是, 这个概率就是甲虫在第二步就原路返回起点的概率. 也就是说如果甲虫不能在第二步就回家的话, 它几乎注定会永远迷失下去了.

参考文献

1. Clifford A. Pickover. The Math Book[M]. NewYork:Union Square & Co. 2009:112.

2. 陈大岳.从随机游动谈起. https://www.math.pku.edu.cn/teachers/dayue/Homepage/random-walk-and.pdf.