Sức mạnh của xác suất [4]
Ngô Quang Hưng | 29 tháng 11, 2005 | 
Bản để in
Có n phong bì, mỗi phong bì đựng một số tiền khác nhau. Các phong bì này được hoán vị ngẫu nhiên và xếp thành một hàng dài. Ta chơi trò chơi sau đây: mở từng phong bì một. Mỗi lần mở xong một phong bì mới ta có quyền quyết định ngừng chơi. Nếu ta ngừng chơi ngay khi vừa mở xong phong bì có số tiền lớn nhất (trong n số) thì ta thắng số tiền đó. Ngược lại thì không được gì cả. Làm thế nào để thiết kế một chiến lược chơi sao cho xác suất ta thắng tiền càng lớn càng tốt? Xác suất lớn nhất có thể đạt được là bao nhiêu?
Ví dụ: nếu ngừng ngay sau khi mở phong bì thứ nhất thì xác suất thắng là 1/n. Với n thật lớn, có cách nào mà xác suất thắng ít nhất là một hằng số không?
Bài này thuộc lớp bài toán day-trading phải không ạ.
Tôi mù tịt về các bài toán day-trading. Nghe bạn nói đi tìm lòng vòng thì có vẻ bài này thuộc loại đó. Tôi đọc được bài này trong một ngữ cảnh khác (các nghịch lý trong lý thuyết xác suất - cụ thể là nghịch lý 2 phong bì). Nếu bạn có links nào về các bài toán day-trading thì xin chia sẻ.
Tôi xin lỗi vì cũng mù tịt về bài toán này.
Tôi chỉ muốn hỏi: nếu tôi có 1 bài toán cần giúp đỡ (về graph) thì tôi có thể post câu hỏi ở đâu và như thế nào ở trong blog này.
Em cũng mới mày mò thôi. Thấy bài toán gọn quá, muốn có lời giải nhưng kiến thức chưa đủ :), nên search một hồi rồi cả hỏi loạn lên.
Bài toán day-trading cụ thể như sau:
Một hộp bao gồm n các quả bóng được đánh số ngẫu nhiên (không nhất thiết từ 1-n nhưng là các số khác nhau và có thể bao gồm các số lớn hơn n). Thực hiện chiến thuật sau.
Bước 1: Đầu tiên, lấy ra lần lượt một nhóm các quả bóng (và biết được các số đánh trên các quả bóng đó), giả thiết với số lượng m = np, với p n-1)đại diện cho xác suất thắng khi dừng tại bước k+1, nghĩa là: Xk = A and B, trong đó
A = sự kiện số lớn nhất trong k số đầu tiên nằm trong tập m quả rút đầu tiên (m=np) -> p(A) = m/k.
B = sự kiện quả thứ k+1 mang số lớn nhất trong n số -> p(B) = 1/n
2 sự kiện này độc lập, vì vậy p(Xk) = p(A).p(B) = m/k . 1/n = n.p/k.n = p/k
(coi 0/0 =1 cho trường hợp số đầu tiên đã là số lớn nhất)
Vậy xác suất thắng với một p cho trước sẽ là Win(p) = Sum (p.1/k) | k= m -> n-1 ;
-> Win (p) = p. Sum (1/k) | k = m-> n-1;
-> Win (p) ~ p. { Tích phân từ m=np đến n-1 của 1/k} ~ -plnp
Giờ thì quay lại khảo sát hàm số, Win(p) đạt cực trị khi Win’(p) = 0 p = e^-1; đây là cực trị max.
Đáp số là lấy m=np quả, với p = e^-1. Sau đó lấy cho tới khi có quả bóng có số lớn hơn tất cả các số còn lại
Em cũng băn khoăn về lời giải này với Two-Envelope Paradox (nghịch lý hai phong bì) mà anh nói tới. Đâu là default assumption trong lời giải trên không áp dụng được cho trường hợp nghịch lý hai phong bì
1/ Bài toán trên chỉ giải được khi xét các trường hợp mở phong bì (rút bóng, mở gói quà, etc) là độc lập; trong khi bài toán về nghịch lý hai phong bì có tính đến quan hệ giữa các reference value (số tiền, số trên bóng, giá trị gói quà, etc). Từ đó mới áp dụng được phép nhân Bayes
2/ Với n đủ lớn thì có thể xấp xỉ tích phân
Em mới chỉ nghĩ được đến đấy, đúng sai thế nào anh chỉ cho em nhé
Đính chính:
Đoạn từ
“Bước 1: Đầu tiên, lấy ra lần lượt một nhóm các quả bóng (và biết được các số đánh trên các quả bóng đó), giả thiết với số lượng m = np, với p n-1)đại diện cho xác suất thắng khi dừng tại bước k+1, nghĩa là: Xk = A and B, trong đó
A = sự kiện số lớn nhất trong k số đầu tiên nằm trong tập m quả rút đầu tiên (m=np) -> p(A) = m/k.
B = sự kiện quả thứ k+1 mang số lớn nhất trong n số -> p(B) = 1/n”
Bị mất chữ.
Đầy đủ như sau:
Bước 1: Bước 1: Đầu tiên, lấy ra lần lượt một nhóm các quả bóng (và biết được các số đánh trên các quả bóng đó), giả thiết với số lượng m = np, với p p(A) = m/k.
B = sự kiện quả thứ k+1 mang số lớn nhất trong n số -> p(B) = 1/n
Đính chính:
Đoạn từ
“Bước 1: Đầu tiên, lấy ra lần lượt một nhóm các quả bóng (và biết được các số đánh trên các quả bóng đó), giả thiết với số lượng m = np, với p n-1)đại diện cho xác suất thắng khi dừng tại bước k+1, nghĩa là: Xk = A and B, trong đó
A = sự kiện số lớn nhất trong k số đầu tiên nằm trong tập m quả rút đầu tiên (m=np) -> p(A) = m/k.
B = sự kiện quả thứ k+1 mang số lớn nhất trong n số -> p(B) = 1/n”
Bị mất chữ; nhờ anh Hưng xóa hộ comment thừa
Đầy đủ như sau:
Bước 1: Bước 1: Đầu tiên, lấy ra lần lượt một nhóm các quả bóng (và biết được các số đánh trên các quả bóng đó), giả thiết với số lượng m = np, với p nhỏ hơn 1
Bước 2: Tiếp tục lấy bóng cho đến khi lấy được quả bóng có đánh số lớn hơn tất cả các số trước đấy.
Tìm p để sao cho xác xuất quả bóng tại thời điểm dừng có giá trị lớn nhất trong n quả.
Bài này em lấy ra từ quyển Probability, Random and Stochastic Processs A. Papoulis and S. U. Pillai mượn của bạn, em ko có softcopy.
Quay lại bài toán, phân hoạch sự kiện ra thành n nhóm độc lập, với p=1/n; 2/n ..n-1/n và trường hợp ngay quả đầu tiên đã có số lớn nhất (có thể coi là với p = 0). Có thể thấy phân hoạch này không giao nhau và hội của chúng phủ đầy đủ sự kiện. Với một p xác định trong phân hoạch đó đặt Xk là đại diện cho xác suất thắng khi dừng tại bước k+1, nghĩa là: Xk = A and B, trong đó
A = sự kiện số lớn nhất trong k số đầu tiên nằm trong tập m quả rút đầu tiên (m=np); p(A) = m/k.
B = sự kiện quả thứ k+1 mang số lớn nhất trong n số; p(B) = 1/n
Về vụ câu hỏi graph theory, bạn có thể đặt câu hỏi ở trang mới tạo: gỡ rối tơ lòng
Lời giải của bạn có thể viết lại như sau (trong bài toán n phong bì đã nêu): mở m phong bì (với m xác định sau) - sau đó lần lượt mở các phong bì từ (m+1) đến n, dừng lại ngay khi thấy số tiền lớn hơn tất cả m phong bì đầu tiên.
Ta chỉ thắng khi mà số tiền lớn nhất nằm trong một phong bì thứ k nào đó (
) và tất cả các phong bì từ (m+1) đến (k-1) đều mang số tiền nhỏ hơn số lớn nhất trong m phong bì đầu. Xác suất mà điều này xảy ra — với k cố định — là
là tốt nhất.
Bỏ qua các trường hợp tầm thường, xác suất mà ta thắng tiền là
Đến đây ta có thể dùng bất đẳng thức
để xấp xỉ cái tổng
Phần còn lại, khảo sát hàm như bạn đã làm cho đáp số
Đây cũng là lời giải tốt nhất mà tôi biết cho bài này. Bài này đúng là không liên quan đến nghịch lý 2 phong bì kia; tôi chỉ đọc được từ cùng một chỗ thôi.