Tổng quan chuyên đề: Tài liệu hướng dẫn phương pháp quy hoạch động (phân tích theo bước đầu tiên - First-step Analysis) để xử lý các mô hì...
Dạng 4. Xác suất hấp thụ – Bài toán người chơi phá sản
Ví dụ 10 (AMC 10B 2014, Bài 25 – cũng là AMC 12B 2014, Bài 22)
Trong ao có 11 lá súng xếp hàng, đánh số 0 đến 10. Một con ếch ngồi ở lá 1. Khi ở lá \(N\) (\(0 < N < 10\)), ếch nhảy sang lá \(N - 1\) với xác suất \(\frac{N}{10}\) và sang lá \(N + 1\) với xác suất \(1 - \frac{N}{10}\), các lần nhảy độc lập. Đến lá 0 ếch bị rắn ăn; đến lá 10 ếch thoát khỏi ao. Tính xác suất ếch thoát.
Trạng thái và hệ thức (phân tích theo bước đầu):
Gọi \(p_N\) là xác suất thoát khi đang ở lá \(N\):
\[p_N = \frac{N}{10} p_{N-1} + \left(1 - \frac{N}{10}\right) p_{N+1}, \quad p_0 = 0, \quad p_{10} = 1\]
Nhận xét đối xứng:
Lá \(N\) và lá \(10 - N\) đối xứng nhau nên \(p_N + p_{10-N} = 1\), đặc biệt \(p_5 = \frac{1}{2}\).
Giải bằng hiệu số:
Đặt \(d_N = p_N - p_{N-1}\). Hệ thức tương đương với \((10 - N)d_{N+1} = N d_N\), nên với \(d_1 = p_1\):
\[d_2 = \frac{d_1}{9}, \quad d_3 = \frac{d_1}{36}, \quad d_4 = \frac{d_1}{84}, \quad d_5 = \frac{d_1}{126}\]
\[\frac{1}{2} = p_5 = d_1 \left(1 + \frac{1}{9} + \frac{1}{36} + \frac{1}{84} + \frac{1}{126}\right) = d_1 \cdot \frac{73}{63}\]
Suy ra \(p_1 = \frac{63}{146}\) (đáp án C của đề AMC).
Công thức kinh điển (Huygens; Ross, A First Course in Probability):
Nếu mỗi bước sang phải với xác suất \(p\) không đổi, sang trái với xác suất \(q = 1 - p \neq p\), trạng thái hấp thụ là 0 và \(N\), thì xác suất đạt \(N\) trước khi về 0, xuất phát từ vị trí \(i\), là:
\[P_i = \frac{1 - \left(\frac{q}{p}\right)^i}{1 - \left(\frac{q}{p}\right)^N}\]
Khi \(p = q = \frac{1}{2}\) thì \(P_i = \frac{i}{N}\). Trong trường hợp công bằng, kì vọng số ván đến khi kết thúc là:
\[E_i = i(N - i)\]
Dạng 5. Quy hoạch động cho kì vọng
Ví dụ 11:
Tung liên tiếp một đồng xu cân đối cho tới khi xuất hiện hai mặt ngửa liên tiếp thì dừng. Trung bình phải tung bao nhiêu lần?
Trạng thái:
Gọi \(E_0\) là kì vọng số lần tung còn lại khi chưa có mặt N ở cuối (kể cả lúc bắt đầu);
\(E_1\) là kì vọng khi vừa tung được một mặt N.
Hệ thức:
Mỗi lần tung tốn 1 lượt rồi chuyển trạng thái:
\[E_0 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0, \quad E_1 = 1 + \frac{1}{2} \cdot 0 + \frac{1}{2}E_0\]
Từ phương trình đầu, ta có: \(E_0 = 2 + E_1\).
Thay vào phương trình sau:
\[E_1 = 1 + \frac{1}{2}(2 + E_1) \implies E_1 = 4, \quad E_0 = 6\]
Nếu chờ dãy NS (ngửa rồi sấp) thay vì NN, kì vọng chỉ là 4. Lí do: khi đang chờ NN mà tung ra S, ta mất hết “tiến độ”; còn khi chờ NS mà tung ra N, ta vẫn giữ nguyên tiến độ. Đây là câu hỏi kinh điển trong giáo trình Stat 110 (Harvard) của J. Blitzstein và là chủ đề “trò chơi Penney” nổi tiếng.
