WordGPT

The secretary problem and the 37% rule

Exercise · Level 5 (Olympiad)

You see 100 candidates one by one and must hire on the spot (no going back). How do you maximise the chance of hiring the best one, and what is that chance?

1e≈0.368\frac1e\approx0.368

wordgptpro.com

Solution 1/2

  1. Skip the first r−1r-1 candidates, then take the first one better than everyone seen so far. If the best is at position k≥rk\ge r, you win when the best of the first k−1k-1 is among the first r−1r-1, which has probability r−1k−1\tfrac{r-1}{k-1}:

    P(r)=r−1n∑k=rn1k−1P(r)=\frac{r-1}{n}\sum_{k=r}^{n}\frac1{k-1}
    (1)

wordgptpro.com

Solution 2/2

  1. For n=100n=100 this is largest at r=38r=38, with P≈0.371P\approx0.371. For large nn put x=r/nx=r/n: P≈xln⁡1xP\approx x\ln\tfrac1x, maximal at x=1ex=\tfrac1e:

    Pmax⁡≈1e≈0.368P_{\max}\approx\frac1e\approx0.368
    (2)
  2. The rule: reject the first 37% of candidates, then pick the next one who beats all of them. You get the best candidate more than a third of the time, however many there are.

Answerskip 37%, then take the next best: P≈0.368\text{skip }37\%,\ \text{then take the next best}:\ P\approx0.368

wordgptpro.com

Need a hint?

Look at the first r candidates without hiring, then hire the first one better than all of them. Find the best r.

Skip the first 37 or 38 of 100 candidates and take the next one who beats them all: the chance of the best is about 37% (1/e).

How to work it out

  1. Skip the first r−1r-1 candidates, then take the first one better than everyone seen so far. If the best is at position k≥rk\ge r, you win when the best of the first k−1k-1 is among the first r−1r-1, which has probability r−1k−1\tfrac{r-1}{k-1}:

    P(r)=r−1n∑k=rn1k−1P(r)=\frac{r-1}{n}\sum_{k=r}^{n}\frac1{k-1}
    (1)
  2. For n=100n=100 this is largest at r=38r=38, with P≈0.371P\approx0.371. For large nn put x=r/nx=r/n: P≈xln⁡1xP\approx x\ln\tfrac1x, maximal at x=1ex=\tfrac1e:

    Pmax⁡≈1e≈0.368P_{\max}\approx\frac1e\approx0.368
    (2)
  3. The rule: reject the first 37% of candidates, then pick the next one who beats all of them. You get the best candidate more than a third of the time, however many there are.

LaTeX source of the formulas on this page
\[ \text{skip }37\%,\ \text{then take the next best}:\ P\approx0.368 \]
\[ P(r)=\frac{r-1}{n}\sum_{k=r}^{n}\frac1{k-1} \]
\[ P_{\max}\approx\frac1e\approx0.368 \]

Questions

What is the answer to: The secretary problem and the 37% rule?

Skip the first 37 or 38 of 100 candidates and take the next one who beats them all: the chance of the best is about 37% (1/e).

What is the key idea?

Learning phase then commitment: the optimum balances missing the best against stopping too early.

Is there a hint?

Look at the first r candidates without hiring, then hire the first one better than all of them. Find the best r.

Related problems

More probability and puzzles

    The secretary problem and the 37% rule: answer and solution | WordGPT