What does Bayesian Search and Optimal Stopping conclude, in numbers, about “Variants of the Secretary Problem and How People Stop”?
Answer: 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 \(n = 100\) 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".
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: 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 |
Show the full program
# (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}")Single source and citation
Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices (Version 1.0.0), Chapter 2: Variants of the Secretary Problem and How People Stop. 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 1 · The Secretary Problem and 1/e: When to Stop If You See Only Ranks and Cannot Go Back
- 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