Trò chơi đoán số
Trong lý thuyết xác suất, đôi khi chúng ta thấy có những kết quả, những thông tin dường như được lấy ra từ hư vô, đôi khi trái với trực giác.
Đầu tiên, hãy xem xét bài toán sau:
Hai người A và B chơi một trò chơi, trong đó mỗi người chọn ngẫu nhiên một số thực trong khoảng từ 0 tới 1.
Người B được phép đoán xem số của mình lớn hơn hay nhỏ hơn số của A. Nếu đoán đúng thì B thắng cuộc.
Nếu là B, bạn làm thế nào để tối đa hóa khả năng chiến thắng của mình?
Gọi hai số được chọn bởi A và B là a và b. Ta thấy rằng nếu B không sử dụng chiến thuật nào và đoán ngẫu nhiên, tỷ lệ thắng sẽ là 50%. Với hai số a, b ngẫu nhiên phân bố đều trong khoảng [0, 1], xác suất để b > a hoặc b < a là 50%.
Chiến thuật 1
Bây giờ, giả sử B chọn chiến thuật sau: chọn ra một số cố định X trong khoảng [0, 1]. B sẽ đoán dựa trên so sánh b và X
Nếu b > X, đoán b > a
Nếu b < X, đoán b < a
(ta không xét b = X vì xác suất này thực tế bằng 0)
Ta có thể tính xác suất này bằng hình học hoặc bằng tích phân.
Hãy bắt đầu với cách tính xác suất bằng hình học
a và b có thể nhận các giá trị từ 0 tới 1. Toàn bộ các cặp giá trị của a và b có thể được biểu diễn bằng hình vuông có cạnh là 1, b nhận các giá trị trên trục b và a nhận các giá trị trên trục a.
Xác suất để B thắng là tổng của hai xác suất
b > X và b > a, tương ứng với diện tích S1
b < X và b < a, tương ứng với diện tích S2
Xác suất để B thắng đạt cực đại khi tổng của S1 và S2 đạt cực đại. Tổng này đạt cực đại khi tổng diện tích hai tam giác màu vàng đạt cực tiểu vì S1 + S2 + S3 + S4 = 1.
Tổng diện tích hai tam giác màu vàng là
Ta biết rằng với hai số dương a, b bất kỳ
a2 + b2 ≥ (a+b)2/2, đẳng thức xảy ra khi a = b
nên tổng diện tích hai tam giác màu vàng đạt cực tiểu bằng 1/4 khi X = 1/2
Điều này có nghĩa là khi B chọn X = 1/2 và so sánh trước khi trả lời, xác suất thắng cuộc của B đạt cực đại, và bằng 1 - 1/4 = 75%.
Tính xác suất với tích phân hàm mật độ xác suất
Xác suất thứ nhất: b > X và b > a,
Ta cần tính xác suất:
P (b>X và b>a)
Điều kiện hóa theo b=x và tích phân trên đoạn x ∈ (X,1):
vì 𝑎 ∼ 𝑈(0,1) (ký hiệu này nghĩa là biến ngẫu nhiên a có phân bố đều trên khoảng (0,1)), P(a<x)=x
Quay lại với hình minh họa xác suất hình học, đây chính là diện tích phần màu xanh dương phía trên, và bằng một nửa diện tích hình vuông trừ đi diện tích phần tam giác màu vàng phía dưới 1/2 - X2/2
Xác suất thứ hai: b < X và b < a
Vì P(a>x)=1−x
Đây chính là diện tích phần màu xanh dương phía dưới, và bằng diện tích hình chữ nhật OXX1 trừ đi diện tích phần tam giác màu vàng phía dưới X - X2/2
Tức là xác suất để B thắng là tổng của hai xác suất trên:
Xác suất này có thể viết gọn lại thành: - X2 + X + 1/2
Kết quả này bằng 1 trừ đi tổng diện tích hai tam giác màu vàng.
Ta biết rằng một tam thức bậc hai có dạng -aX2 + bX + c với a âm sẽ đạt cực đại tại
X = -b/2a, biểu thức của ta đạt cực đại là 0.75 khi X = 0.5
B có thể chiến thắng với xác suất cao nhất là 0.75 khi biểu thức trên đạt cực đại, kết quả này hoàn toàn giống với khi chúng ta tính xác suất bằng hình học.
Kết quả mô phỏng Monte Carlo với 1 triệu lượt chơi cho thấy:
Không dùng chiến lược (đoán ngẫu nhiên): xác suất thắng ≈ 50.0%
Dùng chiến lược với ngưỡng X=0.5: xác suất thắng ≈ 74.96%
python
import random
def simulate_game(num_trials=1000000, threshold_strategy=True, X=0.5):
win_count = 0
for _ in range(num_trials):
# Both players pick a random number between 0 and 1
A = random.random()
B = random.random()
if threshold_strategy:
# B uses the threshold X
if B > X:
B_guess = 'greater'
else:
B_guess = 'less'
# Determine if B's guess is correct
if (B_guess == 'greater' and B > A) or (B_guess == 'less' and B < A):
win_count += 1
else:
# Without any strategy, B randomly guesses
B_guess = random.choice(['greater', 'less'])
if (B_guess == 'greater' and B > A) or (B_guess == 'less' and B < A):
win_count += 1
return win_count / num_trials
# Run simulation with and without strategy
no_strategy_result = simulate_game(threshold_strategy=False)
with_strategy_result = simulate_game(threshold_strategy=True, X=0.5)
no_strategy_result, with_strategy_result
Result
(0.500187, 0.749576)Chiến thuật 2
Tương tự như chiến thuật 1, nhưng X không cố định mà là một số ngẫu nhiên trong khoảng [0, 1]. B vẫn sẽ đoán dựa trên so sánh b và X
Nếu b > X, đoán b > a
Nếu b < X, đoán b < a
Hãy thử xem với chiến thuật trên thì khả năng chiến thắng của B có được cải thiện không, và nếu có thì cải thiện như thế nào.
Phát biểu lại
Trong tình huống này, ta có bài toán tương đương sau: Chọn ngẫu nhiên ba số thực a, b, X trong khoảng [0, 1]. Nếu đã biết b > X thì xác suất để b > a là bao nhiêu?
Tức là, tìm P(b>a ∣ b>X)
Lập luận hoán vị
Vì a, b, X là ba số ngẫu nhiên độc lập trên [0,1], nên mọi hoán vị của thứ tự các số đều có xác suất như nhau.
Có tất cả 3! = 6 thứ tự sắp xếp khác nhau của a, b, X:
a < b < X
a < X < b
b < a < X
b < X < a
X < a < b
X < b < a
Vì a, b, c hoàn toàn độc lập với nhau, nên số trường hợp mà b > X bằng số trường hợp mà X > b, và bằng một nửa số tổng số trường hợp, tức là 3. Ba trường hợp này có xác suất bằng nhau, nhưng trong hai trường hợp thì b > a. Lập luận tương tự với trường hợp b < X.
Nếu B làm theo chiến thuật này, tỉ lệ chiến thắng là 2/3.
Lập luận với tích phân hàm mật độ xác suất
Để tránh nhầm lẫn, ta ký hiệu biến ngẫu nhiên đại diện cho số mà người A và người B chọn được lần lượt là A và B.
✅ Ta có
📌 Tử số
📌 Mẫu số
Vì A,B,X∼U(0,1), ta có trên khoảng (0,1)
Thay vào các biểu thức ở trên ta được
✅ Thay vào ta được kết quả
Điều này có nghĩa là nếu số b > X thì xác suất để b > a là 2/3, tương tự với trường hợp b < X. Trong bất kỳ trường hợp nào xác suất thắng của người B là 2/3.
Có thể giải thích kết quả 2/3 này bằng một cách khác:
Với mỗi giá trị X cụ thể, người B sẽ có một xác suất thắng cụ thể Pwin(X). Giả sử chỉ có hai giá trị X = q cho Pwin(q) = 0.2 và X = t cho Pwin(t) = 0.8. Xác suất để người B chọn X = q là 40% và xác suất để người chơi chọn X = t là 60%. Trong trường hợp này, xác suất thắng của người B sẽ là 0.2 x 0.4 + 0.8 x 0.6 = 0.56
Khi X ∼ U(0,1), xác suất để B thắng là kỳ vọng của Pwin(X) trên toàn bộ các X khả dĩ trên (0,1).
Với giá trị của Pwin(X) đã tính trong chiến thuật 1.
Đây là một tích phân đơn giản, ta có thể dễ dàng tính ra kết quả là 2/3.
Ta có thể kiểm tra kết quả ở trên bằng cách mô phỏng 1 triệu lần chơi.
python
def simulate_game_with_random_X(num_trials=1000000):
win_count = 0
for _ in range(num_trials):
A = random.random()
B = random.random()
X = random.random() # Threshold is also randomly chosen
if B > X:
B_guess = 'greater'
else:
B_guess = 'less'
if (B_guess == 'greater' and B > A) or (B_guess == 'less' and B < A):
win_count += 1
return win_count / num_trials
# Run simulation with random X
random_X_strategy_result = simulate_game_with_random_X()
random_X_strategy_result
Result
0.667038Khi ngưỡng X cũng được chọn ngẫu nhiên mỗi lượt chơi, xác suất thắng của người B là khoảng 66.7%
💡 Trực giác
Bây giờ hãy cùng nhìn lại bài toán này một chút. Ban đầu B phải đưa ra một dự đoán với xác suất chính xác là 50%. Bằng một chiến lược, không cần thu thập thêm thông tin gì, B có thể nâng xác suất đó lên tới 75%. Điều này nghe có vẻ vô lý.
Thực ra thì, xác suất 50% là khi B chưa biết số của mình. Bằng việc biết số của mình, B đã có thêm thông tin, và thông tin đó nâng khả năng chiến thắng của B thêm 25%.
Nếu bạn chưa cảm thấy thuyết phục thì hãy tự đặt mình vào vị trí của B. Khi bạn chưa chọn số ngẫu nhiên của mình, bạn vẫn có thể đoán số đó sẽ lớn hơn hay nhỏ hơn số của A, và xác suất đó chắc chắn bằng 50%. Bây giờ, khi bạn đã chọn một số, giả sử là 0.8. Nếu khoảng số ngẫu nhiên của cả hai người là (0, 1), chắc hẳn bạn sẽ đoán rằng số của bạn lớn hơn, và xác suất đúng của bạn lớn hơn 50%. Niềm tin rằng xác suất đúng trong trường hợp này lớn hơn 50% là một niềm tin đúng đắn, và nó đến từ việc bạn có thêm thông tin về số của mình.
Giờ ta hãy nhìn lại bài toán thêm một lần nữa, nếu người chơi có thể chọn các số ngẫu nhiên trong khoảng tùy ý, từ âm vô cùng tới dương vô cùng, thì kết quả sẽ thế nào? Một cách thực tế hơn, số được chọn là ngẫu nhiên nhưng không có phân bố đều, thì kết quả sẽ thay đổi thế nào?
Giả sử rằng số ngẫu nhiên được hai người chọn có phân bố chuẩn với giá trị trung bình 0 (một giả định tương đối hợp lý), và phương sai là 10 (không quá hợp lý, nhưng chấp nhận được), thì ta có hàm phân phối xác suất chung như sau:
Xác suất mà A và B nằm trong một khoảng nào đó sẽ là một thể tích tương ứng. Khi ta xem xét bài toán với phân bố đều, ta đã tính tỷ lệ các diện tích. Về bản chất, ta đã tính tỉ lệ các thể tích, nhưng vì với phân bố đều, mật độ xác suất là hằng số, nên tỷ lệ thể tích cũng chính là tỷ lệ diện tích.
Trong trường hợp tổng quát hơn, ta vẫn có thể dùng tích phân và hàm mật độ xác suất để tính ra các kết quả tương tự như ta đã làm. Ví dụ, ta có thể tính được nếu B chọn X = 0 để so sánh và đưa ra kết luận thì tỉ lệ thắng sẽ là bao nhiêu.
Nhìn từ trên xuống, ta sẽ thấy heatmap như sau:
Với lập luận hoàn toàn tương tự, ta tính được xác suất mà B có thể chiến thắng nếu dùng chiến thuật 1, là tổng thể tích hai phần có đáy là hình thang màu cam trong hình dưới.
Mặc dù đồ thị này kéo dài tới vô hạn, ta biết rằng nó đối xứng tâm ở (0, 0), và vì thế tổng thể tích cần tính bằng 3/4 tổng thể tích toàn bộ phần không gian dưới bề mặt tạo bởi hàm mật độ xác suất chung. Xác suất thắng của B vẫn là 75%.
Nếu ta chọn một giá trị X khác 0, ta không thể dùng tính chất đối xứng để tìm ra kết quả, mà phải tính các tích phân như ở phần trước. Với hàm mật độ xác suất bất kỳ, các phép tính này có thể sẽ khó thực hiện.
