Bước ngẫu nhiên một chiều: Nghịch lý của sự quay về chắc chắn
(1D Random Walk & Pólya's Recurrence Theorem)
Trong bài viết trước về Ngụy biện con bạc, ta đã nhắc đến một kết quả phản trực giác của xác suất: nếu bạn chơi một trò chơi tung đồng xu công bằng, xác suất để bạn gỡ lại toàn bộ số vốn đã thua là 100%, nhưng kỳ vọng thời gian chờ để làm được điều đó lại bằng vô cực.
Đây không phải là một cách nói cường điệu. Nó là hệ quả trực tiếp từ lý thuyết Bước ngẫu nhiên (Random Walk). Bài viết này sẽ đi sâu vào thiết lập toán học chặt chẽ, phát biểu và chứng minh các định lý làm nền tảng cho nghịch lý này.
1. Thiết lập bài toán
Ta xét mô hình bước ngẫu nhiên đối xứng một chiều (Simple Symmetric 1D Random Walk).
$$ P(X_n = 1) = P(X_n = -1) = \frac{1}{2} \quad \forall n \ge 1. $$$$ S_n = \sum_{i=1}^n X_i, \quad S_0 = 0. $$Không gian trạng thái của chuỗi ${S_n}$ là tập các số nguyên $\mathbb{Z}$.
2. Số lần viếng thăm gốc tọa độ
Để chứng minh xác suất quay về gốc tọa độ bằng 1, ta cần khảo sát xác suất hạt ở tại gốc vào thời điểm $n$. Rõ ràng, hạt chỉ có thể quay về gốc sau một số chẵn các bước (số bước tiến bằng số bước lùi).
$$ P(S_{2n} = 0) = \binom{2n}{n} \frac{1}{2^{2n}}. $$Hơn nữa, $P(S_{2n-1} = 0) = 0$.
Chứng minh. Tại thời điểm $2n$, để $S_{2n} = 0$, hạt phải có đúng $n$ bước $+1$ và $n$ bước $-1$. Số cách chọn $n$ vị trí cho bước $+1$ trong tổng số $2n$ bước là $\binom{2n}{n}$. Mỗi chuỗi có xác suất xảy ra là $(1/2)^{2n}$. Nhân chúng lại ta được kết quả của Bổ đề. Với số bước lẻ, hiển nhiên $S_{2n-1} \neq 0$. $\blacksquare$
Để ước lượng xác suất này khi $n$ tiến tới vô cực, ta sử dụng Công thức xấp xỉ Stirling.
$$ P(S_{2n} = 0) \sim \frac{1}{\sqrt{\pi n}}. $$$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4\pi n} \left(\frac{2n}{e}\right)^{2n}}{\left( \sqrt{2\pi n} \left(\frac{n}{e}\right)^n \right)^2} = \frac{\sqrt{4\pi n} \cdot 2^{2n} \cdot n^{2n} \cdot e^{-2n}}{2\pi n \cdot n^{2n} \cdot e^{-2n}} = \frac{2^{2n}}{\sqrt{\pi n}}. $$$$ P(S_{2n} = 0) = \frac{1}{2^{2n}} \binom{2n}{n} \sim \frac{1}{\sqrt{\pi n}}. $$$\blacksquare$
Trực giác: Bổ đề 2 cho thấy xác suất quay về gốc tại một thời điểm cụ thể $2n$ có giảm đi, nhưng tốc độ giảm rất chậm (theo $1/\sqrt{n}$). Chính sự giảm chậm này là chìa khóa làm cho tổng số lần viếng thăm phân kỳ tiến tới vô cực.
3. Định lý Hồi quy Pólya (Pólya’s Recurrence Theorem)
Gọi $f$ là xác suất để bước ngẫu nhiên quay trở về gốc tọa độ ít nhất một lần. Chuỗi Markov được gọi là hồi quy (recurrent) nếu $f = 1$, và quá độ (transient) nếu $f < 1$.
$$ f = P\left(\bigcup_{n=1}^\infty \{S_n = 0\}\right) = 1. $$$$ V = \sum_{k=1}^\infty \mathbf{1}_{\{S_k = 0\}}. $$$$ E[V] = E\left[ \sum_{k=1}^\infty \mathbf{1}_{\{S_k = 0\}} \right] = \sum_{k=1}^\infty P(S_k = 0) = \sum_{n=1}^\infty P(S_{2n} = 0). $$$$ E[V] = \infty. $$$$ P(V = k) = f^k (1 - f). $$$$ E[V] = \sum_{k=1}^\infty k f^k (1 - f) = \frac{f}{1 - f}. $$Để $E[V] = \infty$, điều kiện bắt buộc là $f = 1$. $\blacksquare$
Trực giác: Định lý Pólya khẳng định rằng, trong không gian 1D (và cả 2D), bạn đi lạc bao xa không quan trọng, bạn chắc chắn 100% sẽ dẫm lại lên dấu chân xuất phát của mình. Nhà toán học Shizuo Kakutani từng đúc kết: “Một người say xỉn cuối cùng sẽ tìm được đường về nhà, nhưng một con chim say xỉn thì có thể mất hút trên bầu trời mãi mãi” (chỉ ra rằng bước ngẫu nhiên 3D là transient, $f \approx 0.34$).
4. Nghịch lý thời gian chờ vô cực
Định lý 1 bảo đảm rằng người chơi tung đồng xu chắc chắn sẽ có thời điểm huề vốn. Vậy tại sao các con bạc vẫn phá sản? Câu trả lời nằm ở thời gian chờ (waiting time).
$$ T = \inf \{ n \ge 1 : S_n = 0 \}. $$$$ E[T] = \infty. $$$$ P(T = 2n) = \frac{1}{2n - 1} P(S_{2n} = 0) = \frac{1}{2n - 1} \binom{2n}{n} \frac{1}{2^{2n}}. $$$$ P(T = 2n) \sim \frac{1}{2n} \cdot \frac{1}{\sqrt{\pi n}} = \frac{1}{2\sqrt{\pi} n^{3/2}}. $$$$ E[T] = \sum_{n=1}^\infty 2n P(T = 2n). $$$$ 2n \cdot P(T = 2n) \sim 2n \cdot \frac{1}{2\sqrt{\pi} n^{3/2}} = \frac{1}{\sqrt{\pi n}}. $$Do chuỗi $\sum \frac{1}{\sqrt{n}}$ là phân kỳ, suy ra tổng kỳ vọng $\sum 2n P(T=2n)$ cũng phân kỳ. Vậy $E[T] = \infty$. $\blacksquare$
5. Kết luận: Bài học từ toán học
Sự kết hợp giữa Định lý 1 và Định lý 2 tạo nên một trạng thái gọi là Null Recurrent (hồi quy không chắc chắn về mặt thời gian).
- Bạn chắc chắn sẽ hòa vốn ($f=1$): Toán học bảo vệ sự công bằng của quy luật xác suất.
- Nhưng bạn không thể đợi được ($E[T]=\infty$): Hệ thống yêu cầu bạn phải có một nguồn vốn vô hạn và một tuổi thọ vô hạn để chờ đợi.
Trong một quỹ đạo bước ngẫu nhiên, để triệt tiêu một độ lệch âm sâu thẳm, quá trình đó không làm tăng xác suất của mặt Ngửa ở các ván sau. Nó đơn giản là dựa vào độ giãn nở vô tận của trục thời gian, cho phép một chuỗi may mắn cực kỳ dị thường (như 1.000 mặt Ngửa liên tiếp) có cơ hội xảy ra để cân bằng lại. Đối với một đời người hữu hạn và túi tiền hữu hạn, sự chắc chắn $100%$ của toán học không thể cứu vãn được sự hữu hạn của thực tại.