What does Bayesian Search and Optimal Stopping conclude, in numbers, about “The Secretary Problem and 1/e: When to Stop If You See Only Ranks and Cannot Go Back”?
Answer: 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 \(n/e\) applicants, then hire the first relative best; the success probability tends to \(1/e \approx 0.368\). For finite \(n\) 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 \(n = 40\) 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.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (17 programs, all checked), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.368, 40
| 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.375 |
Key formula
Show the full program
# 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}")Single source and citation
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices (Version 1.0.0), Chapter 1: The Secretary Problem and 1/e: When to Stop If You See Only Ranks and Cannot Go Back. 5D Library. https://doi.org/10.5281/zenodo.23810102
DOI: 10.5281/zenodo.23810102 · Read the monograph · 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}
}Other chapter answers in this book
- Chapter 2 · Variants of the Secretary Problem and How People Stop
- Chapter 3 · Bayesian Search: Where to Look, and What Not Finding Means
- Chapter 4 · Multi-Armed Bandits: Gittins Indices, Thompson Sampling and the Regret Lower Bound
- Chapter 5 · Sunk Costs: Rational Persistence, Fallacious Persistence and Stop-Loss Boundaries Set in Advance
- Chapter 6 · Applications: Testing Lanes and Selecting People
- Chapter 8 · Practice and a Pre-Registered Trial