随机游走问题

引入

想象一只甲虫在一个弯曲的管子里, 假定管子是无限长的 , 这个小生物无休止的随机游走, 它每次在管子里随机的向前或向后移动一步. 最终它能回到起点的概率是多少？[1]

这是著名的“随机游走”(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.

来源：数来数趣

编辑：cc

转载内容仅代表作者观点

不代表中科院物理所立场

如需转载请联系原公众号

扫码进入“科学与中国”小程序，可观看以院士科普视频为代表的优秀科普视频，第一时间获取中国科学院公众科学日、科学节等科普活动报名信息。

1.2.

3.

4.

5.

6.

7.

8.

9.

10.