随机行走在随机过程中是一个很简单而又很经典的例子, 以一维随机行走为例, 每一时刻都按照概率\(p\)向右走一格, 按照概率\(1-p\)向左走一格. 我们记\(S_n\)为第\(n\)步走到的位置, 那么 $$S_n= \begin{cases} S_{n-1}+1& \text{rand < p}\\
S_{n-1}-1& \text{others} \end{cases}$$

一般我们设置\( p = 1 / 2\)为对称的随机行走. 这个模型我们会考虑行走的位置\(S_n\)的期望与时间\(n\)的关系, 以及\(S_n^{2}, |S_n|\)与时间\(n\)的关系, 还有考虑该模型的常返性, 以及在解微分方程上的应用.

一些期望的计算

首先可以很容易看出, \(S_n\)的期望值是等于零的.

$$ E(S_n) = E(\sum_{k=1}^{n} a_k) = \sum_{k=1}^{n}E(a_k) = 0 $$

对于$S_n^{2}$的期望, 我们有:

\begin{align*} E(S_n^{2}) &= E\left(\left(\sum_{k=1}^{n} a_k\right)^2 \right) \newline & = E\left(\sum_{k=1}^{n} a_k^2\right) + 2\sum_{i=1}^{n}\sum_{j>i}^{n}\ E(a_i a_j)\newline &= E\left(\sum_{k=1}^{n} a_k^2\right) = \sum_{k=1}^{n}E(a_k) = n \end{align*}

所以可以看到随机行走的扩散的范围的期望是与行走的步数的平方根成正比的, 那么我们可以计算一下$|S_n|$的期望.

首先不妨我们假设$n = 2m$, 那么$S_n$的取值即为$-2m,2m+2,…,2m$, 我们可以计算出$S_n$取各个值的概率, 例如$S_n = 2k$即为向右行走的步数比向左走的步数要多$2k$, 那么可以得到向右走的步数为$S_{right} = m+k$, 向左走的步数为$S_{left} = m-k$, 因此我们只需要从$2m$的步数中选取$m+k$为$+1$即可.所以概率为

$$ P\left( S_n = 2k \right) = \frac{C_{2m}^{m+k}}{2^{2m}} = \frac{(2m)!}{2^{2m}(m+k)!(m-k)!}$$

实际上这样就可以求出$|S_n|$的期望了, 但是并不是一个解析的形式, 但是我们可以求出$n\rightarrow\infty$的极限值.. 利用stirling-approximation, $n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$就可以进行近似计算.

因此上述的概率可以简化为:

$$ P\left( S_n = 2k \right) = \sqrt{\frac{2m}{2\pi(m^2-k^2)}}\frac{m^{2m}}{(m+k)^{m+k}(m-k)^{m-k}}$$

下面为了方便我们取对数:

\begin{align*} \ln P &= - (m-k) \ln(1-\frac{k}{m}) - (m+k) \ln(1+\frac{k}{m})+\frac{1}{2} \ln \frac{ 2m }{ 2\pi(m^2-k^2) } \newline & = - \frac{k^2}{m}+\frac{1}{2} \ln \frac{ 2m }{ 2\pi(m^2-k^2) } \end{align*}

所以我们可以得到:

$$P(m, k) =\sqrt{\frac{1}{\pi m}} e^{-\frac{-k^2}{m}}$$

我们把上述的概率换算成一般的概率分布形式为:

$$P(x) = \sqrt{\frac{ 1 }{\pi n}} e^{-\frac{x^2}{n}}$$

因此我们可以计算 $$\lim_{n\rightarrow\infty} E(|S_n|) = \int |x|P dx = \sqrt{\frac{2n}{\pi}}$$

附上模拟的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import matplotlib.pyplot as plt

nstep = 100

def get_final_pos(nstep):
    return np.sum(np.sign(np.random.rand(1,nstep) - 0.5))

def norm_prob(nstep, x):
    return np.sqrt(1/(nstep*np.pi))*np.exp(-x**2/nstep)
def main():
    return [get_final_pos(nstep) for ii in range(100000)]


if __name__ == '__main__':
    res = main()
    x = range(-50,51)
    y = [norm_prob(nstep, i) for i in x]
    plt.hist(res,normed=1)
    plt.plot(x,y)
    plt.show()

可以看到分布是服从正态分布的.

随机行走中的一些概率计算

