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 k1: 0.5000 k=2: 0.6899 k=5: 0.8559 k=10: 0.9240 k=100: 0.9920
k (1 - b_k) at k1000: 0.8039
n10: P(best) = 0.6066 (SE 0.0024)
n40: P(best) = 0.5941 (SE 0.0025)
n100: P(best) = 0.5794 (SE 0.0025)
minimal expected rank: n10: 2.5579, n=40: 3.3282, n=100: 3.6032, n=1000: 3.8324
n100000: 3.8690
expected rank, 1/e cutoff rule: n40: 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