一维简单随机游走常返性证伪

高宏*

（清华大学 精密仪器系）

2.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.02.0Department of Precision Instrument,Tsinghua University清华大学 精密仪器系1000841380131525062789898北京市海淀区清华大学紫光大楼四层东区gaohong@mail.tsinghua.edu.cn高宏（1960年），男，副教授，测试信号分析与处理高宏GAO Hong高宏 2.02.02.02.02.02.02.02.02.02.02.02.02.02.02.01*|*期刊*|*Karl Pearson. The Problem of the Random Walk[J]. Nature,1905, 72（1865）:294.<CR>2*|*专著*|*Gerald L. Alexanderson .The Random Walks of George Polya[M]. Providence: American Mathematical Society, 2000.<CR>3*|*专著*|*Rick Durrett, Probability: Theory and Examples[M], Cambridge：Cambridge University Press, 2010.<CR>4*|*专著*|*钱敏平、龚光鲁、陈大岳、章复熹. 应用随机过程[M]. 北京：高等教育出版社，2017.<CR>5*|*专著*|*王丽霞. 概率论与随机过程：理论、历史及应用[M]. 北京：清华大学出版社，2012.<CR>6*|*期刊*|*高宏. 非平稳随机过程样本轨道研究方法错误及纠正[EB/OL]. 北京：中国科技论文在线 [2020-01-23]. 一维简单随机游走常返性证伪|Disproving the recurrence of one-dimensional simple random walk|*|1|高宏|GAO Hong|清华大学 精密仪器系|Department of Precision Instrument,Tsinghua University|高宏（1960年），男，副教授，测试信号分析与处理|北京市海淀区清华大学紫光大楼四层东区|100084|gaohong@mail.tsinghua.edu.cn|62789898|13801315250

摘要：一维简单随机游走是一种具有离散时间参数和离散状态空间的基本随机过程。本文从一维简单随机游走的常返性推导出了一维简单随机游走的方差与中心极限定理相悖的结论，从而证明了一维简单随机游走的常返性不能成立。本文依据一维简单随机游走定义和大数定律，推导出了一维简单随机游走样本轨道的位移公式和自相关函数，得出了一维简单随机游走的位移与时间成正比的结论，从而推翻了波利亚随机游走定理，并纠正了喝醉的酒鬼最终会返回原点的谬误。

关键词：马尔可夫过程；随机游走；常返性

中图分类号：O211.6

Disproving the recurrence of one-dimensional simple random walk

GAO Hong

(Department of Precision Instrument,Tsinghua University)

Abstract: One-dimensional simple random walk is a basic random process with discrete time parameters and discrete state space. This paper derives the conclusion that the variance of the one-dimensional simple random walk is contrary to the Central Limit Theorem from the recurrence of the one-dimensional simple random walk, thus proving that the recurrence of the one-dimensional simple random walk cannot be established. Based on the definition of the one-dimensional simple random walk and the Law of Large Numbers, this paper derives the displacement formula and autocorrelation function of the sample path of one-dimensional simple random walk. The displacement of one-dimensional simple random walk is proportional to time. This conclusion overturned Polya's random walk theorem and corrected the fallacy that a drunk man will eventually find his way home.

Key words: Markov process;Random Walk; Recurrence

引言

一维简单随机游走是概率论学科中的一种基本随机过程，许多重要的随机过程都可由它派生出来。例如布朗运动可看作是简单随机游走的极限，简单随机游走也可看作是对布朗运动的采样。1905年，英国统计学家皮尔逊在《自然》杂志上公开求解随机游走问题[1]：假设一个酒鬼醉的非常严重，完全丧失了方向感，走路时随机地向前或向后一步步移动，问经过一段时间以后，在哪里找到他的可能性最大？匈牙利数学家波利亚在研究随机游走问题后，得出了从原点出发的酒鬼最终会返回原点的结论，并于1921年提出了著名的“一维简单随机游走是常返的”随机游走定理[2]。

