随机游走问题频域求解

高宏*

（清华大学 精密仪器系）

2.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*|*译著*|*Clifford A.Pickover. 数学之书：数学史上250个里程碑式的发现[M]. 陈以礼. 重庆：重庆大学出版社，2015.<CR>3*|*期刊*|*王国胜、王震. 谈谈简单随机游动[J]. 德州师专学报, 1998, 14（2）:9-12.<CR>4*|*期刊*|*Jonathan Novak. Polya的随机游走定理[J]. 数学译林，2016，35（3）:281-285.<CR>5*|*期刊*|*高宏. 非平稳随机过程样本轨道研究方法错误及纠正[EB/OL]. 北京：中国科技论文在线 [2020-01-23].随机游走问题频域求解|Frequency Domain Solution of Random Walk Problem|*|1|高宏|GAO Hong|清华大学 精密仪器系|Department of Precision Instrument,Tsinghua University|高宏（1960年），男，副教授，测试信号分析与处理|北京市海淀区清华大学紫光大楼四层东区|100084|gaohong@mail.tsinghua.edu.cn|62789898|13801315250

摘要：随机游走问题是数学史上的一个著名问题，其解决答案被誉为数学史上250个里程碑式的重大发现之一。本文首先指出随机游走问题的本质是求解随机过程样本轨道位移特性，以及Polya使用概率分析方法在状态空间求解样本轨道特性的方法错误和将随机变量常返性用于样本轨道的概念错误。本文使用函数分析方法在频域求解随机游走样本轨道的位移特性，得出了醉汉不断远离原点的结论，从而推翻了Polya醉汉最终一定会返回原点的结论。

关键词：随机游走；样本轨道；状态空间；常返性；

中图分类号：O211.6

Frequency Domain Solution of Random Walk Problem

GAO Hong

(Department of Precision Instrument,Tsinghua University)

Abstract: Random walk is a well-known mathematical problem, and its answer is praised as one of 250 milestones in the history of Mathematics. Firstly, this paper points out that the essence of random walk problem is to solve the sample path characteristics of random process, and Polya's method error in using probability theory to solve the sample path characteristics in state space, and conceptual error of using state space origin as sample path origin. In this paper, the displacement of random walk sample path is solved in frequency domain , and the conclusion that the drunk keeps away from the origin is drawn, which overturns Polya's conclusion that the drunk will eventually return to the origin.

Key words: Random Walk；sample path；state space；recurrent

引言

随机游走（Random Walk）是概率论与随机过程学科中用于描述动态随机现象的一种基本随机过程。液体中悬浮微粒的布朗运动、空气中的烟雾扩散、光纤陀螺中的随机漂移误差和股票市场中的价格波动等随机现象均可用随机游走模型进行描述。

1905年，英国统计学家Pearson在《自然》杂志上公开求解随机游走问题[1]：如果一个醉汉走路时每步的方向和大小完全随机，经过一段时间之后，在什么地方找到他的可能性最大？1921年，匈牙利数学家Polya在研究随机游走问题后，证明一维或二维随机游走返回原点的概率为100%，从而得出了醉汉最终会返回原点的结论，同时提出了著名的随机游走定理。Polya随机游走定理被誉为数学史上250个里程碑式的重大发现之一[2]，日本著名数学家角谷静夫通俗地将其表述为：醉鬼总能找到回家的路。

本文指出了Polya使用概率分析方法在状态空间求解样本轨道位移特性的方法错误，以及把随机变量常返性当做样本轨道特性的概念错误，并使用函数分析方法在频域求解随机游走样本轨道位移特性问题，得出了一维随机游走随时间不断远离原点的结论，推翻了Polya醉汉最终一定会返回原点的错误结论。

随机游走常返性悖论

随机游走过程是一种具有常返性的马尔可夫过程，常返性表示从原点出发的质点最终一定会返回原点。

马尔可夫过程则表明随机游走过程是一种具有“无后效性”或“无记忆性”的随机过程。若随机游走过程X(t)在当前时刻t0的值X(t0)已知，则它在t0时刻之后的状态只与它在t0时刻的状态X(t0)有关，而与它在t0时刻之前的状态无关。

悖论1：假设质点在当前时刻的位置为X(t0)，根据随机游走过程的常返性，质点未来一定会返回原点X(0)，这表示随机游走过程具有记忆性，随机游走过程未来的状态与过去的状态X(0)有关，这与马尔可夫过程的“无后效性”和“无记忆性”矛盾。

悖论2：假设质点在当前时刻的位置为X(t0)，根据马尔可夫过程的“无后效性”，质点未来的位置与过去无关，仅与当前的位置X(t0)有关，因此可认为未来的随机游走过程是以当前的位置X(t0)为起点。由随机游走过程的常返性，质点未来将返回到新的起点X(t0)，与随机游走过程返回到原点X(0)的结论矛盾。

事实上，从原点出发的一维简单随机游走以概率1可到达任何整数点[3]，而Polya仅证明了一维简单随机游走以概率1到达原点，而原点只是随机游走所能到达的所有整数点中的一个点而已。

Polya解题方法错误

Polya使用概率分析方法在随机变量状态空间求解随机游走样本轨道问题，证明了“一维或二维简单随机游走是常返的（recurrent）” 随机游走定理[4]，因而得出了“从原点出发的醉汉以概率1最终返回到原点”的结论。

