秘书问题
题
\(n\) 个候选人按随机顺序逐个面试。每面完一个只知道他在已面过的人里排第几，必须当场决定录用或拒绝，拒绝不能反悔。目标是录到全场最好的那一个。什么策略成功率最高？
一句话
先只看不选前 \(r-1 \approx n/e\) 个（约 37%），之后录用第一个比前面所有人都好的——成功率趋于 \(1/e \approx 0.368\)，不随 \(n\) 变大而归零。
关键技巧
两步。
一、最优策略一定是门槛型。 只有"当前是目前为止最好的"（相对第一）才可能是全场最好，其他人录了必输。而第 \(i\) 个人若是相对第一，他是全场最好的概率是 \(i/n\)——越往后越大。所以最优规则是：过了某个位置 \(r\) 之后，见相对第一就录。
二、按全场最好者的位置拆概率。 设全场最好者在位置 \(i\)（概率 \(1/n\)）。\(i < r\) 时他被跳过，输。\(i \ge r\) 时，策略录到他当且仅当位置 \(r..i-1\) 之间没人先被录——即前 \(i-1\) 个人里的最好者落在观察期 \(1..r-1\) 内，概率 \(\frac{r-1}{i-1}\)。于是
令 \(x = r/n\)，和式变积分 \(\sum \frac{1}{i-1} \approx \ln \frac{n}{r}\)：
门槛位置和成功率是同一个数 \(1/e\)——这是 \(-x\ln x\) 的巧合，不是必然。
解
有限 \(n\) 的最优观察期长度 \(r-1\) 与成功率（精确值，由上式逐个 \(r\) 求最大）：
| \(n\) | 3 | 4 | 5 | 10 | 20 | 50 | 100 | 1000 |
|---|---|---|---|---|---|---|---|---|
| 只看不选 \(r-1\) | 1 | 1 | 2 | 3 | 7 | 18 | 37 | 368 |
| 成功率 | 0.5 | 0.4583 | 0.4333 | 0.3987 | 0.3842 | 0.3743 | 0.3710 | 0.3682 |
\(n = 100\)：跳过前 37 个，成功率 37.1%。成功率从上方单调逼近 \(1/e\)，\(r-1\) 始终紧贴 \(n/e\)（\(100/e = 36.8\)，\(1000/e = 367.9\)）。
延伸
- 常见错误：以为观察期越长越稳。观察期拉长，最好者落在观察期里被白白跳过的概率 \(x\) 也线性增大；\(-x\ln x\) 两头都是 0，中间才有峰。
-
最小化期望名次（Chow–Moriguti–Robbins–Samuels 1964）：不求必中第一，只求录到的人平均排名尽量靠前。最优策略不再是单一门槛，而是随位置放宽的一串门槛；倒推 DP 算得 \(n=10, 100, 1000\) 时期望名次为 2.558、3.603、3.832，极限
\[ \prod_{k=1}^{\infty} \left(\frac{k+2}{k}\right)^{1/(k+1)} \approx 3.8695 \]候选人再多，平均也能录到前 4 名——和"成功率 37%"对照，目标函数一换，结论从"赌运气"变成"稳拿高分"。 - 未知 \(n\)：把"位置"换成"时间"。候选人在 \([0,1]\) 上均匀随机时刻到达，人数任意未知，规则改成"\(1/e\) 时刻之前只看"——对任何人数，成功率都不低于 \(1/e\)（Bruss 的 1/e 定律）。只来 1 个人时成功率 \(1 - 1/e \approx 0.632\)。 - 可以录任意多个前 \(k\) 名 / 允许反悔 / 知道真实分数：都是不同的问题。知道分数（例如分数来自已知分布的 i.i.d.）时就退回骰子重掷那种"跟继续价值比"的门槛，成功率明显高于 \(1/e\)——多出来的就是分数里的信息。 - 同款骨架：Bruss 的 odds theorem 把门槛规则推广到任意独立事件序列——从后往前累加 \(p_i/(1-p_i)\)，累到 1 的位置就是门槛。
数值验证
from fractions import Fraction as F
import math, random
def success(n, r):
"""前 r-1 个只看不选，从第 r 个起选第一个超过前面所有人的。"""
if r == 1:
return F(1, n)
return F(r - 1, n) * sum(F(1, i - 1) for i in range(r, n + 1))
for n in [3, 4, 5, 10, 20, 50, 100, 1000]:
r = max(range(1, n + 1), key=lambda r: success(n, r))
print(n, r - 1, round(float(success(n, r)), 4))
# 3 1 0.5 / 4 1 0.4583 / 5 2 0.4333 / 10 3 0.3987 / 20 7 0.3842
# 50 18 0.3743 / 100 37 0.371 / 1000 368 0.3682
def chow(n):
"""最小化期望名次：看到第 i 人、相对名次 j 时停下的期望绝对名次 = j(n+1)/(i+1)。"""
V = F(n + 1, 2) # 最后一人必须收
for i in range(n - 1, 0, -1):
V = sum(min(F(j * (n + 1), i + 1), V) for j in range(1, i + 1)) / i
return V
print([round(float(chow(n)), 4) for n in (10, 100, 1000)]) # [2.5579, 3.6032, 3.8324]
lim = math.prod(((k + 2) / k) ** (1 / (k + 1)) for k in range(1, 200000))
print(round(lim, 4)) # 3.8695
random.seed(3)
n, r, T, win = 100, 38, 200000, 0
for _ in range(T):
a = list(range(n)); random.shuffle(a)
m = max(a[:r - 1])
pick = next((x for x in a[r - 1:] if x > m), a[-1])
win += pick == n - 1
print(win / T) # 0.37146
# 未知 n：候选人在 [0,1] 上均匀随机时刻到达，1/e 时刻之前只看
def bruss(N, T=200000):
w = 0
for _ in range(T):
arr = sorted((random.random(), v) for v in random.sample(range(N), N))
m = max((v for t, v in arr if t < 1 / math.e), default=-1)
pick = next((v for t, v in arr if t >= 1 / math.e and v > m), None)
w += pick == N - 1
return w / T
print([bruss(N) for N in (1, 2, 5, 50)])
# [0.63215, 0.431105, 0.370215, 0.36753] N=50 与 1/e 的差在噪声内（sd≈0.001）