引入
想象一只甲虫在一个弯曲的管子里, 假定管子是无限长的 , 这个小生物无休止的随机游走, 它每次在管子里随机的向前或向后移动一步. 最终它能回到起点的概率是多少？[1]
这是著名的“随机游走”(Random Walks)问题. 最早是于1905年, 由卡尔·皮尔逊提出.
我们先简单来分析一下, 不妨将管子看成是一个整数轴, 甲虫在数轴上随机游走, 从 开始, 每一步都以 的概率移动 (向左)或 (向右). 那么5步以后, 它可能在哪些位置呢？
若 步中有 步向左, 步向右, 不管先后顺序, 甲虫最终会落在 , 根据组合计数原理, 可知总共有 种方式即 条路径.
具体的是：左右右右右, 右左右右右, 右右左右右, 右右右左右, 右右右右左.
要正式定义甲虫走过的路径, 我们可以采用独立随机变量 , 每一个变量分别有 的概率为 , 或 .
更一般的, 一维随机游走问题可定义如下：
每过一个单位时间, 游走者从数轴位置 出发以固定概率随机向左或向右移动一个单位. 不妨将 时刻游走者的位置记为 , 则有 , 其中 为相互独立的随机变量, 满足 .
根据是否规定边界, 随机游走问题又分为无边界和有边界随机游走问题.
最经典的一维有边界随机游走问题是赌徒输光问题和酒鬼失足问题,
nload="this.removeAttribute('width'); this.removeAttribute('height'); this.removeAttribute('onload');" />
赌徒在赌场赌博, 赢的概率是 , 输的概率 , 每次的赌注为 元, 假设赌徒最开始时有赌金 元, 赢了赌金加 元, 输了赌金减 元. 问赌徒输光的概率是多少？
nload="this.removeAttribute('width'); this.removeAttribute('height'); this.removeAttribute('onload');" />
一个醉鬼行走在一头是悬崖的道路上, 酒鬼从距离悬崖仅一步之遥的位置出发, 向前一步或向后退一步的概率皆为 , 问酒鬼失足掉入悬崖的概率是多少？
这两个问题都是有边界的随机游走问题, 文章开头的甲虫问题是无边界的随机游走问题.
有边界的随机游走
对于一维有边界的随机游走问题, 我们关心的是游走者最终是否会到达边界点, 以及到达边界点的概率是多少. 下面我们对这个问题做一分析.
假设初始位置为 , 先考虑双边界问题, 边界为 和 , 其中 , 、 为整数. 游走者每个单位时间移动一次, 向左、向右移动的概率都为 ,到达任一边界后停止移动.
若用 表示初始位置为 时最终落入边界 的概率. 显然我们会有 , 和 , 即初始位置为边界的情况.
若 , 则考虑其下一次移动. 有 的概率向左到达 , 有 的概率向右到达 .
则由全概率公式可得,
整理得到 .
下面是具体的计算过程.
利用 ,
可得 ,
累加法可得, .
由 , ,
可得 .
同理用 表示初始位置为 时最终落入边界 的概率,
可得 .
对于单边界情况, 可以令 得到. 即得到 . 这意味着单边界的随机游走者最终必然会落入边界.
将这个结论用在“赌徒输光问题”上,如果赌徒不设止盈目标的话, 那么最终的结局就是输光本金.
进一步我们还可以思考下面这些问题.
当向左、右移动的概率不等时, 以上结果会发生哪些改变？
在赌本为 的情况下, 输光前赌徒可以玩多少把？
若设置一个止盈目标 , 则赌徒在输光前达到止盈目标的概率为多少？
增加赌本, 对赌徒在输光前到达止盈目标的概率影响有多大？
对于一维无边界随机游走问题, 我们关心的是游走者是否能回到初始位置, 以及回到初始位置的概率是多少？
这个问题可以这样思考：
游走者从原点出发一步之后到了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.