随机游走问题

随机游走问题

一维有边界的随机游走问题

设初始位置位 x = n, 边界为 x = 0 和 x = w，其中 \(0 \leq n \leq w\)，\(n, w\) 为整数。游走者每个单位时间移动一次，向左、向右移动的概率都为 \(\frac{1}{2}\)，达到边界后停止移动。

若用 \(S_{n}\) 表示初始位置为 x = n 时最终落入边界 x = 0 的概率。显然我们会有 \(S_0 = 1\) 和 \(S_w = 0\) ，即初始位置为边界的情况

若 \(0 < n < w\) ，则考虑其下一次移动，有 \(\frac{1}{2}\) 的概率向左到达 \(n - 1\) ，有 \(\frac{1}{2}\) 的概率向右到达 \(n + 1\)

则由全概率公式可以得到：\(S_n = \frac{1}{2} S_{n - 1} + \frac{1}{2} S_{n+1}\)

整理得到：\(S_{n + 1} = 2S_n - S_{n - 1}\)

所以：\(S_{n+1} - S_n = S_n - S_{n-1} = S_1- S_0 = k\)

累加法可以得到：\(S_n = kn + S_0\)

再由 \(S_0 = 1, S_w = 0\) ，可以得到：

\(S_n = 1 - \frac{n}{w} = \frac{w - n}{w}\)

对于单边界情况，可以令 \(w \to +\infty\) ，即得到 \(S_n = 1\)

二维随机游走

二维随机游走 m 步到达点 (x,y) 的概率为 \(P_m(x, y)\)

其中有两个隐藏条件：

1. \(|x| + |y| \leq m\)，即 m 步可以到达点 \((x, y)\)
2. \(|x| + |y|\) 与 m 的奇偶性一致

假设一个 m 步的随机游走到达了点 \((x, y)\)

因为随机游走概率的结果与空间的方向没有关系，只与相对位置有关，不妨定义方向如下：

• 令向量 \(\begin{pmatrix}\dfrac{x}{|x|} \\0\end{pmatrix}\) 为 x 的顺方向，记为 \(e_1\)
• 令向量 \(\begin{pmatrix} -\dfrac{x}{|x|} \\ 0\end{pmatrix}\) 为 x 的逆方向，记为 \(e_1^{'}\)
• 同理记 \(\begin{pmatrix} 0 \\ \dfrac{y}{|y|}\end{pmatrix}\) \(= e_2, \begin{pmatrix} 0 \\ - \dfrac{y}{|y|}\end{pmatrix} = e_2^{'}\)

那么这个随机游走的结果可以表述为：

\(\begin{pmatrix} x \\ y\end{pmatrix} = Ae_1 + Be_1^{'} + Ce_2 + De_2^{'}\) ，其中，\(A, B, C, D\) 都是对应方向上的步数，而且 \(A + B + C + D = m\)，于是 \(m\) 步到达 \((x, y)\) 的路径总数是 \(C_m^AC_{m - A}^{B}C_{m-A-B}^{C}C_{m - A - B - C}^{D} = \dfrac{m!}{A!B!C!D!}\)

对参数进行整理。因为顺方向上步数 A 或者 C 必然不小于绝对位移量，不妨设 \(A = |x| + j\) ，将 A 代入可得 \(B = j\)，同理设 \(C = |y| + i, D = i\)。

可以得到：\(|x| + |y|+ 2(i + j) = m\)

所以：\(j + i = \dfrac{m - (|x| + |y|)}{2} = k\)

由于 \(j, i \geq 0\)，于是 j 的取值是 \(j = 0,...,k\) 。现在就已经将 \(A, B,C,D\) 四个参数统一为一个参数 \(j\)，由此四个方向的步数可以由已知变量 \((m, x, y)\) 和一个参数 j 表示：

\(\begin{pmatrix} A \\ B \\ C\\ D\end{pmatrix} = \begin{pmatrix} |x| + j \\ j \\ |y| + k - j \\ k - j\end{pmatrix}\)

将上式带入概率表达式，将 j 遍历其取值并求和即得结果：

\(P(m, x,y) = \frac{1}{4^{m}} \sum\limits_{j = 0}^{k} \dfrac{m!}{(|x|+j)!(j!)(|y|+k - j)!(k-j)!}\)

其中，\(k = \dfrac{m - |x|-|y|}{2}\)