Secretary Problem

Problem. $n$ candidates arrive in random order. After each interview you learn only the candidate’s rank relative to those seen so far, and must immediately accept or reject — rejections are final. Maximise the probability of hiring the single best candidate.

The optimal strategy

Reject the first $k$ candidates, then accept the first one better than all of them.

The optimal cut-off is $k\approx n/e$, and the success probability is

$\frac{1}{e}\approx \mathrm{0.3679.}$

Remarkably, the probability does not decrease with $n$ — it converges to $1/e$ for every large $n$.

The derivation

With cut-off $k$, you win if the best candidate is at position $i>k$ and the best among the first $i-1$ lies in the first $k$:

$P(k)={\sum }_{i=k+1}^n\frac{1}{n}\cdot \frac{k}{i-1}=\frac{k}{n}{\sum }_{i=k+1}^n\frac{1}{i-1}\approx \frac{k}{n}\ln \frac{n}{k}.$

Maximise over $x=k/n$: $\frac{d}{dx}(-x\ln x)=0$ gives $x=1/e$, with value $1/e$. ∎

int optimalCutoff(int n) {
    double best = 0; int bestK = 0;
    for (int k = 1; k < n; k++) {
        double p = 0;
        for (int i = k + 1; i <= n; i++) p += (double)k / (n * (i - 1));
        if (p > best) { best = p; bestK = k; }
    }
    return bestK;
}

For $n=100$ the exact optimum is $k=37$, with success probability $0.371$.

Why $1/e$ keeps appearing

The same “explore then exploit” structure and the same constant show up throughout online decision-making:

Problem	Constant
Secretary problem	$1/e\approx 0.368$
Online bipartite matching (RANKING)	$1-1/e\approx 0.632$
Max coverage greedy	$1-1/e$
Submodular maximisation greedy	$1-1/e$
Balls into bins, fraction of empty bins	$1/e$
Derangements	$1/e$
Random permutation with no short cycle	$e^{-\gamma }$-flavoured

The recurrence of $1/e$ is not a coincidence: it is $\lim (1-1/n{)}^n$, the probability of avoiding $n$ independent events each of probability $1/n$.

Variants

Variant	Optimal strategy / value
Maximise $\mathrm{Pr}[\text{best}]$	reject $n/e$, then take the first record — $1/e$
Maximise the expected rank	a different, much better strategy; expected rank $\to 3.87$
Maximise the expected value (values known)	threshold rules; the prophet inequality gives $\frac{1}{2}$
Accept the best or second best	higher success probability, two thresholds
Choose $k$ candidates	multiple-choice secretary; $\to 1$ as $k$ grows
Values from a known distribution	a fixed threshold suffices
Rejections can be recalled	trivially solvable
$n$ unknown	randomised cut-off strategies
Arrivals not uniformly random	the guarantee breaks

The prophet inequality

When the values (not just ranks) are drawn from known distributions, a single threshold $T$ with $\mathrm{Pr}[\max >T]=\frac{1}{2}$ guarantees at least $\frac{1}{2}$ of the expected maximum. Simple, and the constant $\frac{1}{2}$ is tight.

This is the theoretical basis for reserve prices in auctions, and it is the “known distributions” counterpart to the rank-only secretary problem.

Online algorithms and competitive ratio

The secretary problem is the entry point to online algorithms, where decisions are irrevocable and the benchmark is the offline optimum:

$\text{competitive ratio}=\frac{\text{ALG}}{\text{OPT}}.$

Online problem	Best ratio
Secretary	$1/e$ (probability of the best)
Online bipartite matching	$1-1/e$
Ski rental	$2$ deterministic, $\frac{e}{e-1}$ randomised
Paging ($k$ pages)	$k$ deterministic, $H_k$ randomised
Online load balancing	$2-\frac{1}{m}$
List update	$2$ (move-to-front)

Ski rental is the other classic worth knowing: rent for 1/day or buy for $B$; renting until you have spent $B$, then buying, is 2-competitive, and randomising the switch point improves it to $\frac{e}{e-1}\approx 1.58$.

Why it is worth knowing

It is the cleanest demonstration that an optimal irrevocable strategy can be computed exactly, and that the answer is a clean constant independent of $n$. The explore-then-exploit shape — sample a fraction, then commit to anything better — recurs throughout online algorithms and is worth recognising.

See also: Probability · Approximation Algorithms · Stable Marriage