本文从一维简单随机游走的常返性出发，推导出了一维简单随机游走的方差与中心极限定理相悖的结论，从而用归谬法证明了一维简单随机游走的常返性不能成立。本文依据一维简单随机游走定义和大数定律，推导出了一维简单随机游走样本轨道位移公式和自相关函数，得出了一维简单随机游走样本轨道的位移与时间成正比的结论，从而推翻了波利亚随机游走定理并纠正了“喝醉的酒鬼最终会返回原点”的谬误。

一维简单随机游走定义及其数字特征

定义：设X1，X2，…，Xi，…为独立同分布（i.i.d.）随机变量，P(Xi=1)= P(Xi=-1)=1/2，S0=0，则称

Sn=S0+X1+X2+…+Xn （1）

为从原点S0出发的一维简单随机游走。

由一维简单随机游走的定义，有E(Xi)=0，D(Xi)=1，因此Sn的数学期望和方差为

E(Sn)=0 （2）

D(Sn)=n （3）

一维简单随机游走常返性证伪

随机游走定理：一维简单随机游走是常返的[3]。

若一维简单随机游走是常返的，则有P(Sn=0，i.o.)=1，表示从原点出发的一维简单随机游走返回原点无穷多次的概率是1，这表明一维简单随机游走一定能回到起点[4]。

假定一维简单随机游走是常返的，则经过足够长的步数n后，所有一维简单随机游走样本轨道都返回到原点S0，即Sn=0，因此有

D(Sn)=0 （4）

表示一维简单随机游走Sn的方差为零，与式（3）方差等于n的结论相矛盾，故开始所作假设不真，即“一维简单随机游走是常返的”结论不能成立。

此外，一维简单随机游走的常返性与中心极限定理相矛盾。由一维简单随机游走定义，Sn就是中心极限定理所假设的独立同分布随机变量之和[5]，根据中心极限定理，当n充分大时，Sn趋于（0，n）正态分布，表明大量随机游走的样本轨道分布在整个状态空间，而不是全部返回到原点S0。因此，一维简单随机游走的常返性与中心极限定理相悖，一维简单随机游走的常返性必定为假。

一维简单随机游走是一种典型的马尔可夫链，具有无后效性。当我们知道一维简单随机游走第n步的位置Sn时，它将来的位置与第n步之前的位置无关。但常返性却表示将来的位置与过去的位置S0有关，因此“常返性”与“无后效”矛盾，“常返性”为假。

一维简单随机游走的常返性与高尔顿板（Galton board）实验结果严重不符。高尔顿板是用来演示一维简单随机游走和验证中心极限定理的实验装置，大量的实验结果显示：小球在下落过程中逐渐向左右两个方向偏移，实验证明一维简单随机游走的小球随时间远离原点。

波利亚解题方法错误

一维简单随机游走Sn是定义在参数集T和状态空间Ω上的二元函数。对于固定的时间（步数）n，随机过程Sn是状态变量ω的函数，称为随机变量；对于固定的状态ω，随机过程Sn是时间（步数）n的函数，称为样本轨道或样本函数，记为s(n)。从式（3）可以看出，一维简单随机游走Sn为非平稳随机过程，因此随机变量Sn有空间意义上的集合统计特性，而样本轨道s(n)并无时间意义上的元素统计特性[6]。也就是说，对于一维简单随机游走样本轨道s(n)，只能将其当作时间函数，用函数分析方法研究其位移随时间的变化规律，而不能将其当作随机变量Sn，用概率分析方法来研究s(n)的统计特性。

皮尔逊的随机游走问题实质上是求解随机游走样本轨道s(n)的位移特性，而波利亚却在状态空间求解随机变量Sn=0的概率，首先使研究对象发生了错位。另外，中心极限定理已经清楚地表明，大量从原点出发的一维简单随机游走样本轨道可以到达状态空间中的任意整数点（包括原点），而波利亚却使用不完全归纳法，从少量一维简单随机游走样本轨道返回原点的个别现象，概括出所有一维简单随机游走样本轨道全部返回原点的一般性结论，其结论所断定的范围大大超出了前提所断定的范围，势必会得出错误的结论。

一维简单随机游走位移公式

由式（1）的定义，可写出单个一维简单随机游走样本轨道数学模型

s(n)=x(1)+x(2)+ …+x(n) （5）

