The Secretary Problem: When to Stop Looking

You’re hiring for a single position. There are $n$ qualified candidates, but they will be interviewed in completely random order. After each interview, you must decide immediately whether to offer the job — say yes and hiring stops, say no and that candidate is gone forever. You want to maximize your chance of hiring the very best candidate.

What’s the optimal strategy?

This is the secretary problem, one of the most famous and surprising results in probability theory. It is sometimes called the marriage problem, the sultan’s dowry problem, or the best-choice problem. It has been independently discovered several times, dating back to 1949, and the optimal solution involves a constant — $1/e$ — that appears with no warning and beautifully ties the problem to the universal mathematical constant $e \approx 2.71828$.

This article is about what the optimal strategy is, why it works, and what the result reveals about the structure of decision-making under uncertainty.

The setup precisely

To make the problem mathematically clean, let’s specify:

1. There are $n$ candidates with distinct quality rankings (no ties).
2. They arrive in a random order, uniformly over all permutations.
3. After interviewing each, you can rank them relative to those already seen.
4. After each candidate, you must immediately accept or reject. No going back.
5. Your goal is to hire the absolute best candidate (rank 1 of $n$).

Note: you cannot get any info about future candidates. You only know the relative rank of those you’ve seen so far. And you can’t compare a current candidate to a future one.

This is an idealization. Real hiring isn’t like this. But the abstract problem turns out to capture something deep about a whole class of decision problems where you have to commit before seeing all options.

The optimal strategy

The answer, derived independently by several mathematicians in the 1950s and 1960s, is a “look-then-leap” rule:

1. Reject the first $r$ candidates unconditionally. Just look at them; build a sense of what the field looks like.
2. From candidate $r+1$ onward, hire the first one who is better than everyone you’ve seen so far.

The question becomes: what is the optimal $r$?

The probability of hiring the best candidate using this strategy with cutoff $r$ is:

$P(r) = \frac{r}{n} \sum_{k=r+1}^{n} \frac{1}{k - 1}.$

To find the optimal $r$, take the derivative with respect to $r$, set it to zero, and solve. After approximation in the limit of large $n$:

$\boxed{r^* \approx \frac{n}{e}.}$

And the corresponding probability of success is:

$P(r^*) \approx \frac{1}{e} \approx 0.368.$

So: reject the first $n/e \approx 37\%$ of candidates outright, then hire the first one who beats all of them. This succeeds about 37% of the time.

For specific $n$:

$n$	Optimal $r$	Probability of success
5	2	0.433
10	3 or 4	0.399
20	7	0.384
100	37	0.371
1000	368	0.368

The probability of success approaches but never quite reaches $1/e$ as $n$ grows. For 100 candidates, you have a 37.1% chance of hiring the absolute best — surprisingly high given that random guessing would give only 1%.

Why $e$ appears

The transcendental number $e$ shows up because the optimization is about a logarithm. Working through the algebra:

$P(r) = \frac{r}{n} \cdot (H_{n-1} - H_{r-1})$

where $H_k = 1 + 1/2 + \cdots + 1/k$ is the harmonic number. For large $n$, $H_n \approx \ln n + \gamma$ (where $\gamma$ is the Euler-Mascheroni constant), so

$P(r) \approx \frac{r}{n} \cdot \ln(n/r).$

Maximize this with respect to $r/n = x$ — set $\frac{d}{dx}[x \ln(1/x)] = -\ln x - 1 = 0$ — and you get $x = 1/e$.

The same constant that controls compound interest, exponential growth, and the Euler identity controls the optimal stopping rule. (See our piece on $e$ for the broader picture.)

Why “look-then-leap” works

The intuition is that the cutoff $r$ balances two competing concerns:

• Too small a cutoff: you don’t see enough candidates to know what good looks like, so the first reasonably good candidate seems great by comparison and you hire someone mediocre.
• Too large a cutoff: you’ve seen so many candidates that the “best so far” rule becomes very strict, and you’re likely to reject many great candidates before reaching the very best.

The optimal cutoff is the one that maximizes the expected information about the field versus the expected loss from rejecting good candidates. That balance turns out to land at $1/e$.

There’s an alternative way to see why $1/e$ is right: among permutations of $n$ candidates, the probability that the best candidate appears in the second position (i.e., position 2) is $1/n$. The probability that the best candidate is at any specific position is $1/n$. The optimal cutoff $r$ is the one that maximizes the chance of stopping at the best candidate while having seen enough of the bad ones first.

Where this gets applied

The secretary problem isn’t really about hiring secretaries. It’s a clean abstract example of optimal stopping theory — the mathematical study of when to commit to a decision given sequential, irreversible choices. Variants of this problem appear throughout applied mathematics:

Online matching. When ride-sharing apps assign drivers to riders, or when ad systems decide which ad to show, the situation is similar: you see opportunities one by one and must commit immediately. Variants of the secretary problem give optimal strategies. The 2009 Nobel Prize in Economics went in part to work on related matching problems.

Online auctions. When deciding whether to accept an offer or wait for a better one, secretary-style reasoning applies. The “buy low, sell high” intuition gets a precise quantitative form.

