一維隨機遊走的常返性證明

作者：由一口鳥發表于收藏時間：2022-08-30

最近對隨機遊走的相關問題比較感興趣。隨機遊走的常返性質是一個較為經典的問題，眾所周知，維度小於等於 2 時常返，大於 2 時非常返。對於一維情形，嚴格來說，只有當左右移動機率對稱時，常返性才得以滿足。本文對一維隨機遊走的常返性進行證明，作為一個沒有系統學習過隨機過程相關課程的非數學科班出身的學生，我用組合數學的相關思路給出證明過程。

先給出問題的形式化定義：

考慮在一維空間

$\mathbb{Z}$

上的隨機遊走

$X = \{X_n\}_{n \geq 0}$

。一個粒子在

時刻從狀態

出發，即

。每次移動時，以

的機率向右移動一個單位，以

的機率向左移動一個單位。請證明狀態

是常返的充要條件是

，即

$\sum_{n=1}^{\infty} \mathbb{P}(X_n = 0, X_k \neq 0, k = 1, ..., n - 1 | X_0 = 0) = 1 \Leftrightarrow p = q = 1/2$

我們將向右移動記為

，向左移動記為

。前

步中，我們根據每一時刻的隨機移動方向，得到一個動作序列。該動作序列由

和

組成，記為

$\{a_{2n} | a_k = \pm 1, k = 1, ..., 2n\}$

。例如，若前 4 步的隨機移動方向分別為 “右左左右”，則對應的動作序列為

$\{+1, -1, -1, +1\}$

。

定義出了動作序列，我們需要挖掘一下動作序列中存在的限制條件。我們首先考慮只在正半軸遊走的情形，負半軸的情形與正半軸完全對稱：

（1）第

步時需要回到原點，這意味著，前

步中向左和向右移動的次數相等，均為

次。換作動作序列的形式化表述，即

$a_1 + a_2 + \dotsb + a_{2n} = 0$

；

（2）第

步時，是第一次回到原點，這意味著在第

步之前，向右移動的次數總是多於向左移動的次數（這個結論可以模擬出棧入棧的思路）。因此，形式化表述為，對於任意正整數

，均有

$a_1 + a_2 + \dots + a_k > 0$

恆成立。

這個約束條件的形式十分類似於著名的 Catalan 數。Catalan 數的一個重要的形式化定義如下［1］：

考慮由

個

和

個

構成的

序列

$\{a_1, a_2, \dots, a_{2n}\}$

，其部分和總滿足

$a_1 + a_2 + ... + a_k \geq 0$

，則序列的個數等於第

個 Catalan 數

$C_n = \frac{1}{n+1} C_{2n}^n (n \geq 0)$

。

與 Catalan 數的性質唯一不同的是，我們給出的動作序列要求部分和嚴格大於 0，而 Catalan 數給出的序列允許部分和等於 0。事實上，根據條件我們不難得出，

，

$a_{2n} = -1$

。這時，限制條件（2）可以轉化為

$a_2 + a_3 + \dots + a_{k} \geq 0 \quad k = 2, 3, ..., 2n-1$

成功地將問題化歸為 Catalan 數的形式。滿足該條件的序列個數即為第

個 Catalan 數

$\frac{1}{n} C_{2(n-1)}^{n-1} = \frac{1}{2} \cdot \frac{1}{2n-1} C_{2n}^n$

。考慮正負半軸的對稱性，滿足

在第

步時首次回到原點

的遊走序列數為

$\frac{1}{2n-1} C_{2n}^n$

。再乘以遊走的機率

，最終的機率計算為

$\mathbb{P}(X_{2n} = 0, X_k \neq 0, k = 1, ..., 2n - 1 | X_0 = 0) = \frac{1}{2n-1} C_{2n}^n (pq)^n$

接下來只需要證明

$\sum_{n=1}^{\infty} \frac{1}{2n-1} C_{2n}^n (pq)^n = 1 \Leftrightarrow p = q = 1/2$

考慮

和函式

$\begin{aligned} S(x) &= \sum_{n=1}^{\infty} \frac{1}{2n-1} C_{2n}^n x^n \\\\ &= \sum_{n=1}^{\infty} \frac{1}{2n-1} \cdot \frac{1}{n!} \cdot \frac{(2n)!}{n!} x^n \\\\ &= \sum_{n=1}^{\infty} \frac{1}{n!} \cdot \frac{1}{2n-1} \cdot \frac{2n \cdot (2n-1) \cdot (2n-2)!}{n \cdot (n-1)!}\\\\ &= \sum_{n=1}^{\infty} \frac{2}{n!} \cdot \frac{(2n-2)!}{(n-1)!} x^n \\\\ \end{aligned}$