5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文
Chapter 2 Variants of the Secretary Problem and How People Stop
The conclusions of Chapter 1 rest on a narrow set of conditions. This chapter relaxes them one at a time: actual scores are visible; the objective becomes the expected rank; offers may be refused; one recall is allowed at the end; the number of applicants is unknown in advance. It closes with how people actually stop in experiments.
Seeing the scores: the full-information version
If each applicant’s quality is a visible score and the distribution of scores is known (say, uniform between 0 and 1), the problem becomes the full-information version. There is then no need to “learn the market” first: the first applicant’s score already says roughly where that applicant stands.
Calculation
Suppose applicants remain to be interviewed. If the present applicant’s score is the highest so far, hiring now succeeds (the applicant is the overall best) with probability ; passing and instead hiring the first later applicant who beats succeeds with probability . The at which the two are equal is the threshold : with , it satisfies (Gilbert and Mosteller 1966). The rule is: hire on a score that is the highest so far and at least . The program finds the thresholds and estimates the success probability from 40,000 simulated runs; its second part uses backward induction to compute the minimal expected rank (best = 1) with relative ranks only, and compares it with the expected rank under the 37 % rule.
# (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.6The threshold rises with the number of applicants still to come: with 1 left, hire on any score above one half; with 10 left, only above 0.924; with 100 left, only above 0.992. tends to about 0.804, so the threshold is roughly . The success probability is 0.607 for and 0.579 for (simulation standard error about 0.0025), consistent with the limit of 0.5802 given by Gilbert and Mosteller (Gilbert and Mosteller 1966). The rise from about 0.37 to about 0.58 measures the value of one piece of information: knowing the scores and their distribution.
Expected rank as the objective
With relative ranks only, if the objective is not “choose the best” but to make the expected rank of the person hired as small as possible (rank 1 is best), the optimal rule is no longer a single threshold but a series of thresholds that relax over time: the later it is, the wider the range of acceptable relative ranks. Chow, Moriguti, Robbins and Samuels proved in 1964 that as the minimal expected rank tends to about 3.8695 (Chow et al. 1964).
The program’s backward induction gives a minimal expected rank of 2.56 for , 3.33 for , 3.60 for , 3.83 for and 3.869 for , approaching 3.8695. Even with a hundred thousand applicants and only relative ranks to go on, one can on average hire someone around the top four. Under the 37 % rule, by contrast, the expected rank of the person hired is 8.9 for and 19.6 for (with the last applicant hired when the rule fails), and it grows with . The optimal rules for the two objectives differ so much that, before applying the secretary problem, the first question to ask is: what does failure cost? Is the second best as bad as the fiftieth?
Offers that may be refused
In reality, the person offered the job may decline. In 1975 Smith studied the case in which each offer is accepted with probability and the search continues after a refusal (Smith 1975).
Calculation
The first part of the program uses backward induction for to find the optimal rule and its success probability, and compares them with Smith’s limit (which is the limit of both the optimal share skipped and the success probability). The second part is a simplified model written for this book: if nobody has been hired when the list runs out, the best applicant seen so far can be called back and is still available with probability . With threshold the success probability for large is , maximised at , where the maximum is also . The program computes the case from the exact formula. The third part is the case of an unknown number of applicants: the number is uniform between 1 and , a single threshold is used, and if fewer than applicants arrive nobody is hired (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.2707When offers may be refused, the optimal rule starts making offers earlier: with from position 51 (skipping 25 %), with success probability 0.251; with from position 32 (skipping 15.5 %), with success probability 0.158 — both close to Smith’s limits of 0.25 and 0.1575. The intuition is that any offer may come to nothing, so more chances to act are needed and the learning phase must be shorter.
One recall at the end
Yang in 1974 studied the general case in which applicants who were passed over can be approached again but may refuse, and examined in detail the cases of a constant and of a geometric refusal probability (Yang 1974). The book’s simplified model allows only one recall at the end. Its conclusion runs opposite to that of the previous section: when recall is possible, one should start hiring later. With the optimal threshold is position 48 and the success probability 0.475; with , position 61 and 0.609; with , position 78 and 0.780 — all close to the limit (0.472, 0.607 and 0.779). The reason is simple: if the best applicant has been skipped there is still a chance to get that person back, so looking at more applicants costs less. With the problem becomes trivial: see everyone and hire the best.
Note
Two relaxations, two directions. “Offers may be refused” means one should act earlier; “recall is possible” means one should act later. In reality both are often present at once (the person passed over may still be available, or may have accepted another offer), so no single percentage can be recommended to everyone regardless of the conditions.
An unknown number of applicants
If the number is uniform between 1 and , the best single threshold comes much earlier: for it skips only 5 applicants (12.5 %), with average success probability 0.289; for it skips 27 (13.5 %), with success probability 0.274. Presman and Sonin’s limits are a skip of of and a success probability of (Presman and Sonin 1972). Treating the largest possible number as if it were the known number and applying the 37 % rule gives a success probability of only 0.19 and 0.18: applicants may well stop arriving before the learning phase is over. The right panel of Figure 1 shows the limits for the three relaxations together.
How people stop in experiments
Evidence
Stopping too early. Seale and Rapoport in 1997 had participants in the laboratory play the classical secretary problem (relative ranks only) and found that they tended to stop searching earlier than the optimal rule prescribes (Seale and Rapoport 1997). They described participants’ behaviour with simple heuristics such as a “cutoff” rule and a “successive non-candidate” rule; later work points out that in problems whose optimal rule has a single threshold, both heuristics perform well (Rapoport et al. 2023). In 2000 Seale and Rapoport went on to study experimentally the version with an unknown number of applicants (Seale and Rapoport 2000). Bearden noted in 2006 that if the payoff is the actual quality of the person hired rather than “the best or nothing”, the optimal threshold lies near , far earlier than , so that “stopping too early” in experiments may partly reflect a natural concern with actual quality — a suggestion he offered as a conjecture (Bearden 2006).
Evidence
Can it be learned? Goldstein, McAfee, Suri and Wright in 2020 had 6,537 players play 48,336 games of a “repeated secretary problem” online: each game had 7 or 15 boxes whose numbers came from one of three fixed distributions, so that players could gradually learn the distribution over many games (Goldstein et al. 2020). At first players both searched too little and searched too much; but they learned quickly, the fitted thresholds came close to the optimal thresholds after a few games, and later win rates approached the maxima attainable with a known distribution (0.622 with 7 boxes and 0.599 with 15). This contrasts with the experiment of Seale and Rapoport, which gave only relative ranks: there participants could not learn the distribution and showed no learning.
The two lines of research used different conditions and cannot simply be set side by side: one gave only ranks, with each game independent, while the other gave values from a fixed distribution that could be learned. The trial in Chapter 8 tests whether, in the classical task with relative ranks only, learning a stopping-threshold rule in advance raises the share of games in which the best option is chosen.
Hypothesis · not established
The hypothesis that “stopping early” partly reflects a different objective (not yet established). The author conjectures that at least part of the early stopping in the classical task is not a failure to understand the rule but reflects an objective such as “a good one will do”, or the treatment of each extra applicant as a cost. If so, teaching participants the 37 % rule will raise their share of “best chosen” but lower their performance on other objectives (for example, the share of games ending with nobody chosen will rise). If in the Chapter 8 trial the group that learns the rule does not choose the best more often, or does so without any rise in the share of games ending with nobody chosen, the hypothesis loses support.
Summary
When scores are visible and their distribution is known, the optimal threshold changes with the number of applicants remaining and the success probability is about 0.58. With expected rank as the objective, the optimal rule achieves an expected rank of only about 3.87, whereas under the 37 % rule the expected rank for is about 19.6. When offers may be refused, one should act earlier; when recall is possible, later. When the number of applicants is unknown, the best single threshold skips only about 13.5 %, with success probability about 0.27. In experiments, people tend to stop too early in tasks that give only ranks, but quickly approach the optimum in repeated games in which the distribution can be learned. The next chapter turns from “when to stop” to “where to look”.
References
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).