TRÒ CHƠI RUSSIAN ROULETTE
Russian roulette là trò chơi mà hai người sẽ dùng một khẩu súng lục 6 ổ đạn, trong đó chỉ có một ổ có chứa đạn. Ban đầu súng sẽ được lên đạn ngẫu nhiên. Người chơi đầu tiên sẽ tự chĩa súng vào đầu mình và bóp cò. Nếu như còn sống, anh ta sẽ đưa cho đối phương và người này cũng sẽ phải làm tương tự. Cứ luân phiên như vậy, trò chơi kết thúc khi viên đạn duy nhất phát nổ.
TỔNG QUÁT HOÁ BÀI TOÁN
Lấy cảm hứng từ trò chơi Russian roulette nêu trên, ta xét bài toán tổng quát sau đây.
Có n người chơi (n ≥ 2) A1, A2, …, An, mỗi người có một khẩu súng riêng giống nhau (6 ổ đạn, 1 ổ duy nhất có đạn). Trong mỗi lần thử, xác suất đạn phát nổ là p, xác suất không có đạn nổ là q = 1 – p, không phụ thuộc vào những lượt bắn của người khác.
Đầu tiên, A1 dùng súng của mình để tự bắn. Tiếp, A2 cũng tự bắn mình bằng súng của mình. Cứ lần lượt như vậy, người cuối cùng sống sót là người chiến thắng. Nghe dã man không?
Ta cần tính xác suất chiến thắng P(i, n) của người thứ i trong n người chơi.
VỚI N = 2
Xét trường hợp chỉ có 2 người chơi. Ở lượt bắn bất kỳ, nếu súng của A1 nổ, anh ta sẽ chết và A2 thắng; ngược lại vai trò của A1 và A2 sẽ đổi chỗ cho nhau. Từ đó, ta có công thức sau đây:
P(1, 2) = p.0 + q.P(2, 2)
Lưu ý, P(1, 2) = 1 – P(1, 2)
Từ đó ta tính được P(1, 2) = q/(1+q), P(2, 2) 1/(1+q). Nếu p=1/6, thì xác suất chiến thắng của A1, A2 lần lượt là 5/11 và 6/11.
LỜI GIẢI ĐỆ QUY
Với n bất kỳ, P(i, n) có thể được tính thông qua đệ quy: P(i, 2), P(i, 3)… và cứ như vậy.
Với n = 3
Có hai trường hợp như sau:
1. A1 nổ súng và chết. Còn lại A2 và A3, họ sẽ chơi giống như trường hợp 2 người chơi theo thứ tự A2 -> A3.
2. A1 sống sót. Họ sẽ chơi tiếp theo thứ tự A2 -> A3 -> A1.
Từ đó ta thu được những công thức sau:
P(1, 3) = p.0 + q.P(3, 3)
P(2, 3) = p.P(1, 2) + q.P(1, 3)
P(3, 3) = p.P(2, 2) + q.P(2, 3)
Trong đó P(1, 2) và P(2, 2) đã được tính phía trên, và P(1, 3) + P(2, 3) + P(3, 3) = 1.
Giải hệ phương trình trên ta được:
P(1, 3) = pq/(1+q) + q^3/(1+q+q^2)
P(2, 3) = q/(1+q+q^2)
P(3, 3) = p/(1+q) + q^2/(1+q+q^2)
Với n = 4
Tương tự, ta cũng xây dựng hệ công thức sau:
P(1, 4) = p.0 + q.P(4, 4)
P(2, 4) = p.P(1, 3) + q.P(1, 4)
P(3, 4) = p.P(2, 3) + q.P(2, 4)
P(4, 4) = p.P(3, 3) + q.P(3, 4)
Tổng quát
Ta có được công thức đệ quy sau:
P(i, n) = p.P(i-1, n-1) + q.P(prev(i), n)
Quy ước:
· P(0, n) = 0
· prev(i) là chỉ số của người chơi liền trước người chới thứ i (ví dụ: prev(2) = 1, prev(1) = n, …)
Chẳng dại gì mà ta đi tính bằng tay lần lượt những bước như trên. Ta sẽ bỏ vào máy tính cho nó chạy. Code ở đây (Python). Kết quả thu được như sau (có thể có sai số do làm tròn):
P(1, 5) = 0.1828
P(2, 5) = 0.1904
P(3, 5) = 0.1989
P(4, 5) = 0.2084
P(5, 5) = 0.2194
…
Có thể thấy, người chơi đầu tiên là thiệt nhất, và tỉ lệ chiến thắng tăng dần cho các người chơi sau. Điều này đã được chứng minh trong bài báo gốc (họ đã xây dựng được công thức tổng quát thay vì đệ quy).
Một điểm đáng lưu ý nữa là với p nhỏ, tức q gần 1, các P(i, n) có giá trị xấp xỉ nhau với cùng n, và gần bằng 1/n.
Người ta cũng xây dựng được công thức xấp xỉ nếu rất rất nhiều người tham gia chơi Russian roulette. Nhưng tình huống này nghe vẻ hơi phi thực tế nhỉ?
