跳转到内容

秘書問題

维基百科,自由的百科全书
(重定向自秘书问题

機率賽局理論上,秘书问题(Secretary problem),类似的名称有37%法則[1]麥穗理論[2]相亲问题止步问题见好就收问题苏丹的嫁妆问题挑剔的求婚者问题等,屬於最佳停止問題英语Optimal stopping[3]。内容是这样的:要聘请一名秘书,有 n 个应聘者。每次面试一人,面试后就要即时决定是否聘他,如果当下决定不聘他,他便不会回来。面试后总能清楚了解应聘者的合适程度,并能和之前的每个人做比较。问什么样的策略,才使最佳人选被选中的概率最大。

求解最优策略

这个问题的最优解是一个停止规则。在这个规则里,面试官会拒绝头 r - 1 个应聘者(令他们中的最佳人选为 应聘者 M),然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。(如果M在所有n个应聘者中也是最好的一个,那么这个策略将选不出任何人选)对于任意的截断值 r,最佳人选被选中的概率是:


求和符号内概率的计算是基于:如果应聘者 i 是(所有应聘者中的)最佳人选,他被选中当且仅当头 i - 1 个应聘者中的最佳人选处在头 r - 1 个被拒绝的应聘者中。令 n 趋近无穷大,把 x 表示为 r/n 的极限,令 ti/ndt1/n,总和可以近似为如下积分:

令 P(x) 对 x 的导数为 0,解出 x,我们得到最优的 x 等于 1/e。从而,当 n 增大时,最优截断值趋近于 n/e 最佳人选被选中的概率为 1/e

对于较小的 n 值, 最优的 r 也可以通过动态规划方法得到。下表给出了一些最优的 r 值:

n 1 2 3 4 5 6 7 8 9
r 1 1 2 2 3 3 3 4 4
P 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.406

此問題的变种

  • 選擇者可選多於一人
  • 求職者的數目未知
  • 求職者之間的關係可影響選擇
  • 被拒絕的求職者有一定機率能被叫回來
  • 選擇者滿足於次好的人

參考

譯自本頁英文版

  • T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1988.
  • 數學傳播第二卷第三期 : 海外學人相親記 [1]页面存档备份,存于互联网档案馆

本版未標示充足內容請見英文版

  1. ^ 葉茲 (Kit Yates). 其實攸關貧富與生死的數學並不難!選擇障礙必備的37%法則 (The Maths of Life and Death). 天下文化. 由林俊宏翻译 (遠見·天下文化事業群). 2022-08-15. (原始内容存档于2024-03-10). 
  2. ^ 劉潤. 麥穗理論─如何選擇人生中最大的那支麥穗?. 工商時報. 2020-07-18. (原始内容存档于2024-03-10). 
  3. ^ 林希陶. 人生大事難以抉擇?用「最佳停止點」來幫助你下決定吧!. PanSci 泛科學. 2019-03-19. (原始内容存档于2023-03-27).