一维随机游走第n步时距原点的平均距离

一、定义

一个醉汉在一条笔直的公路随机游走，每一步都以 50% 的概率向前移动一步：\(+1\)，或向后移动一步：\(-1\)，即每一步都是一个独立的随机变量，记为 \(Z_{1},Z_{2},\dots\)。

设 \(S_{0}=0\)，\(S_{n}=\sum\limits_{j=1}^{n}Z_{j}\)，则级数 $ {S_{n}}$ 称为 \(\mathbb {Z}\) 上的简单随机游走。显然 \(-n\leqslant S_n \leqslant n\)。

在 \(n\) 步随机游走中，醉汉恰有 \(k\) 次向前移动的概率为 \(P_k:=P(\text{恰有}k\text{个}Z_i=1)=\dbinom{n}{k}\dfrac{1}{2^n}\)，此时 \(S_n=2k-n\)，所以一维随机游走中离原点的平均距离为：

\[ E(|S_n|)=\dfrac{1}{2^n}\sum_{k=0}^n\dbinom{n}{k}\left|2k-n\right| \]

二、求解

2.1 结果

在一维随机游走中，当游走到第 \(n=1,2,3,\cdots\) 步时，离原点的平均距离为：

\[ \color{blue}{ E(|S_n|)=\cases{ \dfrac{n}{2^n}\dbinom{n}{n/2}=E(|S_{n-1}|), & \text{if n is even}\\ \\ \dfrac{n+1}{2^{n+1}}\dbinom{n+1}{(n+1)/2}=E(|S_{n+1}|), & \text{if n is odd} } } \]

利用斯特林公式（Stirling’s formula，\(\lim_\limits{n\rightarrow\infty}\dfrac{n!}{\sqrt{2\pi n}(\frac{n}{e})^n}=1\)）有

\[ \lim_{n\rightarrow+\infty}\frac{E(|S_n|)}{\sqrt{n}}=\sqrt{\frac{2}{\pi}} \]

因此 \(\color{blue}{E(|S_n|)}\) 与 \(\color{blue}{\sqrt{\dfrac{2n}{\pi}}}\) 是等价无穷大量。

2.2 计算过程

当 \(n\) 为偶数里，记 \(n=2m\)，由对称性知

\[ E(|S_n|)=\dfrac{2}{2^n}\sum_{k=0}^{m}\dbinom{n}{k}(n-2k) \]

化简上式右边求和符号部分

\[ \begin{aligned} \sum_{k=0}^{m}\dbinom{n}{k}(n-2k)&=\sum_{k=0}^{m}\dbinom{n}{k}n-2\sum_{k=1}^{m}\dbinom{n}{k}k\\ &=\frac{n}{2}\left(2^n+\dbinom{n}{m}\right) - 2\sum_{k=1}^{m}n\dbinom{n-1}{k-1}&{\color{blue}(*)} \\ &=\frac{n}{2}\left(2^n+\dbinom{n}{m}\right) - \frac{2n}{2}2^{n-1} \\ &=n2^{n-1}+\frac{n}{2}\dbinom{n}{m} - \frac{2n}{2}2^{n-1} \\ &=\frac{n}{2}\dbinom{n}{m} \end{aligned} \]

所以

\[ E(|S_n|)=\frac{n}{2^n}\dbinom{n}{n/2} \]

在第 \({\color{blue}(*)}\) 步，用到了以下两个公式

\[ \begin{aligned} k\dbinom{n}{k}=n\dbinom{n-1}{k-1}\\ \sum_{k=0}^m\dbinom{2m}{k}=\dfrac{1}{2}\left[2^{2m}+\dbinom{2m}{m}\right] \end{aligned} \]

当 \(n\) 为奇数时，同理可以求得

\[ E(|S_n|)=\frac{n+1}{2^{n+1}}\dbinom{n+1}{(n+1)/2} \]

■