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
53 0.400 0.4333 0.4333 3
104 0.300 0.3987 0.3987 4
115 0.364 0.3984 0.3984 5
208 0.350 0.3842 0.3842 8
4016 0.375 0.3757 0.3757 16
10038 0.370 0.3710 0.3710 38
1000369 0.368 0.3682 0.3682 369
limit: skip share and P(success) both1/e = 0.3679
n100: skip share x, exact P, approximation -x ln x
x0.10 P = 0.235 -x ln x = 0.230
x0.20 P = 0.326 -x ln x = 0.322
x0.30 P = 0.365 -x ln x = 0.361
x0.37 P = 0.371 -x ln x = 0.368
x0.50 P = 0.349 -x ln x = 0.347
x0.60 P = 0.309 -x ln x = 0.306
simulation, n100, r = 38, 20,000 runs: 0.3731
nobody chosen (best among the skipped), n40, r = 16: 0.375

Key formula

\[P(r) = \sum_{i=r}^{n} \frac{1}{n}\cdot\frac{r-1}{i-1} = \frac{r-1}{n}\sum_{i=r}^{n}\frac{1}{i-1}, \qquad r \ge 2,\]
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