The 37% Rule

Candidates arrive one at a time in random order. You can rank each against those already seen, you must say yes or no on the spot, and nobody can be called back. Choose how many to reject outright; the rule then takes the first candidate who beats all of them.

Chance of the best, rejecting k	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Best cutoff, large n	$k^*\approx\frac{n}{e}$
Its chance	$P(k^*)\to\frac{1}{e}\approx0.3679$

Worked example — The 37% Rule

Chance of the best, rejecting 4	39.84%
Best cutoff k*	4
Chance of the best at k*	39.84%
n/e, for comparison	4.05
Chance of the best by picking at random	9.09%
Chance the best is among the rejected	36.36%
Chance the search reaches the last candidate	40%
Least expected rank any rule can reach	2.6136

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — The 37% Rule

In the secretary problem, n candidates arrive in random order, each is compared only with those already seen, and each must be accepted or rejected on the spot, for good. The cutoff rule rejects the first k and then accepts the first candidate better than all of them.

Where the formula comes from

Split by where the best is. Write B for the position of the best candidate and W for ending with it. B is equally likely to be any of 1 to n.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
A best among the first k is lost. The rule never looks back, so those positions contribute nothing.
$B\le k:\quad P(W\mid B)=0$
A best at position i > k is reached only if nobody between k + 1 and i − 1 was taken. That happens exactly when the best of the first i − 1 sits among the first k, since only then does nobody in between beat the benchmark. Any of the i − 1 is equally likely to be that one.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Add over the positions.
$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}$
Let n grow. With x = k/n the sum becomes an integral and the chance becomes −x ln x. Its derivative, −ln x − 1, is zero at x = 1/e, where the chance is 1/e ≈ 36.79%.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Assumes: Only ranks are seen, never scores; the order is uniformly random; a rejected candidate cannot be recalled and an accepted one always says yes; and anything short of the very best counts as a loss.

Problems solved in full

Three candidates, every order listed 3 steps
Three candidates arrive in random order. Write each order as the ranks in arrival order (1 = best). Rejecting the first and then taking the first who beats everyone before, in how many of the six orders do you end with the best? Check the answer with the formula.

Open this problem in the tool
1. The six orders:
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. The first candidate sets the benchmark. In 213 and 231 the best beats the 2; in 312 the 1 arrives second and is taken. In 123 and 132 nobody beats the 1 that was rejected, so the last is taken; in 321 the 2 beats the 3 and is taken before the 1 arrives:
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. The formula with n = 3 and k = 1:
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Answer

3 of the 6 orders, a chance of 1/2, against 1/3 for taking the first candidate.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Four candidates, every cutoff 2 steps
With four candidates, find the chance of ending with the best for each cutoff k = 0, 1, 2, 3, and the best cutoff.

Open this problem in the tool
Show solution
1. k = 0 takes the first candidate, who is the best with chance 1/4. For k ≥ 1 use the formula:
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Compare the four:
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Answer

Reject one, then take the first who beats it: 11/24 ≈ 45.83%.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
Kepler's eleven 3 steps
In 1611 Johannes Kepler set about choosing a second wife and, over nearly two years, considered eleven candidates. With the cutoff rule and n = 11, which cutoff is best, what is its chance, and which candidate is the first the rule can take?

Open this problem in the tool
Show solution
1. Evaluate the formula around n/e = 11/e ≈ 4.05:
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. k = 4 is the largest; k = 3 and k = 5 are both lower:
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. With four rejected, the fifth candidate is the first the rule can accept. Kepler did marry the fifth, but not by this rule: Ferguson's account of his letter has him persuaded to propose to the fourth after meeting the fifth, being turned down, and going back. The rule forbids going back.
Answer

Reject four, chance 39.84%; the fifth is the first candidate the rule can take.

$k^*=4,\qquad P(4)\approx0.3984$
Many candidates: where 1/e comes from 3 steps
For large n, write the share rejected as x = k/n and find the best x and the chance it gives. Then check against n = 100.

Open this problem in the tool
Show solution
1. The sum is a Riemann sum for 1/t on [x, 1]:
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Set the derivative to zero:
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. For n = 100, n/e ≈ 36.79, and the exact best cutoff is 37:
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Answer

Reject a share 1/e ≈ 36.79%; the chance tends to 1/e. At n = 100 the best cutoff is 37, with chance 37.1%.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Left with the last candidate 3 steps
A hundred candidates, the first 37 rejected. Find the chance that the best is among the rejected, the chance that the search reaches the last candidate, and the chance that the last candidate is then the best.

Open this problem in the tool
Show solution
1. The best is equally likely to be anywhere, so it is among the first 37 with chance:
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. The search reaches candidate 100 exactly when nobody from 38 to 99 is taken, that is when the best of the first 99 is among the first 37:
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. The difference is the case where the search reaches the end and the last candidate is the best:
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Answer

