关于「秘书问题的变体与人的停止行为」,《贝叶斯搜索与最优停止》给出的定量结论是什么?
结论:看得到分数并知道分布时,最优阈值随剩余人数变化,成功概率约为 0.58;以期望名次为目标时,最优规则的期望名次只有约 3.87,而 37% 规则下 \(n = 100\) 的期望名次约为 19.6。录用可能被拒绝时应当更早出手,可以回头时应当更晚出手;人数未知时,最佳单一阈值只跳过约 13.5%,成功概率约 0.27。实验中人们在只给名次的任务里倾向于停得太早,而在可以学习分布的重复游戏中很快接近最优。下一章从「何时停」转向「往哪里找」。
数据口径:本书是教学与研究用的数学模型,不是投资、创业、职业或人力资源建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(17 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 100, 19.6
| full information: b_k k | 1: 0.5000 k=2: 0.6899 k=5: 0.8559 k=10: 0.9240 k=100: 0.9920 |
| k (1 - b_k) at k | 1000: 0.8039 |
| n | 10: P(best) = 0.6066 (SE 0.0024) |
| n | 40: P(best) = 0.5941 (SE 0.0025) |
| n | 100: P(best) = 0.5794 (SE 0.0025) |
| minimal expected rank: n | 10: 2.5579, n=40: 3.3282, n=100: 3.6032, n=1000: 3.8324 |
| n | 100000: 3.8690 |
| expected rank, 1/e cutoff rule: n | 40: 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}
}