House hunting and dating. The popular media has gleefully reported the “37% rule” as advice for dating: date 37% of your prospective partners, then commit to the next one who’s better than everyone you’ve dated. This is, of course, not actually how human relationships work — but it captures something real about the trade-off between exploration and commitment.

Scientific publication. Editors deciding when to publish a paper they’ve reviewed face a similar trade-off: accept this submission, or wait for a possibly better one.

Statistical sampling. Sequential analysis methods (developed by Wald during WWII for quality control) build on similar mathematics. You sample until you have enough evidence to make a decision.

Resource allocation. Cloud computing systems deciding when to grant resources, healthcare systems deciding when to admit patients, banks deciding when to extend credit — many real-time decision problems have secretary-like structure.

In each case, the key insight is the same: spend a portion of your time learning, then commit when you see something clearly above the learned baseline.

Variations and extensions

The classical secretary problem has spawned an enormous literature of variants:

Variable acceptance criterion. Instead of trying to hire the absolute best, what if you’d be happy with any of the top $k$? The optimal strategy still has a learning phase but the cutoff differs.

Recall allowed. What if you can return to a previous candidate (with some probability they’re still available)? This lifts the optimal probability above $1/e$.

Unknown $n$. What if you don’t know how many candidates there are? Sequential rules with adaptive cutoffs work well, with provable competitive ratios against the optimal known-$n$ strategy.

Cardinal information. What if you can observe absolute candidate values, not just relative ranks? Then you can use threshold strategies. The optimal threshold turns out to involve $\sqrt{2 \ln n}$ for normally distributed candidates.

Multiple acceptances. Hiring $k$ candidates instead of one. The optimal strategy still has a learning phase but now keeps accepting candidates above multiple decreasing thresholds.

Adversarial. What if candidates aren’t randomly ordered but chosen by an adversary? Online algorithms theory addresses this; bounds are tighter (worst-case competitive ratios).

This tree of variants is one of the richer areas of probability theory and theoretical computer science. There are good reasons. The secretary problem captures, in clean form, a fundamental aspect of decision-making under uncertainty — and small modifications produce many different real-world scenarios.

What it teaches

Beyond the specific result, the secretary problem teaches several general lessons:

Exploration before exploitation. Almost every reasonable sequential decision problem has a structure of “learn for a while, then commit.” The proportion of time spent learning depends on the problem, but the basic structure is universal. This is the foundation of multi-armed bandit theory and modern reinforcement learning.

Optimal need not be perfect. Even with the optimal strategy, you only succeed 37% of the time. The probability is bounded; the secretary problem is not a “trick” that lets you always pick the best. It’s a way to do as well as possible given the constraints.

Math turns intuition into proof. “Spend some time looking, then commit” is folk wisdom. The mathematics tells you exactly how much time, and exactly what your success probability is. The same kind of folk wisdom plus mathematical precision underlies most of decision theory.

The transcendental constants are everywhere. When optimization produces an answer like $1/e$, it’s a sign that exponential or logarithmic structure is hiding in the problem. The secretary problem is one of many places where $e$ appears with no obvious connection to growth or compound interest. This connects the seemingly unrelated worlds of decision theory, calculus, and pure mathematics.

For practical purposes, the lesson is something like: when faced with sequential, irreversible choices, calibrate yourself for about a third of the available time before committing. The exact threshold depends on the problem, but the order of magnitude is right. The mathematics behind this folk advice — and the surprising appearance of $e$ in the answer — is one of the small joys of probability theory.

A 1949 problem about hiring a secretary turned out to encode something general about decisions in time. That’s the kind of result that makes mathematics worth reading even when you have no plans to hire anyone.

Frequently asked

Why does e show up in the secretary problem?

Because the optimal stopping rule maximizes a probability that turns out to be 1/e in the limit of large n. The fraction n/e to skip emerges from setting the derivative of the success probability to zero. Whenever an optimization problem produces a transcendental answer like 1/e, there's usually an exponential or logarithmic structure underneath.

Does the secretary problem actually work for hiring?

It's a useful framework, but real hiring rarely matches the assumptions: you can usually go back to earlier candidates, you can compare candidates more flexibly, and the goal is rarely 'find the absolute best' but 'find someone good enough.' The lesson is more general: spend a fraction of your search learning what the field looks like, then commit when you find something clearly above that baseline.

Are there variants of this problem?

Many. Variants include allowing recall (you can return to earlier candidates), unknown n, multiple openings, partial information about candidate values, online matching with multiple acceptances, and adversarial settings. The whole subject of optimal stopping theory has dozens of related problems with their own elegant solutions, used in finance, online auctions, and resource allocation.

Continue reading

Blog

The Monty Hall Problem and Why Probability Tricks Your Brain

A game-show puzzle from the 1990s that fooled thousands of mathematicians — and what it reveals about how badly our intuition handles conditional probability.

Read →Blog

The Birthday Paradox: Why 23 People Is All You Need

In a room of 23 people, the chance two share a birthday is greater than 50%. A closer look at one of the most counterintuitive results in elementary probability.

Read →Blog

Bayesian Inference: How Beliefs Should Update

If a medical test is 99% accurate and comes back positive, what's the probability you actually have the disease? Often surprisingly low. Bayes' theorem tells you the right answer.

Read →