The Secretary Problem and the 37 Percent Rule

The secretary problem's optimal rule rejects the first 37 percent of candidates, and both the cutoff and the success probability equal one over e.

The secretary problem's optimal strategy rejects the first roughly 37 percent of candidates outright, using them only to set a benchmark, and then selects the very next candidate who beats every candidate seen so far. As the number of candidates grows large, this rule succeeds in identifying the single best candidate with probability that also converges to roughly 37 percent, since both the optimal cutoff fraction and the resulting success probability equal 1 divided by the mathematical constant e, approximately 0.368.

There are n candidates who arrive one at a time in a uniformly random order, and their relative rankings are all distinct with no ties. After observing each candidate, the interviewer must immediately decide to hire them or reject them forever, based only on how that candidate compares to everyone seen so far, not on any absolute score. The goal is to maximize the probability of hiring the single best candidate out of all n, and the question asks for the optimal decision rule and the probability of success it achieves.

The candidates encountered early in the sequence carry little useful information, since being the best seen so far among the first few candidates says almost nothing about whether that candidate is the best among all n. A sound strategy therefore spends an initial stretch purely gathering information, rejecting every candidate in that stretch regardless of how impressive they look, then switches to hiring the first candidate afterward who outranks every candidate seen before, including the rejected ones. The only free parameter is where to place the cutoff between the observation phase and the hiring phase, call that cutoff position r out of n.

The strategy succeeds exactly when two things both happen: the single best candidate overall sits somewhere after position r, and no candidate between position r plus 1 and the position just before the best candidate was ever the best-so-far, which would have triggered an early, wrong hire. The best candidate overall is equally likely to sit in any of the n positions.

Conditional on the true best candidate sitting at position i, greater than r, the strategy succeeds only if the best among the first i minus 1 candidates is among the first r of them, since that is exactly the condition under which nobody between position r plus 1 and position i minus 1 was ever the best-so-far. Because that best-so-far position is uniformly distributed across the first i minus 1 candidates, this conditional probability equals r divided by i minus 1.