关于「秘书问题的变体与人的停止行为」,《贝叶斯搜索与最优停止》给出的定量结论是什么?

结论:看得到分数并知道分布时,最优阈值随剩余人数变化,成功概率约为 0.58;以期望名次为目标时,最优规则的期望名次只有约 3.87,而 37% 规则下 \(n = 100\) 的期望名次约为 19.6。录用可能被拒绝时应当更早出手,可以回头时应当更晚出手;人数未知时,最佳单一阈值只跳过约 13.5%,成功概率约 0.27。实验中人们在只给名次的任务里倾向于停得太早,而在可以学习分布的重复游戏中很快接近最优。下一章从「何时停」转向「往哪里找」。

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

English version

对照数据表

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

full information: b_k k1: 0.5000 k=2: 0.6899 k=5: 0.8559 k=10: 0.9240 k=100: 0.9920
k (1 - b_k) at k1000: 0.8039
n10: P(best) = 0.6066 (SE 0.0024)
n40: P(best) = 0.5941 (SE 0.0025)
n100: P(best) = 0.5794 (SE 0.0025)
minimal expected rank: n10: 2.5579, n=40: 3.3282, n=100: 3.6032, n=1000: 3.8324
n100000: 3.8690
expected rank, 1/e cutoff rule: n40: 8.9, n=100: 19.6
查看完整验算程序
# (1) Full information (Gilbert & Mosteller): values U(0, 1) are seen; with k to come,
#     take a best-so-far x iff x >= b_k, z = (1 - b_k)/b_k solving sum C(k,j) z^j/j = 1.
# (2) Minimal expected rank with relative ranks only (Chow et al.): backward induction.
import math, random

def threshold(k):
    lo, hi = 0.0, 1.0
    for _ in range(60):
        z, s, t = (lo + hi) / 2, 0.0, 1.0
        for j in range(1, k + 1):
            t *= (k - j + 1) / j * z; s += t / j          # t = C(k, j) z^j
        lo, hi = (lo, z) if s > 1 else (z, hi)
    return 1 / (1 + lo)

def full_info_sim(n, runs, rng):
    b, wins = [0.0] + [threshold(k) for k in range(1, n)], 0
    for _ in range(runs):
        xs, best = [rng.random() for _ in range(n)], -1.0
        for i, x in enumerate(xs):
            if x > best:
                best = x
                if x >= b[n - 1 - i]:
                    wins += x == max(xs); break
    return wins / runs

def expected_rank(n):       # stop at i, relative rank r: expected rank r (n+1)/(i+1)
    v = (n + 1) / 2
    for i in range(n - 1, 0, -1):
        c = (n + 1) / (i + 1); m = min(i, int(v / c))      # accept relative ranks <= m
        v = (c * m * (m + 1) / 2 + (i - m) * v) / i
    return v

def classical_rank(n, r, runs, rng):          # 1/e cutoff rule; last one if nobody
    tot = 0
    for _ in range(runs):
        o = list(range(1, n + 1)); rng.shuffle(o); bar = min(o[:r - 1])
        tot += next((x for x in o[r - 1:] if x < bar), o[-1])
    return tot / runs

if __name__ == "__main__":
    rng = random.Random(1966)
    print("full information: b_k " + "  ".join(f"k={k}: {threshold(k):.4f}"
                                              for k in (1, 2, 5, 10, 100))
          + f"\n   k (1 - b_k) at k = 1000: {1000 * (1 - threshold(1000)):.4f}")
    for n in (10, 40, 100):
        p = full_info_sim(n, 40000, rng)
        se = math.sqrt(p * (1 - p) / 40000)
        print(f"   n = {n:3d}: P(best) = {p:.4f} (SE {se:.4f})")
    print("minimal expected rank: " + ", ".join(f"n={n}: {expected_rank(n):.4f}"
                                                for n in (10, 40, 100, 1000)))
    print(f"   n=100000: {expected_rank(100000):.4f}")
    cr = [classical_rank(n, r, 20000, rng) for n, r in ((40, 16), (100, 38))]
    print(f"expected rank, 1/e cutoff rule: n=40: {cr[0]:.1f}, n=100: {cr[1]:.1f}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数》第 2 章「秘书问题的变体与人的停止行为」(版本 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}
}

本书其他章节结论