gaohong5250的个人博客分享 http://blog.sciencenet.cn/u/gaohong5250

博文

为什么随机游走的醉汉不会返回原点? 精选

已有 3280 次阅读 2020-10-29 15:44 |个人分类:随机过程|系统分类:论文交流| 随机游走、随机过程

一、随机游走问题

1905年,英国统计学家Pearson在《自然》杂志上公开求解随机游走问题(Random Walk Problem:如果一个醉汉走路时每步的方向和大小完全随机,经过一段时间之后,在什么地方找到他的可能性最大?

1921年,匈牙利数学家Polya在研究随机游走问题后,证明了“一维或二维随机游走具有常返性”的随机游走定理,从而得出了随机游走的醉汉最终会返回原点的结论。

日本著名数学家角谷静夫通俗形象地将Polya随机游走定理表述为:喝醉的酒鬼总能找到回家的路。因此,随机游走定理也被称为酒鬼回家定理

二、与高尔顿板实验结果不符

高尔顿板是英国生物统计学家高尔顿(Galton)专门设计用来演示一维随机游走及正态分布现象的实验装置 。

高尔顿板.png

图1 高尔顿板随机游走实验

高尔顿板上的每一个圆点表示钉在板上的钉子,钉子之间的距离彼此相等,呈三角形排列,上一层每一颗钉子的位置恰好位于下一层两颗钉子的正中间。

当小球从最上方的入口落下时,小球每次碰到钉子后向左、右两个方向落下的概率各为50%,直到最后落入底部的一个格子内。

小球的下落过程就相当于一维简单随机游走。把大量小球逐个从入口处放下,只要高尔顿板的面积足够大、钉子数量足够多,落在底部格子内的小球将形成与正态分布曲线相似的中间高、两边低的钟形曲线。

如果高尔顿板面积足够大,小球在下落过程中将逐渐向左右两个方向扩散,表明一维简单随机游走的小球(醉汉)随时间远离原点。

三、与随机游走模型的数字特征不一致

《随机过程》教科书给出了一维简单随机游走的数学模型

[公式]

式中 [公式] 、 [公式] ,…, [公式] 为独立同分布 [公式] 随机变量。当 [公式] 时,称为从原点出发的一维简单随机游走。

一维简单随机游走向左移动一步的概率与向右移动一步的概率相等,有

[公式]

由于 [公式] , [公式] ,因此一维简单随机游走 [公式] 的数学期望和方差为

[公式]

[公式]

表明一维简单随机游走 [公式] 的方差与步数 [公式] 成正比

方差是用来刻画随机变量偏离均值分散程度的数字特征,度量的是所有样本轨道(小球或醉汉)偏离均值的发散程度,因此, [公式] 表明,随着步数 [公式] 的增加,大量一维简单随机游走的小球或醉汉会远离原点

图2给出了大量一维简单随机游走醉汉的样本轨道仿真曲线,显然,所有样本轨道在第 [公式] 步时的位置服从 [公式] 正态分布。从图中可以看出,对于其中任何一条样本轨道(醉汉),都随步数 [公式] 的增加远离原点,与高尔顿板的实验结果相同 。

随机游走仿真.png

图2 一维简单随机游走样本轨道

四、Polya随机游走定理的证明方法

Polya随机游走定理只证明了随机游走具有常返性(Recurrence),即

[公式]

常返性只表示随机变量 [公式] (醉汉集合)返回原点无穷多次的概率等于1,但不能说明样本轨道 [公式] (一个醉汉)最终一定会返回原点。

假设有无数个醉汉从原点出发,在第 [公式] 步时,所有醉汉的位置服从 [公式] 正态分布,因此,随机游走过程具有如下两个重要性质:

(1)随机游走是一个扩散过程,醉汉样本整体向远离原点的方向扩散;

(2)在原点始终可以看到醉汉,也就是说,在原点看到醉汉的概率等于1。

Polya只是利用概率计算方法证明了第二个性质,却得出了所有醉汉最终会返回原点的结论。

五、随机游走位移公式

Pearson的随机游走问题是求解样本轨道 [公式] 的时间性质,而非随机变量 [公式] =0的概率。

[公式] 为独立同分布随机变量,即 [公式] 的样本轨道 [公式] 在不同时刻互不相关,因此 [公式] 的时间自相关函数为

[公式]

式中 [公式] 为单位冲击序列。

根据维纳-辛钦定理,平稳随机过程的自相关函数与其功率谱密度之间构成一对傅里叶变换,因此 [公式] 的功率谱密度为

[公式]

表明 [公式] 的功率谱密度在整个频率轴上均匀分布,因此 [公式] 为白噪声时间序列。

由前面一维随机游走随机变量 [公式] 模型,可直接写出样本轨道 [公式] 的模型

[公式] = [公式]

可将上式改写为

[公式]

式中为 [公式] 为 [公式] 在区间 [公式] 上的算数平均值,其物理意义为一维随机游走的质点(醉汉)在区间 [公式] 上的平均速度。

因此,一维随机游走的位移 [公式] 等于其平均速度 [公式] 与步数 [公式] 的乘积, [公式] 的变化规律就完全取决于 [公式] 的特性。

从信号分析的角度看,白噪声序列 [公式] 包含了所有频率的谐波分量, 在区间[公式]上不可能对所有频率的谐波分量进行整周期截取,因此频谱泄漏效应会导致 [公式] 中出现直流分量,[公式] 就是随机信号 [公式] 在区间[公式]上的直流分量。

白噪声序列 [公式] 是随机序列,由 [公式] 构造出的 [公式] 也是随机的,其方差为

[公式]

当 [公式] 充分大时,[公式] 的方差趋于零,[公式] 趋于一个常数,因此,一维随机游走的位移[公式]与步数[公式]成正比,随着步数 [公式] 的增加,醉汉会远离远点。





http://wap.sciencenet.cn/blog-3418723-1256235.html

上一篇:《随机过程》教科书中一个导致范式危机的低级错误
下一篇:反证法证明随机游走的醉汉不可能返回原点

14 武夷山 李毅伟 刘钢 谢维 张启峰 黄永义 黄河宁 王明 王安良 杜占池 胡大伟 文克玲 张晓良 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (17 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-27 22:35

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部