37%, 37.37% and 0.37%: more than one search in three ends with the last candidate, and almost never because the last is the best.

$0.37,\qquad 0.3737,\qquad 0.0037$
The lowest expected rank, three candidates 3 steps
Three candidates, and the aim is now the lowest expected rank (1 = best), not the best itself. Find the optimal rule by backward induction and its expected rank.

Open this problem in the tool
Show solution
1. A candidate seen i-th whose rank among those seen is j has expected overall rank j(n + 1)/(i + 1). The third candidate must be taken, and has expected rank (n + 1)/2:
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. At the second candidate, take it if its expected rank is no more than 2, otherwise go on:
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. At the first, taking it gives 2, more than 5/3, so go on:
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Answer

Pass the first, take the second if it beats the first, otherwise take the third: expected rank 5/3 ≈ 1.67. With three candidates this is exactly the cutoff rule with k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Two candidates, scores seen 2 steps
Two candidates have scores drawn independently and uniformly from 0 to 1, and you see each score as it arrives. Find the rule that most often ends with the higher score, and its chance. Compare it with ranks alone.

Open this problem in the tool
Show solution
1. If you pass the first, whose score is x, you must take the second, which wins when it is higher: chance 1 − x. If you take the first, it wins when the second is lower: chance x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. So take the first when x ≥ 1/2. Average over x:
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Answer

Take the first when its score is at least 1/2: chance 3/4. With ranks alone, two candidates give 1/2 whatever you do.

$P=\frac{3}{4}>\frac{1}{2}$

Supplementary problems, answers only

With five candidates, find the best cutoff and its chance.

Show answer

Reject two: 13/30 ≈ 43.33%.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
With two candidates and ranks only, show that every rule ends with the best half the time.

Show answer

Taking the first wins with 1/2; passing it means taking the second, also 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
With ten candidates at the best cutoff, find the chance the best is among the rejected and the chance the search reaches the last candidate.

Show answer

k = 3: 30% and 3/9 ≈ 33.33%.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
In the large-n limit, find the chance of the best when a fifth of the candidates are rejected, and when three fifths are.

Show answer

−0.2 ln 0.2 ≈ 32.19% and −0.6 ln 0.6 ≈ 30.65%.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
With four candidates, find the lowest expected rank any rule can reach.

Show answer

15/8 = 1.875.

$c_0=\frac{15}{8}=1.875$

Reject a quarter or reject a half: the same chance

The curve is flat at the top, and that is what makes the rule usable. Press A quarter rejected: 35.04%. Press Half rejected: 34.91%. The best cutoff for a hundred, 37, gives 37.1%, so rejecting anywhere from a quarter to a half costs you at most 2.2 points. As n grows the curve becomes −x ln x, with x the share rejected, and at a quarter and at a half it takes exactly the same value, because ¼ ln 4 = ½ ln 2 ≈ 34.66%. So you need not know n well: guess it a third too high or a third too low, reject 37% of your guess, and for large n you still keep at least 34.5%.

Aim only for the best, and more than a third of the time you get the last

The rule bets everything on the very best. When the best is among the candidates you rejected, which happens 37% of the time with a hundred, nobody later can beat the benchmark, and the search runs to the end and takes whoever comes last. Press A hundred, 37 rejected: the expected rank of the candidate taken is 20.01. In 1964 Chow, Moriguti, Robbins and Samuels asked for the rule with the lowest expected rank instead. It takes a candidate who is merely near the top of those seen so far, with a standard that loosens as the line runs out, and its expected rank at n = 100 is 3.60. Theirs stays below 4 for every n this page offers and tends to 3.8695; the 37% rule's keeps growing with n, to 185.54 at a thousand.

See the scores, and the chance rises to 58%

The 37% rule uses only ranks: who beat whom. Suppose instead that you see each candidate's actual score and know how scores are spread, say uniformly between 0 and 1. Gilbert and Mosteller solved this version in 1966, and the look-without-choosing phase disappears. From the first candidate on, you take anyone who is the best so far and scores above a threshold, and the threshold falls as the line runs out: 0.5 with one candidate still to come, 0.6899 with two, 0.9240 with ten. The chance of ending with the best is 60.6% for eleven candidates and 58.29% for a hundred, and it tends to 58.02%, against 36.79% from ranks alone. Knowing what a good score looks like is worth about 21 points.

Learning path

Choosing on what you have seen

References (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

By the 7 Raven Room team · Reviewed against published sources. Corrections welcome.

The 37% Rule

Where the formula comes from

Supplementary problems, answers only

Reject a quarter or reject a half: the same chance 🖖

Aim only for the best, and more than a third of the time you get the last 🖖

See the scores, and the chance rises to 58% 🖖

Reject a quarter or reject a half: the same chance

Aim only for the best, and more than a third of the time you get the last

See the scores, and the chance rises to 58%