关于「秘书问题与 1/e:只看名次、不能回头时何时停下」,《贝叶斯搜索与最优停止》给出的定量结论是什么?
结论:在人数已知、随机顺序、只看相对名次、不能回头、只有第一名算成功的条件下,最优规则是阈值规则:先跳过约 \(n/e\) 人,之后录用第一个相对最佳者,成功概率趋于 \(1/e \approx 0.368\);有限 \(n\) 时最优跳过比例与成功概率略有不同,可以精确计算,最优点附近成功概率很平坦。约 63% 的时候规则没有选中第一名,\(n = 40\) 时有 37.5% 的情形空手而归。弗格森的考证说明,加德纳最初的游戏是一个两人博弈,至今的标准解法回答的是更窄的问题;开普勒的故事违反了「不能回头」的假设。下一章放宽这些条件。
数据口径:本书是教学与研究用的数学模型,不是投资、创业、职业或人力资源建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.368, 40
| 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 |
核心公式
\[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}
}