The Secretary Problem and Optimal Stopping

You must hire one assistant. There are $n$ applicants, you interview them one at a time in a random order, and after each interview you can rank that person against everyone you have seen so far — but nothing else. You must decide immediately: hire and stop, or reject forever. No calling anyone back. You win only if you hire the single best applicant of the whole pool.

With $n = 100$, what is your best strategy, and how often does it work?

Most people's first instinct is that this is hopeless — one shot, no do-overs, blind ranks. Try it before reading on, ideally with $n = 3$ or $n = 4$ where you can count everything by hand.

Getting the shape of the answer first

Any sensible strategy has the same skeleton. Hiring early is silly because you have no benchmark; hiring late is forced and probably mediocre. So you look at some candidates without hiring, learn how good "good" is, and then leap at the first candidate who beats everybody seen so far. Call such a candidate a record.

That reduces the whole problem to one number: the cutoff $k$, the count of applicants you deliberately throw away. Everything after that is mechanical — take the first record after position $k$, or end up with the last applicant if no record shows up.

Worked example: n = 4, counted exactly

Condition on where the best applicant actually sits, say position $i$; each position is equally likely, probability $1/4$. With cutoff $k$ you catch that best applicant if two things hold: they arrive after the cutoff ($i > k$), and nobody before them triggers a premature hire — which happens exactly when the best of the first $i-1$ applicants was inside the discarded block. Given the best is at $i$, the runner-up-so-far is equally likely to be in any of those $i-1$ earlier slots, so that has probability $k/(i-1)$.

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

In words: average, over every possible location of the true best, the chance that your rule is still shopping when they walk in. Now grind out $n = 4$:

• $k = 0$ (hire the first person): you win only if the best came first — $1/4 = 6/24$.
• $k = 1$: $\frac{1}{4}\left(\frac11 + \frac12 + \frac13\right) = \frac{1}{4}\cdot\frac{11}{6} = \frac{11}{24} \approx 0.458$.
• $k = 2$: $\frac{1}{4}\left(\frac22 + \frac23\right) = \frac{1}{4}\cdot\frac53 = \frac{10}{24} \approx 0.417$.
• $k = 3$: $\frac{1}{4}\cdot\frac33 = \frac{6}{24} = 0.25$.

So with four applicants you discard exactly one and take the next record, winning $11/24$ — about 46 percent of the time, against the 25 percent you would get by picking at random.

Worked example: n = 100 and the magic fraction

Run the same sum with $n = 100$ and $k = 37$. The tail $\sum_{i=38}^{100} \frac{1}{i-1}$ is a chunk of the harmonic series, close to $\ln(99.5/36.5) \approx 1.003$, so

$$P(37) \approx 0.37 \times 1.003 \approx 0.371 .$$

Roughly 37 percent — and notice it barely moved from the four-applicant case. Writing $x = k/n$ and letting $n$ grow, the sum becomes $x\ln(1/x)$, whose maximum sits at $x = 1/e \approx 0.368$ with value $1/e \approx 0.368$ as well. Hence the folklore 37 percent rule: sample 37 percent, then pounce, and you get the best candidate 37 percent of the time no matter how big the pool.

The transferable technique

Two habits generalise far beyond hiring. First, condition on the thing you care about — here, the position of the best applicant — and average over it, rather than trying to track the whole process forward. Second, when a problem is one-shot and irreversible, look for a threshold rule and reduce the search to a single parameter you can optimise.

That combination cracks the when-to-stop-rerolling dice game (accept any roll above a value you compute backwards from the end), the red-and-black card stopping game, the game of googol, and the whole explore-then-exploit family in which you spend a fixed budget learning before committing. On a desk it is the same question as deciding how long to shop an order around before taking the price in front of you: sample the market for a while, then hit the first quote that beats everything you have seen.