5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English

第一章 秘书问题与 1/e:只看名次、不能回头时何时停下

一个游戏与它的六个条件

加德纳 1960 年介绍的「古戈尔游戏」后来被改写成更容易讲的故事:一个职位有 nn 名求职者,他们以随机的顺序一个一个来面试;面试官每见一个人,只能判断此人比之前见过的人好还是差,看不到绝对分数;每见完一个人必须当场决定录用或拒绝,拒绝了就不能再回头;只有录用到全部 nn 人中最好的那一个才算成功。弗格森把这个问题的「最简形式」归纳为六条:只有一个职位;求职者人数 nn 已知;求职者以随机顺序依次面试,每种顺序的可能性相同;可以把所有求职者从好到差排序(没有并列),但是否录用只能依据已面试者之间的相对名次;被拒绝的人不能再被召回;只对最好的那一个满意,即选中全体最佳者得 1、否则得 0 (Ferguson 1989)。最后一条是目标:第二名与最后一名同样算失败。

这几条都很重要。第二章与第六章会看到,改动其中任何一条,最优的做法都会明显不同。

阈值规则的精确成功概率

在这些条件下,一个很自然的规则是阈值规则:先拒绝前 r−1r-1 个人,只用来「了解行情」;从第 rr 个人开始,录用第一个比之前所有人都好的人(称为「相对最佳者」);如果到最后都没有出现,就没有录用任何人(或者只能录用最后一个人,这对「选中第一名」的概率没有影响)。

推导

设全体最好的人在第 ii 位(概率 1/n1/n)。如果 i<ri < r,他被拒绝了,规则失败。如果 i≥ri \ge r,规则选中他的条件是:第 rr 位到第 i−1i-1 位之间没有出现相对最佳者,也就是前 i−1i-1 人中最好的那个落在前 r−1r-1 位,概率为 (r−1)/(i−1)(r-1)/(i-1)。所以 P(r)=∑i=rn1n⋅r−1i−1=r−1n∑i=rn1i−1,r≥2,P(r) = \sum_{i=r}^{n} \frac{1}{n}\cdot\frac{r-1}{i-1} = \frac{r-1}{n}\sum_{i=r}^{n}\frac{1}{i-1}, \qquad r \ge 2, 而 P(1)=1/nP(1) = 1/n(录用第一个人)。令 x=(r−1)/nx = (r-1)/n,当 nn 很大时求和近似为 ln⁡(n/(r−1))\ln(n/(r-1)),于是 P≈−xln⁡xP \approx -x\ln x;对 xx 求导,−ln⁡x−1=0-\ln x – 1 = 0,得 x=1/ex = 1/e,最大值也是 1/e≈0.36791/e \approx 0.3679。

为什么最好的规则一定是阈值规则?可以用逆向归纳(动态规划)验证。第 ii 个人是相对最佳者的概率是 1/i1/i;如果他是相对最佳者,他也是全体最佳者的概率是 i/ni/n,随 ii 增大;而「放过他、继续用最优方式往下走」的成功概率 ViV_i 随 ii 减小。所以一旦在某一位停下比继续好,之后每一位也都是停下更好:最优规则必然是「从某一位开始,遇到相对最佳者就停」。这类问题称为单调停止问题,只看下一步的「一步前瞻」规则就是最优的;邓金 1963 年把秘书问题写成马尔可夫过程的停时问题,证明了这一点 (Dynkin 1963)。

推导

程序对不同的 nn 用精确公式找出最好的阈值 r*r^*,并用逆向归纳独立地算出最优成功概率与「从第几位开始停」,两者应当一致;然后列出 n=100n = 100 时成功概率随跳过比例的变化,与极限近似 −xln⁡x-x\ln x 比较;最后用 20,000 次模拟检验 n=100n = 100、r=38r = 38 时的公式。

# 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

