---
description: "先只看前 $n/e$ 个、之后选第一个破纪录的，成功率趋于 $1/e$；按最优者的位置拆概率，和式化积分 $-x\\ln x$"
---

# 秘书问题

## 题

$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}$。于是

$$
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}
$$

令 $x = r/n$，和式变积分 $\sum \frac{1}{i-1} \approx \ln \frac{n}{r}$：

$$
P \approx -x \ln x, \qquad \frac{d}{dx}(-x\ln x) = -\ln x - 1 = 0 \ \Rightarrow\ x = \frac{1}{e},\ \ P = \frac{1}{e}
$$

**门槛位置和成功率是同一个数 $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.）时就退回[骰子重掷](dice-reroll.md)那种"跟继续价值比"的门槛，成功率明显高于 $1/e$——多出来的就是分数里的信息。
- **同款骨架**：Bruss 的 odds theorem 把门槛规则推广到任意独立事件序列——从后往前累加 $p_i/(1-p_i)$，累到 1 的位置就是门槛。

??? note "数值验证"

    ```python
    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）
    ```