5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文
Chapter 1 The Secretary Problem and 1/e: When to Stop If You See Only Ranks and Cannot Go Back
A game and its six conditions
Gardner’s 1960 “game of googol” was later retold as an easier story. A job has applicants who come for interview one at a time in random order. After each interview the interviewer can tell only whether this applicant is better or worse than those already seen, not an absolute score; each applicant must be hired or rejected on the spot, and a rejected applicant cannot be called back; success means hiring the best of all . Ferguson summarised the “simplest form” of the problem in six conditions: there is one position; the number of applicants is known; the applicants are interviewed sequentially in random order, each order being equally likely; all applicants can be ranked from best to worst without ties, but the decision must be based only on the relative ranks of those interviewed so far; an applicant once rejected cannot later be recalled; and you are satisfied with nothing but the very best, so the payoff is 1 for choosing the best of all and 0 otherwise (Ferguson 1989). The last condition is the objective: the second best fails just as badly as the worst.
Each of these conditions matters. Chapters 2 and 6 show that changing any one of them changes the best course of action markedly.
The exact success probability of a cutoff rule
Under these conditions a natural rule is a cutoff rule: reject the first applicants, using them only to “learn the market”; from applicant onwards, hire the first one who is better than everyone before (a “relative best”); if none appears, hire nobody (or be forced to hire the last applicant, which does not change the probability of choosing the best).
Calculation
Suppose the overall best applicant is in position (probability ). If , that applicant was rejected and the rule fails. If , the rule chooses that applicant if and only if no relative best appears in positions to , that is, if the best of the first lies in the first positions, which has probability . Hence and (hire the first applicant). With and large, the sum is approximately , so ; setting the derivative to zero gives , and the maximum is also .
Why must the best rule be a cutoff rule? Backward induction (dynamic programming) confirms it. Applicant is a relative best with probability ; if so, the probability that this applicant is also the overall best is , which increases with , while , the probability of success from passing this applicant and then continuing optimally, decreases with . So once stopping is better than continuing at some position, it is better at every later position too: the optimal rule must be “from some position onwards, stop at the first relative best”. Problems of this kind are called monotone stopping problems, for which the one-stage look-ahead rule is optimal; Dynkin showed this for the secretary problem in 1963 by treating it as a stopping problem for a Markov process (Dynkin 1963).
Calculation
For several values of the program finds the best cutoff from the exact formula and, independently, computes the optimal success probability and the position from which to stop by backward induction; the two should agree. It then lists, for , how the success probability varies with the share skipped, beside the limiting approximation , and finally checks the formula for , by 20,000 simulated runs.
# Classical secretary problem: cutoff rule r (skip r - 1, then take the first relative
# best). Exact P(r) = (r-1)/n * sum_{i=r}^{n} 1/(i-1); backward induction as a check.
import math, random
def p_cutoff(n, r):
return 1 / n if r == 1 else (r - 1) / n * sum(1 / (i - 1) for i in range(r, n + 1))
def dp(n): # v: success probability after passing applicant i
v, stop_from = 0.0, n
for i in range(n, 0, -1): # i is a relative best w.p. 1/i, then overall best w.p. i/n
if i / n >= v:
stop_from = i
v = (1 / i) * max(i / n, v) + (1 - 1 / i) * v
return v, stop_from
def simulate(n, r, runs, rng):
wins = 0
for _ in range(runs):
order = list(range(n)); rng.shuffle(order) # 0 = the best applicant
bar = min(order[:r - 1])
wins += next((x for x in order[r - 1:] if x < bar), None) == 0
return wins / runs
if __name__ == "__main__":
print(" n cutoff r* skipped share P(success) DP value DP stops from")
for n in (5, 10, 11, 20, 40, 100, 1000):
r = max(range(1, n + 1), key=lambda r: p_cutoff(n, r)); v, s = dp(n)
print(f"{n:5d} {r:6d} {(r - 1) / n:6.3f} {p_cutoff(n, r):.4f}"
f" {v:.4f} {s:5d}")
print(f"limit: skip share and P(success) both -> 1/e = {1 / math.e:.4f}")
print("n = 100: skip share x, exact P, approximation -x ln x")
for x in (0.10, 0.20, 0.30, 0.37, 0.50, 0.60):
print(f" x = {x:.2f} P = {p_cutoff(100, round(100 * x) + 1):.3f}"
f" -x ln x = {-x * math.log(x):.3f}")
sim = simulate(100, 38, 20000, random.Random(1960))
print(f"simulation, n = 100, r = 38, 20,000 runs: {sim:.4f}")
print(f"nobody chosen (best among the skipped), n = 40, r = 16: {15 / 40:.3f}")
# n cutoff r* skipped share P(success) DP value DP stops from
# 5 3 0.400 0.4333 0.4333 3
# 10 4 0.300 0.3987 0.3987 4
# 11 5 0.364 0.3984 0.3984 5
# 20 8 0.350 0.3842 0.3842 8
# 40 16 0.375 0.3757 0.3757 16
# 100 38 0.370 0.3710 0.3710 38
# 1000 369 0.368 0.3682 0.3682 369
# limit: skip share and P(success) both -> 1/e = 0.3679
# n = 100: skip share x, exact P, approximation -x ln x
# x = 0.10 P = 0.235 -x ln x = 0.230
# x = 0.20 P = 0.326 -x ln x = 0.322
# x = 0.30 P = 0.365 -x ln x = 0.361
# x = 0.37 P = 0.371 -x ln x = 0.368
# x = 0.50 P = 0.349 -x ln x = 0.347
# x = 0.60 P = 0.309 -x ln x = 0.306
# simulation, n = 100, r = 38, 20,000 runs: 0.3731
# nobody chosen (best among the skipped), n = 40, r = 16: 0.375Four points stand out. First, the exact formula and backward induction give identical success probabilities and stopping positions: the optimal rule is indeed a cutoff rule. Second, for finite the optimal share skipped is not exactly 37 %: it is 3 of 10 (30 %) for , 35 % for , 37.5 % for and 36.8 % for ; the success probability falls from 0.433 for towards the limit 0.368 and stays slightly above throughout. The simulated 0.3731 for differs from the exact 0.3710 by less than one standard error (about 0.0034). Third, for the optimal rule hires the first relative best in position 5 or later; Ferguson notes that Kepler, among eleven candidates, eventually chose the fifth as well. The match is only numerical: as explained below, Kepler’s situation did not meet the conditions of the problem.
Fourth, and most useful in practice: the success probability is flat near the optimum. For , skipping 30 % succeeds with probability 0.365 and skipping 50 % with 0.349, both close to the optimal 0.371; what really hurts is skipping too few (0.235 at 10 %) or too many (0.309 at 60 %). “37 %” is therefore better seen as the centre of a range than as a number to be followed exactly.
The rule also fails
An optimal success probability of about 37 % means that about 63 % of the time the rule does not choose the best. It fails in two ways. In one, the best applicant was among the first who were skipped, no relative best appears afterwards, and nobody is hired (or the last applicant is hired by default); this happens with probability , which is 37.5 % for and . In the other, the rule hires a relative best while someone better is still to come. Under “the best or nothing” scoring the two failures are equivalent; in any real choice, hiring the second best and hiring nobody are very different outcomes. Chapter 2 shows that with a different objective, such as minimising the expected rank of the person hired, the optimal rule is quite different.
Note
“Optimal” is relative to an objective. The 37 % rule maximises the probability of choosing the very best. It does not care how good the person chosen is, nor whether one ends up with nobody. If the objective is the expected quality of the hire, or if interviews themselves are costly, the optimal share to skip is much smaller (Chapters 2 and 6). Treating the rule as general life advice tacitly adopts an objective that few people actually hold.
Who solved the secretary problem?
Evidence
Ferguson’s history. In “Who solved the secretary problem?”, published in Statistical Science in 1989, Ferguson traced the origins of the problem (Ferguson 1989). He dates its first appearance in print to Gardner’s column of February 1960, where it was called the “game of googol” and attributed to Fox and Marnie, with a solution published the following month (Gardner 1960). The first solution in a scholarly journal was Lindley’s 1961 paper, which used dynamic programming (Lindley 1961); Dynkin in 1963 treated it as an optimal stopping problem for a Markov process (Dynkin 1963); Gilbert and Mosteller in 1966 gave many elegant derivations and extensions, including the full-information version (Gilbert and Mosteller 1966); and the asymptotic solution for minimising the expected rank was given by Chow, Moriguti, Robbins and Samuels in 1964 (Chow et al. 1964).
The answer to the paper’s title is “nobody”. Ferguson’s reason is that in Gardner’s original game the numbers on the slips are written by another person, who can choose them to make your task hard, so that the game is in essence a two-person game; the solutions of the 1960s all assume that only relative ranks can be used (or that the numbers come from a known distribution), and so do not answer the game version. He credits Samuels’s minimax result of 1981 with solving the harder half of that version and gives his own treatment. The mathematics of the “37 % rule” is clear, but the question it answers is narrower than Gardner’s original game.
The paper also discusses two pieces of prehistory that are often mentioned. In 1875 Cayley posed a lottery problem in the Educational Times and solved it by backward induction; but that problem scores the actual amount drawn, and Ferguson does not regard it as a secretary problem at all. Kepler, after his wife died in 1611, considered eleven candidates over two years and finally married the fifth; but he tried to go back to a candidate he had passed over (and was turned down), which means that he did not consider himself bound by “no recall”. Claims such as “Kepler used the 37 % rule” are therefore inaccurate: Kepler’s story shows precisely how real choices tend to violate the assumptions of the secretary problem.
Do the assumptions hold in practice?
Putting Ferguson’s six conditions back into real life, they can be checked one by one.
A known number: in hiring one often does not know how many more will apply (Chapter 2). Random order: early and late applicants may differ, and if order is related to quality the derivation fails. Relative ranks only: in reality scores are usually visible and their distribution roughly known (Chapter 2). No recall: one often can go back, though the person may have accepted another offer, and offers may be refused (Chapter 2). Only the best counts: in reality quality varies continuously and interviews cost something (Chapter 6).
These checks are not meant to dismiss the model. The value of the secretary problem lies in putting the two errors, stopping too early and stopping too late, into one framework that can be calculated, and in showing that when information is scarce, it pays to set aside part of one’s opportunities for learning. Chapter 2 relaxes the conditions one at a time and watches how the conclusions change.
Summary
With a known number of applicants, random order, relative ranks only, no recall and only the best counting as success, the optimal rule is a cutoff rule: skip about applicants, then hire the first relative best; the success probability tends to . For finite the optimal share skipped and the success probability differ slightly and can be computed exactly; the success probability is flat near the optimum. About 63 % of the time the rule does not choose the best, and for it ends with nobody in 37.5 % of cases. Ferguson’s history shows that Gardner’s original game was a two-person game and that the standard solutions answer a narrower question; Kepler’s story violates the “no recall” assumption. The next chapter relaxes these conditions.
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).