引入
例 1 ( 一维随机游走问题 )
想象一只甲虫在一个弯曲的管子里, 假定管子是无限长的 , 这个小生物无休止的随机游走, 它每次在管子里随机的向前或向后移动一步. 最终它能回到起点的概率是多少?[1]
这是著名的“随机游走”(Random Walks)问题. 最早是于1905年, 由卡尔·皮尔逊提出.
我们先简单来分析一下, 不妨将管子看成是一个整数轴, 甲虫在数轴上随机游走, 从
若
具体的是:左右右右右, 右左右右右, 右右左右右, 右右右左右, 右右右右左.
要正式定义甲虫走过的路径, 我们可以采用独立随机变量
更一般的, 一维随机游走问题可定义如下:
定义 1 ( 一维随机游走 )
每过一个单位时间, 游走者从数轴位置
根据是否规定边界, 随机游走问题又分为无边界和有边界随机游走问题.
最经典的一维有边界随机游走问题是赌徒输光问题和酒鬼失足问题,
例 2 ( 赌徒输光问题 )
赌徒在赌场赌博, 赢的概率是
例 3 ( 酒鬼失足问题 )
一个醉鬼行走在一头是悬崖的道路上, 酒鬼从距离悬崖仅一步之遥的位置出发, 向前一步或向后退一步的概率皆为
这两个问题都是有边界的随机游走问题, 文章开头的甲虫问题是无边界的随机游走问题.
有边界的随机游走
对于一维有边界的随机游走问题, 我们关心的是游走者最终是否会到达边界点, 以及到达边界点的概率是多少. 下面我们对这个问题做一分析.
假设初始位置为
若用
若
则由全概率公式可得,
整理得到
下面是具体的计算过程.
利用
可得
累加法可得,
由
可得
同理用
可得
对于单边界情况, 可以令
将这个结论用在“赌徒输光问题”上, 如果赌徒不设止盈目标的话, 那么最终的结局就是输光本金.
进一步我们还可以思考下面这些问题.
当向左、右移动的概率不等时, 以上结果会发生哪些改变?
在赌本为
的情况下, 输光前赌徒可以玩多少把? 若设置一个止盈目标
, 则赌徒在输光前达到止盈目标的概率为多少? 增加赌本, 对赌徒在输光前到达止盈目标的概率影响有多大?
无边界的随机游走
对于一维无边界随机游走问题, 我们关心的是游走者是否能回到初始位置, 以及回到初始位置的概率是多少?
这个问题可以这样思考:
游走者从原点出发一步之后到了1或-1, 根据对称性, 可以只考虑一半, 即从1出发的随机游走会不会回到原点. 根据上面对于有单边界的随机游走问题的分析, 可知最终随机游走者会回到原点. 于是我们说一维随机游走是常返的. [2]
事实上, 对于一维无边界随机游走问题, 匈牙利数学家波利亚在1921年时就证明了甲虫能回到起点的概率是1. 也就意味着一维空间的随机游走几乎是必然可以返回起点的.
除了研究一维随机游走问题, 我们还可以将问题推广, 思考高维随机游走问题.
如果将甲虫放置在两个空间维度即平面的原点处, 然后甲虫向东南西北四个方向随机走一步, 继续无限制地随机游走下去, 那么最终甲虫会回到起点吗? 波利亚的研究表明, 这种随机游走最终会把甲虫带回到起点的概率也是1.[1]
波利亚的研究还表明, 三维空间是第一种甲虫有可能迷失方向的欧几里得空间. 甲虫在三维空间的宇宙中无限制地随机游走, 最终会回到原点的概率只有34%.
在更高的n维空间中, 甲虫返回原点的机会甚至更小, 大约只有
参考文献
Clifford A. Pickover. The Math Book[M]. NewYork:Union Square & Co. 2009:112.
陈大岳.从随机游动谈起. https://www.math.pku.edu.cn/teachers/dayue/Homepage/random-walk-and.pdf.