Bạn đang đi tìm thuê một căn phòng trọ. Thị trường nóng, phòng đẹp vừa đăng lên là có người chốt ngay trong ngày. Bạn xem căn thứ nhất — khá ổn. Thuê luôn? Nhưng lỡ căn thứ hai đẹp hơn thì sao? Bỏ qua? Nhưng lỡ nó là căn tốt nhất trong cả tháng tìm kiếm thì sao?
Đây không phải là chuyện thiếu quyết đoán. Đây là một bài toán toán học có lời giải chính xác, mang tên Bài toán Thư ký (Secretary Problem) — và câu trả lời của nó là một con số kỳ lạ: 37%.
Đề bài
Bài toán cổ điển được phát biểu như sau. Bạn cần tuyển một thư ký, và luật chơi là:
- Có đúng n ứng viên, và bạn biết trước con số n.
- Họ đến phỏng vấn theo thứ tự hoàn toàn ngẫu nhiên.
- Sau mỗi buổi phỏng vấn, bạn chỉ biết thứ hạng tương đối của người này so với những người đã gặp (ví dụ: "giỏi thứ 2 trong 5 người đã gặp"), chứ không có điểm số tuyệt đối.
- Bạn phải quyết định ngay lập tức: nhận hoặc loại. Quyết định là không thể đảo ngược — đã loại thì không gọi lại được, đã nhận thì dừng cuộc tuyển.
- Mục tiêu: tối đa hóa xác suất chọn đúng người giỏi nhất trong toàn bộ n người.
Điều kiện số 5 rất khắc nghiệt: chọn được người giỏi thứ nhì cũng bị tính là thất bại hoàn toàn, y như chọn người dở nhất. Đây là bài toán "được ăn cả, ngã về không".
Chiến lược tối ưu: Nhìn rồi mới Nhảy
Trực giác đầu tiên có thể là: "Cứ chọn đại một người ngẫu nhiên" — xác suất thắng là 1/n. Với 100 ứng viên thì chỉ 1%. Quá thấp.
Chiến lược tối ưu thực ra rất đơn giản, gồm hai giai đoạn:
- Giai đoạn Quan sát: Phỏng vấn k ứng viên đầu tiên và loại toàn bộ, dù họ có xuất sắc đến đâu. Mục đích duy nhất là thiết lập một "chuẩn mực" — ghi nhớ ai là người giỏi nhất trong nhóm này.
- Giai đoạn Hành động: Từ ứng viên thứ k+1 trở đi, chọn ngay người đầu tiên giỏi hơn tất cả những người đã gặp. Nếu đi hết danh sách mà không ai vượt chuẩn, bạn buộc phải nhận người cuối cùng (và coi như thua).
Toàn bộ bài toán quy về một câu hỏi duy nhất: k nên bằng bao nhiêu?
- k quá nhỏ → bạn chốt quá vội, chuẩn mực chưa đủ cao.
- k quá lớn → bạn kén chọn quá lâu, và rất có thể người giỏi nhất đã nằm trong nhóm bị bạn loại thẳng tay.
Bảng tra cứu cho n cụ thể
Với n nhỏ, công thức xấp xỉ chưa chính xác. Đây là các giá trị tối ưu tính trực tiếp:
Số ứng viên (n) | Số người cần bỏ qua (k) | Xác suất thắng |
|---|---|---|
3 | 1 | 50,0% |
4 | 1 | 45,8% |
5 | 2 | 43,3% |
10 | 3 | 39,9% |
20 | 7 | 38,4% |
50 | 18 | 37,4% |
100 | 37 | 37,1% |
1.000 | 368 | 36,8% |
∞ | n/e | 36,79% |
Bài toán Thư ký sinh ra cả một nhánh nghiên cứu tên là lý thuyết dừng tối ưu (optimal stopping theory), với vô số biến thể: bài toán hậu tiến sĩ (chọn người giỏi thứ nhì), bài toán Robbins, bài toán thư ký có chi phí phỏng vấn, phiên bản có nhiều vị trí cần tuyển...
Tài liệu tham khảo và đọc thêm
- https://www2.math.upenn.edu/~ted/210F10/References/Secretary.pdf
- https://www.randomservices.org/random/urn/Secretary.html
- https://eventuallyalmosteverywhere.wordpress.com/2013/09/13/the-secretary-problem/
Không có nhận xét nào:
Đăng nhận xét