5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English
第二章 秘书问题的变体与人的停止行为
第一章的结论依赖一组很窄的条件。本章逐一放宽它们:看得到实际分数;目标换成期望名次;录用可能被拒绝;最后可以回头;人数事先不知道。最后讨论实验中人们实际怎样停下。
看得到分数:完全信息版本
如果每个求职者的水平是一个可以看到的分数,而且知道分数的分布(例如在 0 到 1 之间均匀分布),问题就变成了完全信息版本。这时不需要先「看行情」:第一个人的分数本身就告诉你他大概处在什么位置。
推导
设还剩 人没有面试。如果眼前这个人的分数 是迄今最高的,录用他,成功(他是全体最佳)的概率是 ;如果放过他、改为录用之后第一个超过 的人,成功概率是 。两者相等时的 就是阈值 :令 ,它满足 (Gilbert and Mosteller 1966)。规则是:遇到迄今最高、且不低于 的分数就录用。程序求出阈值,并用 40,000 次模拟估计成功概率;第二部分用逆向归纳计算只看相对名次时最小期望名次(第 1 名记为 1),并与 37% 规则下的期望名次比较。
# (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}")
# 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 人时,分数过半就录用;剩 10 人时要 0.924 以上;剩 100 人时要 0.992 以上。 趋于约 0.804,也就是说阈值大约是 。成功概率 时为 0.607, 时为 0.579(模拟标准误约 0.0025),与吉尔伯特与莫斯特勒给出的极限 0.5802 一致 (Gilbert and Mosteller 1966)。从约 0.37 提高到约 0.58,衡量的是「知道分数及其分布」这条信息的价值。
目标换成期望名次
只看相对名次时,如果目标不是「选中第一名」,而是让被录用者的期望名次尽量小(第 1 名最好),最优规则就不再是单一阈值,而是一组随时间放宽的阈值:越往后,可以接受的相对名次越宽。周元燊、森口繁一、罗宾斯与塞缪尔斯 1964 年证明,当 时,最小期望名次趋于约 3.8695 (Chow et al. 1964)。
程序的逆向归纳给出: 时最小期望名次为 2.56, 时 3.33, 时 3.60, 时 3.83, 时 3.869,逐渐逼近 3.8695。也就是说,即使有十万名求职者,只靠相对名次,平均也能录用到前四名左右的人。相比之下,37% 规则下被录用者的期望名次在 时为 8.9,在 时为 19.6(规则失败时被迫录用最后一个人),而且随 增大而变大。两种目标的最优规则差别如此之大,说明在应用秘书问题之前,首先要问的是:失败的代价是什么?第二名与第五十名是否同样糟糕?
录用可能被拒绝
现实中被录用的人可能拒绝。史密斯 1975 年研究了每次录用以概率 被接受、被拒绝后继续面试的情形 (Smith 1975)。
推导
程序的第一部分对 用逆向归纳求最优规则与成功概率,并与史密斯的极限 比较(它同时是最优的跳过比例与成功概率的极限)。第二部分是本书写的一个简化模型:如果到最后都没有录用任何人,可以回头联系迄今见过的最好的人,他仍然可用的概率为 。用阈值 时,大 下的成功概率为 ,在 处取得最大值,最大值也是 。程序用精确公式计算 的情形。第三部分是人数未知的情形:人数 在 1 到 之间均匀分布,只用单一阈值 ,如果来的人少于 个,就没有录用任何人 (Presman and Sonin 1972)。
# Relaxed secretary problems (relative ranks only).
# (a) Offers accepted with probability p, search goes on after a refusal (Smith 1975);
# backward induction; Smith's limit p^(1/(1-p)).
# (b) Book's simplified model: if nobody is chosen, the best seen so far can be recalled
# at the end, still available w.p. q; P = x ln(1/x) + q x, best at x = e^(q-1).
# (c) N uniform on 1..b (Presman & Sonin 1972); single cutoff r; too few -> nobody.
import math
def uncertain(n, p):
v, first = 0.0, n
for i in range(n, 0, -1):
if i / n >= v:
first = i
v = (1 / i) * max(p * i / n + (1 - p) * v, v) + (1 - 1 / i) * v
return v, first
def p_cut(n, r):
if r > n:
return 0.0
return 1 / n if r == 1 else (r - 1) / n * sum(1 / (i - 1) for i in range(r, n + 1))
def unknown_n(b, r):
return sum(p_cut(m, r) for m in range(1, b + 1)) / b
if __name__ == "__main__":
print("(a) n = 200: p first offer at P(best hired) limit p^(1/(1-p))")
for p in (1.0, 0.75, 0.5, 0.25):
v, f = uncertain(200, p); lim = 1 / math.e if p == 1 else p ** (1 / (1 - p))
print(f" {p:4.2f} {f:4d} ({(f - 1) / 200:.3f}) {v:.4f}"
f" {lim:.4f}")
print("(b) n = 100: q best cutoff r P(best hired) limit e^(q-1)")
for q in (0.0, 0.25, 0.5, 0.75):
pr, r = max((p_cut(100, r) + q * (r - 1) / 100, r) for r in range(1, 101))
print(f" {q:4.2f} {r:4d} {pr:.4f}"
f" {math.exp(q - 1):.4f}")
print("(c) N uniform on 1..b, single cutoff r")
for b in (40, 200):
r = max(range(1, b + 1), key=lambda k: unknown_n(b, k))
r37 = round(b / math.e) + 1
print(f" b = {b:3d}: best r = {r}, (r-1)/b = {(r - 1) / b:.3f},"
f" P = {unknown_n(b, r):.4f}; 1/e cutoff r = {r37}:"
f" P = {unknown_n(b, r37):.4f}")
print(f" limits (Presman-Sonin): (r-1)/b -> e^-2 = {math.exp(-2):.4f},"
f" P -> 2 e^-2 = {2 * math.exp(-2):.4f}")
# (a) n = 200: p first offer at P(best hired) limit p^(1/(1-p))
# 1.00 74 (0.365) 0.3695 0.3679
# 0.75 64 (0.315) 0.3177 0.3164
# 0.50 51 (0.250) 0.2509 0.2500
# 0.25 32 (0.155) 0.1580 0.1575
# (b) n = 100: q best cutoff r P(best hired) limit e^(q-1)
# 0.00 38 0.3710 0.3679
# 0.25 48 0.4750 0.4724
# 0.50 61 0.6085 0.6065
# 0.75 78 0.7799 0.7788
# (c) N uniform on 1..b, single cutoff r
# b = 40: best r = 6, (r-1)/b = 0.125, P = 0.2889; 1/e cutoff r = 16: P = 0.1895
# b = 200: best r = 28, (r-1)/b = 0.135, P = 0.2742; 1/e cutoff r = 75: P = 0.1847
# limits (Presman-Sonin): (r-1)/b -> e^-2 = 0.1353, P -> 2 e^-2 = 0.2707录用可能被拒绝时,最优规则更早开始发出录用: 时从第 51 位开始(跳过 25%),成功概率 0.251; 时从第 32 位开始(跳过 15.5%),成功概率 0.158;都与史密斯的极限 0.25 和 0.1575 接近。直觉是:每一次录用都可能落空,所以需要更多的「出手机会」,学习阶段就要缩短。
最后可以回头
杨 1974 年研究了可以回头联系已被放过的人、但对方可能拒绝的一般情形,并详细讨论了拒绝概率为常数与呈几何形式两种情况 (Yang 1974)。本书的简化模型只允许最后回头一次。它的结论与前一节相反:能回头时应当更晚开始录用。 时最优阈值为第 48 位,成功概率 0.475; 时为第 61 位、0.609; 时为第 78 位、0.780;都与极限 的 0.472、0.607、0.779 接近。道理很简单:最好的人如果被跳过了,还有机会把他找回来,所以多看一些人的代价变小了。 时问题变得平凡:看完所有人,录用最好的那个。
注
两种放宽,两个方向。 「录用可能被拒绝」使人应当更早出手,「可以回头」使人应当更晚出手。现实中两者常常同时存在(被放过的人可能还在,也可能已经接受了别的机会),所以没有一个比例能够脱离具体条件推荐给所有人。
人数事先不知道
如果人数 在 1 到 之间均匀分布,最佳的单一阈值要大幅提前: 时只跳过 5 人(12.5%),平均成功概率 0.289; 时跳过 27 人(13.5%),成功概率 0.274;普雷斯曼与索宁的极限是跳过 的 ,成功概率 (Presman and Sonin 1972)。如果误把最大可能人数 当作已知人数、照搬 37% 规则,成功概率只有 0.19 与 0.18:人很可能在学习阶段还没结束时就来完了。图一右图把三种放宽的极限画在一起。
人在实验中怎样停下
证据
停得太早。 西尔与拉波波特 1997 年在实验室中让参与者做经典的秘书问题(只给相对名次),发现参与者倾向于比最优规则更早停止搜索 (Seale and Rapoport 1997);他们用「阈值」与「连续非候选者」等简单启发式描述参与者的行为,后来的研究指出,在最优规则只有一个阈值的问题中,这两种启发式的表现都不错 (Rapoport et al. 2023)。西尔与拉波波特 2000 年又用实验研究了人数未知的版本 (Seale and Rapoport 2000)。比尔登 2006 年指出,如果报酬是被录用者的实际水平而不是「第一名或零」,最优的阈值大约在 ,远早于 ,所以实验中「停得太早」部分可能反映了人们自然地关心实际水平,但他把这作为一种推测提出 (Bearden 2006)。
证据
能学会吗。 戈尔德斯坦、麦卡菲、苏里与赖特 2020 年在网上让 6,537 名玩家玩了 48,336 局「重复的秘书问题」:每局 7 个或 15 个盒子,盒子里的数来自三种固定的分布之一,玩家可以在多局中逐渐了解分布 (Goldstein et al. 2020)。玩家一开始既有搜索过少,也有搜索过多;但他们学得很快,拟合得到的阈值在几局之后就接近最优阈值,后期的成功率接近已知分布时的最大值(7 个盒子 0.622,15 个盒子 0.599)。这与西尔和拉波波特只给相对名次的实验形成对比:在那里,参与者无法了解分布,也没有显示出学习。
这两组研究的条件不同,不能简单地放在一起比较:一个只给名次、一局一局独立,一个给数值、而且分布固定可学。第八章的试验要检验的,是在只给相对名次的经典任务中,事先学习一条停止阈值规则能否提高选中最佳者的比例。
假说 · 尚未验证
「过早停止」部分是目标不同的假说(尚未确立)。作者推测,经典任务中的过早停止至少有一部分不是「不懂规则」,而是参与者在心里用的是「选到好的就行」的目标,或者把每多看一个人当作一种成本。如果是这样,教会参与者 37% 规则能提高「选中第一名」的比例,但会降低他们在其他目标上的表现(例如空手而归的比例上升)。如果第八章的试验中,学习规则的一组选中第一名的比例没有提高,或者提高的同时空手而归的比例没有上升,这一假说即失去支持。
本章小结
看得到分数并知道分布时,最优阈值随剩余人数变化,成功概率约为 0.58;以期望名次为目标时,最优规则的期望名次只有约 3.87,而 37% 规则下 的期望名次约为 19.6。录用可能被拒绝时应当更早出手,可以回头时应当更晚出手;人数未知时,最佳单一阈值只跳过约 13.5%,成功概率约 0.27。实验中人们在只给名次的任务里倾向于停得太早,而在可以学习分布的重复游戏中很快接近最优。下一章从「何时停」转向「往哪里找」。
参考文献
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).