常返性

在随机过程里面有这样一个段子, 喝醉酒的人总可以找到回家的路然而喝醉酒的小鸟却不一定可以找回回家的路. 实际上就是二维随机行走当行走的步数趋于无穷大的时候总是可以回到原点, 然而三维的随机行走却不一定可以回到原点. 这里我们以一维随机行走为例, 说明常返性的由来.

首先我们用数学的语言描述什么是常返性, 也即为:

$$\lim_{n\rightarrow \infty} P(S_0 \neq 0 ,S_2 \neq 0,…,S_{2n} \neq 0) = 0$$

实际上我们只需要证明上式成立即可. 这里我们不妨考虑其反面, 先求出刚好$2m$次回到原点的概率, 这也就意味着, $2m$次之前一定没有到达原点.

引理

假设A, B两人竞选某个职位, 现在已知A的得票为$m$, B的得票为$n$, 其中$m>n$, 假定唱票的顺序是完全随机的, 那么在此过程中, A的票数一直领先于B的概率是多少?

这里可以使用递推的方式来解决, 最后一票可能是A, 也有可能是B, 那么所求的概率$P_n^m$即可以表达为:

$$P_n^m = \frac{n}{m+n} P_{n-1}^m + \frac{m}{m+n}P_{n}^{m-1}$$

很明显:

$P_1^{0} = 1, P_2^1 = \frac{1}{3}, P_3^1 = \frac{2}{4}, P_3^2 = \frac{1}{5} $ 可以看出$P_n^m = \frac{n-m}{n+m}$. 带入验证也是正确的. 下面就借助这个结果可以证明随机行走的常返性这一结论.

由于我们假定刚好$2m$次回到原点, 也就说明前$2m-1$次中有$m$次向右, $m-1$次向左(不妨这样假设), 也就说明这$2m-1$次中向右的次数一直多于向左的次数, 其概率为$\frac{2}{2m-1}$, 分子为2是因为这里不知道是向左的次数多于还是少于向右的, 等概率的所以应该乘以2, 接着最后一步有$\frac{1}{2}$的概率向左或者向右, 所以在已知$m$次向左和向右的情况下, 最后一步刚好回到原点的概率为$\frac{1}{2m-1}$.

所以我们可以得出, $2m$次行走刚刚好到达原点的概率为:

$$P(S_0 \neq 0, S_2 \neq 0, …, S_{2m} = 0) = \frac{1}{2m-1}\frac{C_{2m}^{m}}{2^{2m}}$$ 为了方便我们可以记上式为$Q_m = \frac{1}{2m-1}\frac{C_{2m}^{m}}{2^{2m}}$

那么最终我们只需要证明

$$1 - \sum_{m=1}^{\infty}Q_m = 0$$

下面可以证明这一结果. 实际上有这样一个神奇的结果:

$$1 - \sum_{m=1}^{n}Q_m = \frac{C_{2n}^{n}}{2^{2n}} $$

下面我们可以来证明这一点.

首先 $n = 1$的时候是成立的, 假设$n = k$的时候也成立, 现在$n = k+1$, 那么只需要证明

\begin{align*} \frac{C_{2k+2}^{k+1}}{(2k+1)2^{2k+2}} = \frac{C_{2k}^{k}}{2^{2k}} - \frac{C_{2k+2}^{k+1}}{2^{2k+2}} \end{align*}

这是很容易验证的.所以我们可以得到, 前$2n$次都没有回到原点的概率为:

\begin{align*} P & = \frac{C_{2n}^{n}}{2^{2n}} \sim \frac{1}{\sqrt{n\pi}} \end{align*}

所以当$n\rightarrow \infty$的时候, 回到原点的概率为1.

下面即为模拟一维随机行走常返性的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
import matplotlib.pyplot as plt

def return_origin(nstep):
    s = 0
    for ii in range(nstep):
        if np.random.rand() > 0.5:
            s += 1
        else:
            s -= 1
        if s == 0:
            return True
    return False

if __name__ == '__main__':
    final_res = [[1 if return_origin(ii) else 0 for idx in range(10000)] for ii in range(10,1000)]
    final_res = np.array(final_res)
    res = np.sum(final_res,axis=1)
    plt.plot(range(10,1000),res)
下图是返回的次数与行走的步数的关系, 可以看到是符合根号$n$的关系的.