一、定义

一个醉汉在一条笔直的公路随机游走，每一步都以 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} $$

■