Secretary Problem

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%.

(Nguồn: https://changyaochen.github.io/blog/ )

Đề 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.

Đây là điều đẹp đẽ nhất của bài toán: cả ngưỡng dừng tối ưu lẫn xác suất thắng đều bằng 1/e ≈ 36,8%. Hằng số e — vốn quen thuộc trong lãi kép và tăng trưởng mũ — bất ngờ xuất hiện ở một bài toán tuyển dụng.

(Nguồn: https://www.going2paris.net/post/the-secretary-problem )

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/

Birthday Paradox

Trong một căn phòng chỉ có 23 người, khả năng để ít nhất hai người có cùng ngày sinh nhật (ngày và tháng) là bao nhiêu? Nhiều người sẽ đoán con số này sẽ rất thấp. Tuy nhiên, câu trả lời thực tế lại vượt quá 50%. Nếu số người tăng lên 57, tỷ lệ này sẽ tăng lên tới hơn 99%.

(Nguồn: https://github.com/inversia/birthday-paradox )

Hiện tượng này được gọi là Nghịch lý Ngày sinh (Birthday Paradox). Nó không phải là một nghịch lý theo nghĩa mâu thuẫn tính toán, mà là một "nghịch lý thị giác" đối với giác quan thông thường: kết quả toán học hoàn toàn chính xác nhưng lại đi ngược lại suy đoán tự nhiên của con người.

Tại sao não bộ chúng ta bị "đánh lừa"?

Lý do chính khiến hầu hết mọi người ước tính sai là vì chúng ta thường cá nhân hóa bài toán.

Khi nghe câu hỏi, bạn thường tự hỏi: "Tỷ lệ để ai đó trong phòng có cùng ngày sinh với chính tôi là bao nhiêu?". Nếu chỉ so sánh ngày sinh của 22 người còn lại với bạn, xác suất đúng là rất thấp. Để có 50% cơ hội tìm thấy một người trùng ngày sinh với riêng bạn, căn phòng cần tới 253 người.

Tuy nhiên, Nghịch lý Ngày sinh không yêu cầu trùng với một người cụ thể. Câu hỏi ở đây là: Có hai người bất kỳ nào trong phòng trùng ngày sinh với nhau hay không?

Cách dễ nhất là tính xác suất của biến cố đối: xác suất để không ai trùng sinh nhật với ai.

Giả sử đơn giản hóa: 365 ngày, mỗi ngày có khả năng như nhau, bỏ qua năm nhuận và sinh đôi.

• Người thứ 1: được chọn thoải mái → 365/365
• Người thứ 2: phải né ngày của người 1 → 364/365
• Người thứ 3: phải né 2 ngày → 363/365
• ...
• Người thứ n: → (365 − n + 1)/365

 Nhân tất cả lại: 

(Nguồn: https://ritambhara.in/blog/details/birthday-paradox-birthday-problem/286)

          Với n = 23, biểu thức này cho ra 0,5073 — tức 50,73%. 

Khi chuyển hướng sang việc so sánh "mọi người với nhau", số lượng cặp so sánh tăng lên rất nhanh. Với 23 người, số lượng cặp đôi có thể tạo ra để so sánh là 253 cặp. Với 253 cơ hội để xảy ra sự trùng hợp, việc tỷ lệ vượt qua mức 50% trở nên dễ hiểu hơn rất nhiều.

 

Tỷ lệ thay đổi thế nào theo sĩ số nhóm?

Sự bùng nổ của xác suất theo quy mô nhóm thể hiện rất rõ qua các con số:

Số người trong phòng (n)	Xác suất có ít nhất 2 người trùng ngày sinh
10	11.7%
23	50.7%
30	70.6%
57	99.0%
70	99.9%

Nghĩa là, chỉ cần một hội trường nhỏ với khoảng 70 người, khả năng tìm thấy hai người cùng ngày sinh đã gần như là chắc chắn. 

Từ lớp học đến an ninh mạng

Nghịch lý Ngày sinh không chỉ là một câu đố vui toán học. Nguyên lý này đóng vai trò then chốt trong khoa học máy tính và mật mã học, cụ thể là về bài toán Tấn công Ngày sinh (Birthday Attack).

Trong an ninh mạng, các hàm băm (hash functions) được dùng để biến đổi dữ liệu thành chuỗi ký tự có độ dài cố định. Về lý thuyết, mỗi dữ liệu sẽ có một chuỗi băm riêng. Tuy nhiên, tương tự như việc tìm hai người trùng ngày sinh, việc tìm ra hai tập dữ liệu khác nhau nhưng tạo ra cùng một mã băm (gọi là "độ đụng độ" hay collision) dễ xảy ra hơn chúng ta tưởng rất nhiều.

Các kỹ sư an ninh mạng bắt buộc phải sử dụng các độ dài chuỗi băm đủ lớn để ngăn chặn kẻ tấn công lợi dụng Nghịch lý Ngày sinh nhằm phá khóa mã hóa.

Tài liệu tham khảo và đọc thêm

• https://betterexplained.com/articles/understanding-the-birthday-paradox/
• https://pi.math.cornell.edu/~mec/2008-2009/TianyiZheng/Birthday.html
• https://math.info/Misc/Birthday_Problem/

The Coupon Collector’s Problem

Giả sử một hãng phát hành 50 mẫu thẻ khác nhau. Mỗi lần mua một gói sản phẩm, bạn nhận được ngẫu nhiên một thẻ, và tất cả các thẻ đều có xác suất xuất hiện như nhau.

Câu hỏi đặt ra là:

Trung bình phải mua bao nhiêu gói để sưu tập đủ cả 50 mẫu?

Nhiều người sẽ đoán khoảng 50–70 gói. Tuy nhiên, đáp án đúng lại vào khoảng 225 gói. Điều này nghe có vẻ khó tin, nhưng lại hoàn toàn hợp lý khi nhìn dưới góc độ xác suất.

Nói cách khác, để có đủ các loại thẻ, trung bình bạn phải mua nhiều gấp hơn năm lần số lượng loại thẻ tồn tại.

(Nguồn: https://www.reddit.com/r/Tradingcards/comments/1lc00cr/bear_fruit_snack_trading_cards/)

Điều gì khiến con số này lớn như vậy?

Hãy tưởng tượng quá trình sưu tập diễn ra từng bước.

Lần đầu tiên, chắc chắn bạn nhận được một loại mới.

Lần thứ hai, khả năng nhận được loại mới vẫn rất cao.

Sau khoảng vài chục lần mua, bộ sưu tập của bạn đã gần hoàn thiện.

Nhưng khi bạn đã có 99 trong số 100 loại thì sao?

Lúc này, mỗi lần mở hộp, xác suất nhận được đúng loại còn thiếu chỉ còn khoảng 1%.

Điều đó có nghĩa là bạn sẽ phải mở trung bình khoảng 100 hộp nữa chỉ để tìm được đúng một món cuối cùng.

Đó chính là nguyên nhân khiến giai đoạn cuối luôn kéo dài hơn rất nhiều so với giai đoạn đầu.

Một quy luật rất quen thuộc trong cuộc sống

Điều thú vị là hiện tượng này không chỉ xuất hiện trong việc sưu tập.

Nó xuất hiện ở rất nhiều công việc hàng ngày.

Ví dụ, khi viết một bài báo khoa học.

Có thể bạn hoàn thành được 80% bản thảo chỉ trong vài tuần.

Nhưng 20% cuối cùng – chỉnh sửa, phản biện, bổ sung tài liệu tham khảo, kiểm tra số liệu, sửa lỗi ngôn ngữ – đôi khi lại mất nhiều thời gian hơn cả phần đã viết.

Hay khi lập trình phần mềm.

Phiên bản đầu tiên có thể hoàn thành khá nhanh.

Nhưng việc sửa những lỗi cuối cùng, xử lý các trường hợp đặc biệt và tối ưu hiệu năng lại chiếm phần lớn thời gian của dự án.

Ngay cả việc dọn dẹp nhà cửa cũng vậy.

Bạn có thể dọn gần xong trong một giờ, nhưng vài góc nhỏ cuối cùng lại khiến bạn mất thêm rất nhiều thời gian.

Đây chính là tinh thần của Coupon Collector's Problem: Càng gần hoàn thành, tiến độ càng chậm.

(Nguồn: https://math.stackexchange.com/questions/3410020/analysis-of-coupon-collector-variant-with-diminishing-probabilities-of-finding-a)

Không chỉ là trò chơi. Ngày nay, bài toán này được ứng dụng trong rất nhiều lĩnh vực khoa học.

• Khoa học dữ liệu

Một mô hình trí tuệ nhân tạo cần bao nhiêu dữ liệu để "nhìn thấy" tất cả các loại trường hợp?

Nếu một số trường hợp rất hiếm gặp thì việc thu thập dữ liệu sẽ trở nên khó khăn giống hệt việc tìm những coupon cuối cùng.

• Sinh học

Các nhà sinh thái học muốn biết đã khảo sát đủ các loài trong một khu rừng hay chưa.

Họ không thể chỉ dựa vào số mẫu đã thu thập mà phải sử dụng các mô hình xác suất để ước lượng số loài còn chưa được quan sát.

• Mạng máy tính

Một máy chủ cần nhận đủ tất cả các gói dữ liệu trước khi có thể ghép thành một tập tin hoàn chỉnh.

Một vài gói cuối cùng thường đến muộn hoặc bị mất, khiến toàn bộ quá trình bị kéo dài.

• Marketing

Nhiều chương trình khuyến mãi được thiết kế dựa trên đúng nguyên lý này.

Các bộ sticker, thẻ sưu tập, nắp chai hay blind box đều khiến người chơi phải mua nhiều hơn rất nhiều so với số lượng món đồ thực tế vì những món cuối cùng rất khó xuất hiện.

Một bài học thú vị. Coupon Collector's Problem không chỉ là một bài toán xác suất.

Nó còn nhắc chúng ta rằng cảm giác "mãi không xong" ở giai đoạn cuối của một công việc là điều hoàn toàn bình thường.

• Khi mới bắt đầu, mọi nỗ lực đều tạo ra kết quả rõ rệt.

• Nhưng càng tiến gần tới mục tiêu, mỗi bước tiến sẽ nhỏ hơn và đòi hỏi nhiều thời gian hơn.

• Điều đó không có nghĩa là bạn đang làm việc kém hiệu quả.

• Đó đơn giản là bản chất của nhiều quá trình ngẫu nhiên và cũng là điều mà toán học đã chỉ ra từ rất lâu.

Đôi khi, phần khó nhất của hành trình không phải là bắt đầu, mà chính là hoàn thành những mảnh ghép cuối cùng.

Tài liệu tham khảo

• https://mat.uab.cat/matmat_antiga/PDFv2014/v2014n02.pdf
• https://sites.math.rutgers.edu/~sc2518/21W170E3/Coupon%20collector.pdf
• https://adler.ieor.berkeley.edu/ilans_pubs/coupons_2003.pdf

FT50

FT50 (Financial Times Top 50) là danh sách gồm 50 tạp chí học thuật và thực tiễn hàng đầu thế giới về kinh tế, kinh doanh và quản trị. Danh sách này do tờ báo uy tín Financial Times tuyển chọn và sử dụng làm tiêu chuẩn vàng để đánh giá năng suất nghiên cứu của giảng viên khi xếp hạng các trường kinh doanh toàn cầu.

(Nguồn: https://bluesky-thinking.com/business-research-after-ft50-reshuffle-and-mit-sloan-management-review-closure/ )

Journal Title		Subject Area	Publisher
1	Accounting Review	Accounting	American Accounting Association
2	Accounting, Organizations and Society	Accounting	Elsevier
3	Contemporary Accounting Research	Accounting	Wiley / Canadian Academic Accounting Association
4	Journal of Accounting and Economics	Accounting	Elsevier
5	Journal of Accounting Research	Accounting	Wiley / University of Chicago
6	Review of Accounting Studies	Accounting	Springer
7	American Economic Review	Economics	American Economic Association
8	Econometrica	Economics	Wiley / Econometric Society
9	Journal of Political Economy	Economics	University of Chicago Press
10	Quarterly Journal of Economics	Economics	Oxford University Press / Harvard University
11	Research Policy	Economics, Management	Elsevier
12	Review of Economic Studies	Economics	Oxford University Press
13	Entrepreneurship Theory and Practice	Entrepreneurship	Sage
14	Journal of Business Venturing	Entrepreneurship	Elsevier
15	Strategic Entrepreneurship Journal	Entrepreneurship	Wiley / Strategic Management Society
16	Journal of Finance	Finance	Wiley / American Finance Association
17	Journal of Financial and Quantitative Analysis	Finance	Cambridge University Press
18	Journal of Financial Economics	Finance	Elsevier
19	Review of Finance	Finance	Oxford University Press / European Finance Association
20	Review of Financial Studies	Finance	Oxford University Press
21	Human Resource Management	Human Resources	Wiley
22	Information Systems Research	Information Systems	INFORMS
23	Journal of Management Information Systems	Information Systems	Taylor & Francis
24	MIS Quarterly	Information Systems	Management Information Systems Research Centre, University of Minnesota
25	Journal of International Business Studies	International Business	Palgrave Macmillan / Academy of International Business
26	Academy of Management Annals	Management	Academy of Management
27	Academy of Management Journal	Management	Academy of Management
28	Academy of Management Review	Management	Academy of Management
29	Administrative Science Quarterly	Management	Sage / Cornell University
30	Harvard Business Review	Management	Harvard Business Publishing
31	Journal of Management	Management	Sage
32	Journal of Management Studies	Management	Wiley / Society for the Advancement of Management Studies
33	Management Science	Management	INFORMS
34	MIT Sloan Management Review	Management	MIT Sloan School of Management
35	Strategic Management Journal	Management	Wiley
36	Journal of Consumer Psychology	Marketing	Wiley / Society for Consumer Psychology
37	Journal of Consumer Research	Marketing	Oxford University Press
38	Journal of Marketing	Marketing	Sage / American Marketing Association
39	Journal of Marketing Research	Marketing	Sage / American Marketing Association
40	Journal of the Academy of Marketing Science	Marketing	Springer
41	Marketing Science	Marketing	INFORMS
42	Journal of Operations Management	Operations	Wiley / Association for Supply Chain Management
43	Manufacturing & Service Operations Management	Operations	INFORMS
44	Operations Research	Operations	INFORMS
45	Production and Operations Management	Operations	Sage / Production and Operations Management Society
46	Organization Science	Organizational Behaviour	INFORMS
47	Organizational Behavior and Human Decision Processes	Organizational Behaviour	Elsevier
48	Journal of Applied Psychology	Psychology	American Psychological Association
49	Psychological Science	Psychology	Sage / Association for Psychological Science
50	American Sociological Review	Sociology	Sage / American Sociological Association

Tài liệu tham khảo

• https://www.ft.com/ft50-journals 
• https://ceibs.libguides.com/c.php?g=963339&p=7006421