Một bài puzzle nữa về sequential decision
Nguyễn Xuân Long | 10 tháng 12, 2005 | 
Bản để in
Bài này cũng tương tự như (có lẽ dễ hơn một chút) bài toán thổi bóng . Khác ở đây là các quả bóng đã được thổi sẵn :-), nhưng dẫu sao cũng thuộc một dạng optimal sequential decision making problem:
Giả sử có n quả bóng đã được thổi, có thể tích 
để trong một cái giỏ. Bạn bị bịt mắt và chỉ có thể dựa vào khả năng so sánh 2 quả bóng trong tay xem quả nào lớn hơn mà thôi. Đầu tiên, bạn sẽ nhặt hoàn toàn ngẫu nhiên một quả bóng trong giỏ. Sau đó tiếp tục như sau: Tại từng thời điểm, bạn nhặt hoàn toàn ngẫu nhiên thêm một quả trong giỏ, so sánh quả vừa nhặt và quả đang có trong tay, so sánh xem quả nào lớn/nhỏ hơn và sẽ giữ lại một quả trong số hai quả đó. Quả bóng đã bỏ đi rồi thì không được nhặt lại nữa. Hỏi làm thế nào nhặt ra được quả bóng lớn nhất (quả có thể tích 1), với xác suất cao nhất? Xác suất cao nhất ấy là bao nhiêu (khi n tiến tới vô hạn)?
Trích từ: Optimal stopping rules. A. N. Shiryayev. Springer-Verlag, 1978.
Xin nói thêm, bài trên có kết quả tính toán được khi
rất ngắn gọn.