结果有四点值得注意。第一,精确公式与逆向归纳给出的成功概率和停止位置完全一致,最优规则确实是阈值规则。第二,有限 nn 时最优跳过的比例并不正好是 37%:n=10n = 10 时跳过 3 人(30%),n=20n = 20 时 35%,n=40n = 40 时 37.5%,n=1000n = 1000 时 36.8%;成功概率从 n=5n = 5 时的 0.433 逐渐降到极限 0.368,始终略高于 1/e1/e。n=100n = 100 的模拟结果 0.3731 与精确值 0.3710 的差别在一个标准误(约 0.0034)之内。第三,n=11n = 11 时最优规则是录用第一个出现在第 5 位及以后的相对最佳者;弗格森注意到,开普勒在 11 位候选人中最终选的恰好也是第 5 位,但这只是数字上的相合,下文会说明开普勒并不符合这个问题的条件。

第四,也是最实用的一点:成功概率在最优点附近很平坦。n=100n = 100 时,跳过 30% 的成功概率为 0.365,跳过 50% 为 0.349,都与最优的 0.371 相差不多;真正有害的是跳过得太少(10% 时只有 0.235)或太多(60% 时 0.309)。所以「37%」更像一个区间的中心,而不是需要精确遵守的数字。

左:秘书问题中阈值规则的成功概率与跳过比例的关系(n = 10、40、100,以及极限 -x\ln x;虚线为 1/e)。曲线在最优点附近很平坦。右:第二章讨论的三种放宽条件下的极限成功概率:最后可以回头、回头时对方仍可录用的概率为 q(e^{q-1});录用被接受的概率为 p(史密斯 1975:p^{1/(1-p)});人数在 1 到 b 之间均匀分布(2e^{-2})。

规则也会失败

最优规则的成功概率约为 37%,意味着约 63% 的时候它没有选中第一名。失败有两种。一种是最好的人恰好在被跳过的前 r−1r-1 人里,之后不会再出现相对最佳者,结果一个人也没录用(或被迫录用最后一个人):这种情形的概率是 (r−1)/n(r-1)/n,n=40n = 40、r=16r = 16 时为 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% 法则」这类说法不准确:开普勒的故事说明的恰恰是现实中的选择常常违反秘书问题的假设。

这些假设在现实中成立吗

把弗格森的六个条件放回现实,可以逐条检查。

人数已知:招聘时往往不知道还会来多少人(第二章)。随机顺序:早期与晚期的申请者可能不同,顺序与质量相关时推导不再成立。只看相对名次:现实中通常看得到分数,也大致知道分布(第二章)。不能回头:常常可以回头,但对方可能已接受别的机会;录用也可能被拒绝(第二章)。只有第一名算成功:现实中录用的是水平连续变化的人,面试也有成本(第六章)。

这些检查不是为了否定这个模型。秘书问题的价值在于把「过早停下」与「过晚停下」两种错误放在同一个可以计算的框架里,并且说明在信息很少时,先拿出一部分机会来学习是值得的。第二章逐一放宽这些条件,看结论怎样变化。

本章小结

在人数已知、随机顺序、只看相对名次、不能回头、只有第一名算成功的条件下,最优规则是阈值规则:先跳过约 n/en/e 人,之后录用第一个相对最佳者,成功概率趋于 1/e≈0.3681/e \approx 0.368;有限 nn 时最优跳过比例与成功概率略有不同,可以精确计算,最优点附近成功概率很平坦。约 63% 的时候规则没有选中第一名,n=40n = 40 时有 37.5% 的情形空手而归。弗格森的考证说明,加德纳最初的游戏是一个两人博弈,至今的标准解法回答的是更窄的问题;开普勒的故事违反了「不能回头」的假设。下一章放宽这些条件。

参考文献

Chow, Y. S., S. Moriguti, H. Robbins, and S. M. Samuels. 1964. “Optimal Selection Based on Relative Rank (the ‘Secretary Problem’).” Israel Journal of Mathematics 2: 81–90. https://doi.org/10.1007/BF02759948.
Dynkin, Eugene B. 1963. “The Optimum Choice of the Instant for Stopping a Markov Process.” Soviet Mathematics Doklady 4: 627–29.
Ferguson, Thomas S. 1989. “Who Solved the Secretary Problem?” Statistical Science 4 (3): 282–89. https://doi.org/10.1214/ss/1177012493.
Gardner, Martin. 1960. “Mathematical Games.” Scientific American 202 (2).
Gilbert, John P., and Frederick Mosteller. 1966. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (313): 35–73.
Lindley, Dennis V. 1961. “Dynamic Programming and Decision Theory.” Applied Statistics 10 (1): 39–51.

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