5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English
第一章 秘书问题与 1/e:只看名次、不能回头时何时停下
一个游戏与它的六个条件
加德纳 1960 年介绍的「古戈尔游戏」后来被改写成更容易讲的故事:一个职位有 名求职者,他们以随机的顺序一个一个来面试;面试官每见一个人,只能判断此人比之前见过的人好还是差,看不到绝对分数;每见完一个人必须当场决定录用或拒绝,拒绝了就不能再回头;只有录用到全部 人中最好的那一个才算成功。弗格森把这个问题的「最简形式」归纳为六条:只有一个职位;求职者人数 已知;求职者以随机顺序依次面试,每种顺序的可能性相同;可以把所有求职者从好到差排序(没有并列),但是否录用只能依据已面试者之间的相对名次;被拒绝的人不能再被召回;只对最好的那一个满意,即选中全体最佳者得 1、否则得 0 (Ferguson 1989)。最后一条是目标:第二名与最后一名同样算失败。
这几条都很重要。第二章与第六章会看到,改动其中任何一条,最优的做法都会明显不同。
阈值规则的精确成功概率
在这些条件下,一个很自然的规则是阈值规则:先拒绝前 个人,只用来「了解行情」;从第 个人开始,录用第一个比之前所有人都好的人(称为「相对最佳者」);如果到最后都没有出现,就没有录用任何人(或者只能录用最后一个人,这对「选中第一名」的概率没有影响)。
推导
设全体最好的人在第 位(概率 )。如果 ,他被拒绝了,规则失败。如果 ,规则选中他的条件是:第 位到第 位之间没有出现相对最佳者,也就是前 人中最好的那个落在前 位,概率为 。所以 而 (录用第一个人)。令 ,当 很大时求和近似为 ,于是 ;对 求导,,得 ,最大值也是 。
为什么最好的规则一定是阈值规则?可以用逆向归纳(动态规划)验证。第 个人是相对最佳者的概率是 ;如果他是相对最佳者,他也是全体最佳者的概率是 ,随 增大;而「放过他、继续用最优方式往下走」的成功概率 随 减小。所以一旦在某一位停下比继续好,之后每一位也都是停下更好:最优规则必然是「从某一位开始,遇到相对最佳者就停」。这类问题称为单调停止问题,只看下一步的「一步前瞻」规则就是最优的;邓金 1963 年把秘书问题写成马尔可夫过程的停时问题,证明了这一点 (Dynkin 1963)。
推导
程序对不同的 用精确公式找出最好的阈值 ,并用逆向归纳独立地算出最优成功概率与「从第几位开始停」,两者应当一致;然后列出 时成功概率随跳过比例的变化,与极限近似 比较;最后用 20,000 次模拟检验 、 时的公式。
# Classical secretary problem: cutoff rule r (skip r - 1, then take the first relative
# best). Exact P(r) = (r-1)/n * sum_{i=r}^{n} 1/(i-1); backward induction as a check.
import math, random
def p_cutoff(n, r):
return 1 / n if r == 1 else (r - 1) / n * sum(1 / (i - 1) for i in range(r, n + 1))
def dp(n): # v: success probability after passing applicant i
v, stop_from = 0.0, n
for i in range(n, 0, -1): # i is a relative best w.p. 1/i, then overall best w.p. i/n
if i / n >= v:
stop_from = i
v = (1 / i) * max(i / n, v) + (1 - 1 / i) * v
return v, stop_from
def simulate(n, r, runs, rng):
wins = 0
for _ in range(runs):
order = list(range(n)); rng.shuffle(order) # 0 = the best applicant
bar = min(order[:r - 1])
wins += next((x for x in order[r - 1:] if x < bar), None) == 0
return wins / runs
if __name__ == "__main__":
print(" n cutoff r* skipped share P(success) DP value DP stops from")
for n in (5, 10, 11, 20, 40, 100, 1000):
r = max(range(1, n + 1), key=lambda r: p_cutoff(n, r)); v, s = dp(n)
print(f"{n:5d} {r:6d} {(r - 1) / n:6.3f} {p_cutoff(n, r):.4f}"
f" {v:.4f} {s:5d}")
print(f"limit: skip share and P(success) both -> 1/e = {1 / math.e:.4f}")
print("n = 100: skip share x, exact P, approximation -x ln x")
for x in (0.10, 0.20, 0.30, 0.37, 0.50, 0.60):
print(f" x = {x:.2f} P = {p_cutoff(100, round(100 * x) + 1):.3f}"
f" -x ln x = {-x * math.log(x):.3f}")
sim = simulate(100, 38, 20000, random.Random(1960))
print(f"simulation, n = 100, r = 38, 20,000 runs: {sim:.4f}")
print(f"nobody chosen (best among the skipped), n = 40, r = 16: {15 / 40:.3f}")
# n cutoff r* skipped share P(success) DP value DP stops from
# 5 3 0.400 0.4333 0.4333 3
# 10 4 0.300 0.3987 0.3987 4
# 11 5 0.364 0.3984 0.3984 5
# 20 8 0.350 0.3842 0.3842 8
# 40 16 0.375 0.3757 0.3757 16
# 100 38 0.370 0.3710 0.3710 38
# 1000 369 0.368 0.3682 0.3682 369
# limit: skip share and P(success) both -> 1/e = 0.3679
# n = 100: skip share x, exact P, approximation -x ln x
# x = 0.10 P = 0.235 -x ln x = 0.230
# x = 0.20 P = 0.326 -x ln x = 0.322
# x = 0.30 P = 0.365 -x ln x = 0.361
# x = 0.37 P = 0.371 -x ln x = 0.368
# x = 0.50 P = 0.349 -x ln x = 0.347
# x = 0.60 P = 0.309 -x ln x = 0.306
# simulation, n = 100, r = 38, 20,000 runs: 0.3731
# nobody chosen (best among the skipped), n = 40, r = 16: 0.375结果有四点值得注意。第一,精确公式与逆向归纳给出的成功概率和停止位置完全一致,最优规则确实是阈值规则。第二,有限 时最优跳过的比例并不正好是 37%: 时跳过 3 人(30%), 时 35%, 时 37.5%, 时 36.8%;成功概率从 时的 0.433 逐渐降到极限 0.368,始终略高于 。 的模拟结果 0.3731 与精确值 0.3710 的差别在一个标准误(约 0.0034)之内。第三, 时最优规则是录用第一个出现在第 5 位及以后的相对最佳者;弗格森注意到,开普勒在 11 位候选人中最终选的恰好也是第 5 位,但这只是数字上的相合,下文会说明开普勒并不符合这个问题的条件。
第四,也是最实用的一点:成功概率在最优点附近很平坦。 时,跳过 30% 的成功概率为 0.365,跳过 50% 为 0.349,都与最优的 0.371 相差不多;真正有害的是跳过得太少(10% 时只有 0.235)或太多(60% 时 0.309)。所以「37%」更像一个区间的中心,而不是需要精确遵守的数字。
规则也会失败
最优规则的成功概率约为 37%,意味着约 63% 的时候它没有选中第一名。失败有两种。一种是最好的人恰好在被跳过的前 人里,之后不会再出现相对最佳者,结果一个人也没录用(或被迫录用最后一个人):这种情形的概率是 ,、 时为 37.5%。另一种是录用了一个「当时的相对最佳者」,但更好的人还在后面。按「第一名或零」计分时,两种失败没有区别;但在任何现实的选择中,录用了第二名与谁也没录用的差别非常大。第二章会看到,换一个目标(例如最小化被录用者的期望名次),最优规则就完全不同。
注
「最优」是相对于目标而言的。 37% 规则最大化的是「选中第一名」的概率,它不关心选中的人有多好,也不关心空手而归。如果目标是被录用者的期望水平,或者面试本身有成本,最优的跳过比例会小得多(第二章与第六章)。把这条规则当作普遍的生活建议,等于默认了一个很少有人真正持有的目标。
谁解决了秘书问题
证据
弗格森的考证。 弗格森 1989 年在《统计科学》上发表《谁解决了秘书问题?》,梳理了这一问题的来历 (Ferguson 1989)。他认为问题最早见于加德纳 1960 年 2 月的专栏,加德纳称它为「古戈尔游戏」并归于福克斯与马尼,解答刊登于次月 (Gardner 1960);最早在学术期刊上给出解答的是林德利 1961 年用动态规划处理的论文 (Lindley 1961);邓金 1963 年把它写成马尔可夫过程的最优停时问题 (Dynkin 1963);吉尔伯特与莫斯特勒 1966 年给出了许多优雅的推导与推广,包括完全信息版本 (Gilbert and Mosteller 1966);最小化期望名次的渐近解由周元燊、森口繁一、罗宾斯与塞缪尔斯 1964 年给出 (Chow et al. 1964)。
文章题目的答案是「没有人」。弗格森的理由是:在加德纳原始的游戏里,纸条上的数是另一个人写下的,写数的人可以故意让你难以判断,所以这本质上是一个两人博弈;1960 年代的解法都假设只能利用相对名次(或者假设数值来自已知分布),并没有回答这个博弈版本。他认为塞缪尔斯 1981 年的极小极大结果解决了这个版本中较难的一半,并给出了自己的处理。所以,「37% 法则」的数学是清楚的,但它回答的问题比加德纳最初的游戏窄。
文章也讨论了两段常被提起的前史。凯莱 1875 年在《教育时报》上提出过一个抽奖问题,并用逆向归纳求解;但那个问题按抽到的实际金额计分,弗格森认为它连秘书问题都不算。开普勒 1611 年丧妻后,在两年里考察了 11 位候选人,最终娶了第 5 位;但他曾想回头追求一位已被他放过的候选人(遭到拒绝),也就是说,他并不认为自己受「不能回头」的约束。所以「开普勒用了 37% 法则」这类说法不准确:开普勒的故事说明的恰恰是现实中的选择常常违反秘书问题的假设。
这些假设在现实中成立吗
把弗格森的六个条件放回现实,可以逐条检查。
人数已知:招聘时往往不知道还会来多少人(第二章)。随机顺序:早期与晚期的申请者可能不同,顺序与质量相关时推导不再成立。只看相对名次:现实中通常看得到分数,也大致知道分布(第二章)。不能回头:常常可以回头,但对方可能已接受别的机会;录用也可能被拒绝(第二章)。只有第一名算成功:现实中录用的是水平连续变化的人,面试也有成本(第六章)。
这些检查不是为了否定这个模型。秘书问题的价值在于把「过早停下」与「过晚停下」两种错误放在同一个可以计算的框架里,并且说明在信息很少时,先拿出一部分机会来学习是值得的。第二章逐一放宽这些条件,看结论怎样变化。
本章小结
在人数已知、随机顺序、只看相对名次、不能回头、只有第一名算成功的条件下,最优规则是阈值规则:先跳过约 人,之后录用第一个相对最佳者,成功概率趋于 ;有限 时最优跳过比例与成功概率略有不同,可以精确计算,最优点附近成功概率很平坦。约 63% 的时候规则没有选中第一名, 时有 37.5% 的情形空手而归。弗格森的考证说明,加德纳最初的游戏是一个两人博弈,至今的标准解法回答的是更窄的问题;开普勒的故事违反了「不能回头」的假设。下一章放宽这些条件。
参考文献
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).