前言

本文章简要介绍一些常见的随机过程

随机游走（Random Walk）

定义

随机游走是一个离散时间的随机过程，
::: align-center
S_n=S_0+X_1+X_2+\cdots+X_n
:::
其中：

• S_0是初始位置
• X_i是一系列独立同分布（iid）的随机变量，代表每一步的增量
• S_n代表最终的位置

在这其中，最为简单的是一维简单随机游走，它的状态空间为\pm1（前进/后退），索引集为1,2,\cdots,n，即
::: align-center
X_i=\left\{ \begin{matrix}+1 & p\\ -1 & 1-q\end{matrix}\right .
:::
其中p+q=1，若p=q=0.5则称为对称随机游走

一维简单随机游走的期望和方差

期望：
::: align-center
E(S_n)=E(\sum_{i=1}^n X_i)=\sum_{i=1}^n E(X_i)=n(p-q)
:::
方差：
::: align-center
\begin{aligned}&Var(S_n)=Var(\sum_{i=1}^n X_i)=nVar(X_i)\\ &=n[1-(p-q)^2]\\ &=4npq\end{aligned}
:::
标准差正比于\sqrt{n}，所以扩散范围按\sqrt{n}增长

一维简单随机游走的生成函数

计算S_n的PGF：
::: align-center
\begin{aligned}&G_{S_n}(s)=E(S^{S_n})=E(S^{\sum_{i=1}^n X_i})=\prod_{i=1}^n E(S^{X_i})=E^n(S^{X_i})\end{aligned}
:::
而
::: align-center
E(S^{X_i})=(ps+\frac{q}{s})
:::
故G_{S_n}(s)=(ps+\frac{q}{s})^n，利用PGF求导可以得到
::: align-center
E(S_n)=G'_{S_n}(1)=n(p-q)
:::
和
::: align-center
E(S_n(S_n-1))=E(S_n^2)-E(S_n)=G''_{S_n}(1)=n(n-1)(p-q)^2+2qn
:::
也可以得出Var(S_n)=4npq

一维随机游走的概率质量函数

在求得PGF后，我们还可以求出一维随机游走的PMF：
::: align-center
(ps+\frac{q}{s})^n=\sum_{k=0}^\infty\binom{n}{k}(ps)^{k}(\frac{q}{s})^{n-k}=\sum_{k=0}^\infty\binom{n}{k}p^kq^{n-k}s^{2k-n}
:::
则PMF，即P(S_n=m)即为s^m项的系数。令2k-n=m得到k=\frac{n+m}{2}
则PMF求得为P(S_n=m)=\binom{n}{\frac{n+m}{2}}p^{\frac{n+m}{2}}q^{\frac{n-m}{2}}
或者又由\binom{n}{k}=\binom{n}{n-k}可以得到为\binom{n}{\frac{n-m}{2}}p^{\frac{n+m}{2}}q^{\frac{n-m}{2}}
从这可以看出限制：n与m必须同奇偶，否则PMF应该取值0

是否会返回？

若我们想要研究一个一个简单一维随机游走是否会返回，设\mathcal{R}为“从原点出发，最终至少回到原点一次”的概率，记P_0^{(n)}为第n步恰好回到原点的概率（此处n必须为偶数，详情见上），N为随机游走总共回到原点的次数

首先我们研究N的期望，即E(N)，定义指示变量I_n=\left\{\begin{matrix}1 & S_n=0\\ 0 & \text{否则}\end{matrix} \right .
则有N=\sum_{i=1}^\infty I_n，取期望得到引理一
::: align-center
E(N)=E(\sum_{i=1}^\infty I_n)=\sum_{i=1}^\infty E(I_n)=\sum_{i=1}^\infty P(S_n=0)=\sum_{i=1}^\infty P^{(n)}_0
:::

接下来研究E(N)和\mathcal{R}的关系，因为随机游走中每一次回到原点后，后续的轨迹和从原点全新的出发是完全同分布的（也就是强马尔可夫性），故考虑N这个随机变量每个取值的概率

• N=0（即从不返回）：1-\mathcal{R}
• N=1（只返回一次）：\mathcal{R(1-R)}
• N=2（只返回两次）：\mathcal{R^2(1-R)}
• ...
• N=n（只返回n次）：\mathcal{R^n(1-R)}

即N符合几何分布，由几何分布的期望公式\frac{\text{成功概率}}{\text{失败（停止）概率}}可直接得到E(N)=\frac{\mathcal{R}}{\mathcal{1-R}}(\mathcal{R}<1)，或者直接求解级数和函数：
::: align-center
E(N)=\sum_{n=1}^\infty n\mathcal{R^n(1-R)}
:::
得到收敛半径\mathcal{R}<1，和函数\frac{\mathcal{R}}{\mathcal{1-R}}，作为引理2

在建立了P^{(n)}_0与E(N)，E(N)和\mathcal{R}的联系后，我们便可以通过研究P^{(n)}_0来研究E(N)和\mathcal{R}了

而
::: align-center
P_0^{(n)}=P(S_n=0)=\left\{\begin{matrix}\binom{n}{n/2}p^{n/2}q^{n/2} & n偶\\0 & n奇\end{matrix} \right.
:::
此时我们便可以计算E(N)，去除n为奇数时的0项，只考虑为偶数时的期望，令n=2k，得到：
::: align-center
E(N)=\sum_{k=1}^\infty\binom{n}{k}p^kq^k=\sum_{k=1}^\infty\frac{(2k)!}{(k!)^2}(pq)^k
:::
而有