关于「秘书问题与 1/e:只看名次、不能回头时何时停下」,《贝叶斯搜索与最优停止》给出的定量结论是什么?

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

数据口径:本书是教学与研究用的数学模型,不是投资、创业、职业或人力资源建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序,全部核对)、原典与作者的假说。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.368, 40

n cutoff r* skipped share P(success) DP value DP stops from
53 0.400 0.4333 0.4333 3
104 0.300 0.3987 0.3987 4
115 0.364 0.3984 0.3984 5
208 0.350 0.3842 0.3842 8
4016 0.375 0.3757 0.3757 16
10038 0.370 0.3710 0.3710 38
1000369 0.368 0.3682 0.3682 369
limit: skip share and P(success) both1/e = 0.3679
n100: skip share x, exact P, approximation -x ln x
x0.10 P = 0.235 -x ln x = 0.230
x0.20 P = 0.326 -x ln x = 0.322
x0.30 P = 0.365 -x ln x = 0.361
x0.37 P = 0.371 -x ln x = 0.368
x0.50 P = 0.349 -x ln x = 0.347
x0.60 P = 0.309 -x ln x = 0.306
simulation, n100, r = 38, 20,000 runs: 0.3731
nobody chosen (best among the skipped), n40, r = 16: 0.375

核心公式

\[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,\]
查看完整验算程序
# 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}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数》第 1 章「秘书问题与 1/e:只看名次、不能回头时何时停下」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102

DOI: 10.5281/zenodo.23810102 · 阅读本章所在专著 · 5DL-B-042 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026042,
  author    = {Fan, Yafu},
  title     = {Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.23810102},
  url       = {https://doi.org/10.5281/zenodo.23810102}
}

本书其他章节结论