一维离散随机游走常返性
一个随机过程 $X = \left(X_n\right)_{n \in \mathbb N}$，$X_0 = 0$，$X_{n + 1}$ 在 $X_n$ 基础上等概率随机加 $1$ 或减 $1$。$X$ 是马尔可夫（Markov）链，分析原点的常返性（瞬时 / 常返 / 正常返 / 零常返）。
假设 $n$ 是正整数，$X_n = 0$ 的概率
$$\Pr\left[X_n = 0\right] = 2^{-2n}\binom{2n}n = 2^{-2n}\frac{\left(2n\right)!}{n!n!}$$
由 Stirling 公式可知
$$\Pr\left[X_n = 0\right] = \frac{\left(2n\right)!}{n!n!} \sim \frac1{\sqrt{\pi n}}$$
所以
$$\sum\limits_{n \geq 1}\Pr\left[X_n = 0\right] = \infty$$
且
$$\lim\limits_{n \to \infty}\frac1{\sqrt{\pi n}} = 0$$
因此原点零常返（null recurrent）。
二维离散随机游走常返性
一个随机过程 $X = \left(X_n\right)_{n \in \mathbb N}$，$X_0 = 0$，$X_{n + 1}$ 在 $X_n$ 基础上等概率随机加上 $\left\{1, -1, i, -i\right\}$ 中的一个。$X$ 是马尔可夫（Markov）链，分析原点的常返性（瞬时 / 常返 / 正常返 / 零常返）。
假设 $n$ 是正整数，$X_n = 0$ 的概率
$$ \begin{aligned} \Pr\left[X_n = 0\right] &= 4^{-2n}\sum\limits_{0 \leq m \leq n}\binom{2n}m\binom{2n - m}m\binom{2n - 2m}{n - m}\\ &= 4^{-2n}\sum\limits_{0 \leq m \leq n}\frac{\left(2n\right)!}{\left(m!\left(n - m\right)!\right)^2}\\ &= 4^{-2n}\frac{\left(2n\right)!}{n!n!}\sum\limits_{0 \leq m \leq n}\left(\frac{n!}{m!\left(n - m\right)!}\right)^2\\ &= 4^{-2n}\frac{\left(2n\right)!}{n!n!}\sum\limits_{0 \leq m \leq n}\binom nm\binom n{n - m} \end{aligned} $$
考虑 $\sum\limits_{0 \leq m \leq n}\binom nm\binom n{n - m}$ 的组合意义为 求 $2n$ 个东西里面选 $n$ 个的方案数，可以看作枚举前 $n$ 个东西里面选出 $m$ 个，然后在后面 $n$ 个东西里面选出 $n - m$ 个。因此
$$4^{-2n}\frac{\left(2n\right)!}{n!n!}\sum\limits_{0 \leq m \leq n}\binom nm\binom n{n - m} = 4^{-2n}\left(\frac{\left(2n\right)!}{n!n!}\right)^2$$
由 Stirling 公式，可得
$$\Pr\left[X_n = 0\right] = 4^{-2n}\left(\frac{\left(2n\right)!}{n!n!}\right)^2 \sim \frac1{\pi n}$$
所以
$$\sum\limits_{n \geq 1}\Pr\left[X_n = 0\right] = \infty$$
且
$$\lim\limits_{n \to \infty}\frac1{\pi n} = 0$$
因此原点零常返。
高维离散随机游走常返性
观察规律可知，在 $k$ 维的离散随机游走中：
$$\Pr\left[X_n = 0\right] \sim \frac1{\left(\pi n\right)^{\frac k2}}$$
当 $k \geq 3$ 时，任意状态瞬时。
参考
http://home.ustc.edu.cn/~fa1247/Stochastic%20Process.pdf
https://box.nju.edu.cn/d/feb7035e412948b5b909/files/?p=%2F%E5%B0%B9%E4%B8%80%E9%80%9A.pdf
https://blog.csdn.net/qq_41741344/article/details/122508195