# Bước ngẫu nhiên một chiều: Nghịch lý của sự quay về chắc chắn Trong bài viết trước về [Ngụy biện con bạc]({{< ref "/posts/math/stats/gamblers-fallacy.md" >}}), 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). **Định nghĩa 1 (Bước ngẫu nhiên một chiều).** Cho $\{X_n\}_{n \ge 1}$ là một dãy các biến ngẫu nhiên độc lập và cùng phân phối, nhận giá trị trong tập $\{-1, 1\}$ với xác suất: $$ P(X_n = 1) = P(X_n = -1) = \frac{1}{2} \quad \forall n \ge 1. $$ Vị trí của hạt tại bước thứ $n$, ký hiệu là $S_n$, được xác định bởi: $$ 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). **Bổ đề 1 (Xác suất tại gốc).** Với mọi số nguyên $n \ge 1$, xác suất để hạt ở tại gốc tọa độ ở bước thứ $2n$ là: $$ 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. **Bổ đề 2 (Xấp xỉ tiệm cận).** Khi $n \to \infty$, ta có sự tiệm cận: $$ P(S_{2n} = 0) \sim \frac{1}{\sqrt{\pi n}}. $$ *Chứng minh.* Theo công thức Stirling, $n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$. Thay vào $\binom{2n}{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}}. $$ Thay kết quả này vào Bổ đề 1, ta có: $$ 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$. **Định lý 1 (Pólya, 1921 - Bản một chiều).** Bước ngẫu nhiên đối xứng một chiều là một chuỗi hồi quy. Tức là, xác suất hạt quay về gốc tọa độ bằng 1: $$ f = P\left(\bigcup_{n=1}^\infty \{S_n = 0\}\right) = 1. $$ *Chứng minh.* Gọi $V$ là tổng số lần hạt viếng thăm gốc tọa độ trong suốt vô hạn bước (không tính thời điểm ban đầu $n=0$). Ta có thể viết $V$ dưới dạng tổng các hàm chỉ thị (indicator variables): $$ V = \sum_{k=1}^\infty \mathbf{1}_{\{S_k = 0\}}. $$ Kỳ vọng số lần viếng thăm là: $$ 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). $$ Theo Bổ đề 2, $P(S_{2n} = 0) \sim \frac{1}{\sqrt{\pi n}}$. Chuỗi $\sum \frac{1}{\sqrt{n}}$ là chuỗi $p$-series với $p=1/2 < 1$, do đó nó **phân kỳ**. Suy ra: $$ E[V] = \infty. $$ Mặt khác, ta tính $E[V]$ thông qua xác suất $f$. Xác suất để hạt quay về gốc đúng $k$ lần là xác suất nó quay về $k$ lần liên tiếp và sau đó không bao giờ quay về nữa: $$ P(V = k) = f^k (1 - f). $$ Suy ra $V$ tuân theo phân phối hình học. Kỳ vọng của $V$ tính theo $f$ là: $$ 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)**. **Định nghĩa 2 (Thời điểm chạm gốc đầu tiên).** Gọi $T$ là số bước tối thiểu (lớn hơn 0) để bước ngẫu nhiên quay về gốc: $$ T = \inf \{ n \ge 1 : S_n = 0 \}. $$ **Định lý 2 (Thời gian chờ vô hạn).** Dù xác suất quay về gốc là $1$ ($P(T < \infty) = 1$), kỳ vọng của thời gian chờ lại bằng vô cực: $$ E[T] = \infty. $$ *Chứng minh.* Ta sử dụng kết quả kinh điển từ nguyên lý phản xạ (Reflection Principle) hoặc hàm sinh, kết quả cho biết quan hệ giữa xác suất quay về lần đầu $P(T = 2n)$ và xác suất ở tại gốc $P(S_{2n} = 0)$: $$ P(T = 2n) = \frac{1}{2n - 1} P(S_{2n} = 0) = \frac{1}{2n - 1} \binom{2n}{n} \frac{1}{2^{2n}}. $$ Sử dụng xấp xỉ Stirling (Bổ đề 2) $P(S_{2n} = 0) \sim \frac{1}{\sqrt{\pi n}}$, ta thu được xấp xỉ tiệm cận cho phân phối của thời gian dừng: $$ P(T = 2n) \sim \frac{1}{2n} \cdot \frac{1}{\sqrt{\pi n}} = \frac{1}{2\sqrt{\pi} n^{3/2}}. $$ Bây giờ, ta tính kỳ vọng của $T$: $$ E[T] = \sum_{n=1}^\infty 2n P(T = 2n). $$ Khi xét phần đuôi của chuỗi (với $n$ lớn), các số hạng tiệm cận với: $$ 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). 1. **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. 2. **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.