随机游走模型

【概述】

1905 年，统计学家卡尔·皮尔逊公开求解随机游走问题（Random Walk Problem）：如果一个醉汉走路时每步的方向和大小完全随机，经过一段时间之后，在什么地方找到他的可能性最大？

1921年，匈牙利数学家 Polya 在研究随机游走问题后，证明了一维或二维随机游走具有常返性的随机游走定理，并得出了随机游走的醉汉最终会返回原点的结论。日本数学家角谷静夫将 Polya 随机游走定理表述为：喝醉的酒鬼总能找到回家的路，因此，随机游走定理也被称为酒鬼回家定理

2012年，Polya 的随机游走定理被《数学之书》列入数学发展史上最重要的250个里程碑式事件之一，其是这样用现代语言描述随机游走问题的：想象一只机器甲虫在一条无限长的水管中随机地向前或向后移动一步，问它最终回到原点的概率是多少？Polya 证明：如果不限制机器甲虫在一维空间内随机游走的步数，则机器甲虫最终回到原点的概率等于 $1$​

在随机过程中，随机游走（Random Walk，RW）模型，能用来表示不规则的变动形式，液体中悬浮微粒的布朗运动、空气中的烟雾扩散、股票市场的价格波动等动态随机现象均可用随机游走模型进行描述

【定义】

每过一个单位时间，游走者从数轴位置 $S_0$ 出发以固定概率随机向左或向右移动一个单位，记 $n$ 时刻游走者的位置为 $S_n$​，则一维随机游走被定义为：

$$S_n=S_0+X_1+X_2+\cdots +X_n$$

当 $S_0=0$ 时，称为从原点出发的一维简单随机游走

其中，$X_1,X_2,\cdots ,X_n$ 是独立同分布的随机变量，满足：

$$P(X_i=1)=1-P(X_i=-1)=p$$

一维随机游走也可以看作一阶马尔可夫链，其状态空间为 $i=0,\pm 1,\pm 2,\cdots$，对于概率 $0<p<1$，转移概率由下式给出

$$p_{i,i+1}^{(1)}(n)=1-p_{i,i-1}^{(1)}(n)=p$$