式中x(i)（i=1，2，…）为随机变量Xi（i=1，2，…）的样本轨道，是一次随机游走试验中观测到的时间函数。

式（5）表明，一维简单随机游走样本轨道具有很强的记忆性，当前时刻的位移s(n)不仅与当前时刻的x(n)有关，而且与之前所有时刻的x(1)，x(2) ，…，x(n-1)都有关。

由于Xi为独立同分布随机变量，因此Xi为各态历经平稳随机过程，x(i)的时间平均在概率意义上等于Xi的空间平均，x(i)的时间均值和方差分别为

式中为x(n)的算数平均值，其定义为

的物理意义表示一维简单随机游走的质点在区间[0，n] 上的平均速度，或是随机信号x(n)在区间[0，n] 上的直流分量。

Xi为独立同分布随机变量，表示x(i) 在不同时刻互不相关，因此x(i)的时间自相关函数Rx(k)为

式中δ(k)为单位冲击序列，其定义为

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

Px(ω)在整个频率轴上均匀分布，表明x(i)为白噪声序列。

由式（8）的算数平均值定义，式（5）的样本轨道可改写为

因此可以得出下面的随机游走定理：

随机游走定理：一维简单随机游走样本轨道的位移等于其平均速度与时间的乘积。

根据大数定律[5]，算数平均值反映了x(n)中的确定性部分，当n充分大时，趋于一个接近时间均值的常数。因此，一维简单随机游走样本轨道的位移s(n)随时间线性增长，与物理学中机械运动质点位移与时间成正比的结论完全一致。

注意，即使n充分大时，也不等于零。这是因为x(i)中包含了所有频率的谐波分量，x(n)不可能对所有频率的谐波分量进行整周期截取，因此频谱泄漏效应会导致时间序列x(n)中出现直流分量。

从式（12）可以看出，一维简单随机游走样本轨道的位移特性完全取决于平均速度的变化规律，平均速度的方差为

x反映了平均速度围绕时间均值波动的程度。x与成反比，当n<100时， 变化异常剧烈，s(n)表现出很强的随机性；当n充分大时，趋于一个常数，s(n)成为一条斜率为的直线。

由于随机变量Sn是大量样本轨道s(n)的集合，因此当n充分大时，Sn变为一族从原点发出的射线，这些射线在状态空间的位置分布服从式（2）和式（3）描述的一维简单随机游走数字特征，与物理学扩散现象相符。

样本轨道时间自相关函数

由式（5）和式（9），可推导出一维简单随机游走样本轨道s(n)的时间自相关函数

表明一维简单随机游走样本轨道s(n)在很宽的范围内具有相关性，s(n)中存在可以识别和利用的规律，s(n)具有可预测性。

结论

本文从一维简单随机游走的常返性出发，推导出了一维简单随机游走的方差与中心极限定理相悖的结论，从而用归谬法证明了一维简单随机游走的常返性不能成立。本文依据一维简单随机游走定义和大数定律，推导出了可揭示一维简单随机游走现象、特征及规律的样本轨道位移公式和自相关函数，得出了一维简单随机游走的位移与时间成正比的结论，从而推翻了波利亚随机游走定理，并纠正了“喝醉的酒鬼最终会返回原点”的谬误。

[参考文献] (References)

[1] Karl Pearson. The Problem of the Random Walk[J]. Nature,1905, 72（1865）:294.
[2] Gerald L. Alexanderson .The Random Walks of George Polya[M]. Providence: American Mathematical Society, 2000.
[3] Rick Durrett, Probability: Theory and Examples[M], Cambridge：Cambridge University Press, 2010.
[4] 钱敏平、龚光鲁、陈大岳、章复熹. 应用随机过程[M]. 北京：高等教育出版社，2017.
[5] 王丽霞. 概率论与随机过程：理论、历史及应用[M]. 北京：清华大学出版社，2012.
[6] 高宏. 非平稳随机过程样本轨道研究方法错误及纠正[EB/OL]. 北京：中国科技论文在线 [2020-01-23].

作者简介：高宏（1960年），男，副教授，测试信号分析与处理. E-mail: gaohong@mail.tsinghua.edu.cn