随机游走过程X（t）是定义在Ω×T上的二元函数，它从状态空间Ω和参数集T两个维度描述随机现象。对于固定的t∈T，X（t）是随机变量；对于固定的ω∈Ω，X（t）是一个定义在T上的确定性时间函数，通常称为样本轨道。为便于区别随机变量和样本轨道，我们将样本轨道简记为小写的x（t），因此，随机变量X（t）是一族样本轨道x（t）的集合。

Pearson的一维随机游走问题可表述为：当时间t足够大时，x（t）如何变化？Pearson的随机游走问题实质上是求解一条样本轨道x（t）的位移特性，而非样本轨道的集合X（t）在状态空间的性质。

随机游走过程为非平稳随机过程，只有集合平均意义上的随机变量统计特性，而无时间意义上的样本轨道统计特性，因此在研究随机游走过程的随机变量X(t)和样本轨道x(t)时，要分别采用概率分析方法和函数分析方法，否则会使研究对象发生错位[5]，得出与事实完全不符的错误结论。

Polya的错误在于，使用概率分析方法求解非平稳随机过程样本轨道问题，最终得出的“常返性”只是描述随机游走过程随机变量的状态空间特性，而不是样本轨道的位移特性。

Polya随机游走定理的“常返性”实质上是随机游走过程随机变量X(t)的“常返性”。当时间t足够大时，P(X(t)=0，i.o.)=1，表示任何时刻都会有样本轨道x(t)位于原点，但不代表所有样本轨道x(t)都位于原点。若将随机变量X(t)的“常返性”用来描述单个样本轨道x(t)位移特性，势必会产生前面的两个悖论，并得出醉汉最终会返回原点的错误结论，将真理变成谬误。

频域求解

一维随机游走模型

设醉汉或质点在水平直线上的位移为x(t)，每隔单位时间Δt移动一次，每步的方向和大小完全随机，每步之间互不相关，则第n步的位移x(n)可以视为第n-1步的位移x(n-1)再加上一个白噪声函数ε(n)，可得随机游走样本轨道模型

x(n)= x(n-1)+ ε(n) （1）

设x(0)=0，有

当n趋于无穷大时，Δt变为无穷小量，式（2）的离散模型可变换为连续模型

由式（1）的样本轨道模型，可得随机变量模型

式中εi为iid独立同分布随机变量。设εi服从（0，σ2）正态分布，有

E[X(n)]=0 （5）

D[X(n)]= nσ2 （6）

表明随机游走过程的随机变量X(n)在状态空间服从（0，nσ2）正态分布。由于方差nσ2代表所有样本轨道x(n)在状态空间偏离原点的程度，因此对于单个的样本轨道来说，x(n)距原点的距离会越来越远，表示醉汉或质点不断远离原点。

假设Polya的随机游走定理正确，则从原点出发的所有醉汉或质点最终都返回到原点，此时的D[X(n)]= 0，与式（6）的D[X(n)]= nσ2相矛盾，因此随机游走定理的结论不成立。

时间自相关函数

假设白噪声过程样本函数ε(t)服从（0，σ2）正态分布，则ε(t)的时间自相关函数为

Rε(τ)=σ2δ(t) （7）

式中δ(t)为单位冲击函数。

由式（3），可计算出x(t)的时间自相关函数

式中为时间间隔。

功率谱密度

在[0，t]区间，样本函数的x(t)的平均功率有限，其自相关函数Rx()绝对可积，根据维纳-辛钦定理，x(t)的功率谱密度Sx(ω)是其自相关函数Rx()的傅立叶变换，有

式中，Sinc(ωt)为辛格函数。

ω=0时，Sinc(0)=1，因此有

Sx(0)=σ2t2 （10）

表明x(t)中存在一条与时间t成正比的线性趋势线。

当时间t充分大时，Sinc(ωt)的能量向Sinc(0)集中，因此x(t)在时域中就表现为

即样本轨道x(t)距原点的距离与时间成正比，样本轨道x(t) 是一族从原点发出的射线，醉汉或质点离原点越来越远，与物理学扩散现象相符。

图1为白噪声εi服从（0，1）正态分布时的10条随机游走样本轨道在n=1000步时的仿真曲线。从图中可以看出，从原点出发的质点位移相对原点呈发散状态，所有样本轨道x(n)在n时刻的取值服从（0，n）正态分布，每条样本轨道中均存在一条与时间成正比的线性趋势线，表明从原点出发的质点或醉汉离原点越来越远。

图1 随机游走样本轨道

Fig. 1 Sample paths of Random Walk

结论

本文首先指出了Pearson的随机游走问题是求解随机过程样本轨道位移特性问题，同时指出了随机游走常返性悖论和Polya使用概率分析方法在随机过程状态空间求解样本轨道位移特性的方法错误。本文使用函数分析方法在频域求解随机游走样本轨道的位移特性，得出了一维随机游走随时间不断远离原点的结论，从而推翻了Polya一维随机游走最终一定会返回原点的错误结论。

[参考文献] (References)

[1] Karl Pearson. The Problem of the Random Walk[J]. Nature,1905, 72（1865）:294.
[2] Clifford A.Pickover. 数学之书：数学史上250个里程碑式的发现[M]. 陈以礼. 重庆：重庆大学出版社，2015.
[3] 王国胜、王震. 谈谈简单随机游动[J]. 德州师专学报, 1998, 14（2）:9-12.
[4] Jonathan Novak. Polya的随机游走定理[J]. 数学译林，2016，35（3）:281-285.
[5] 高宏. 非平稳随机过程样本轨道研究方法错误及纠正[EB/OL]. 北京：中国科技论文在线 [2020-01-23].

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