Hiring the best of five

Idea. Only a candidate who is the best so far can be the overall best, so the decision is when to start accepting such candidates. Compute the success probability of each cut-off and take the best.

Step 1: success with cut-off $k\ge 1$. The best candidate is in position $i$ with probability $\frac{1}{5}$. If $i\le k$, it is rejected. If $i>k$, it is hired exactly when nobody between positions $k+1$ and $i-1$ was hired before it, that is, when the best of the first $i-1$ candidates lies among the first $k$, which has probability $\frac{k}{i-1}$. So $$P(k)=\frac{k}{5}\sum _{i=k+1}^5\frac{1}{i-1}.$$

Step 2: compare.

• $k=1$: $\frac{1}{5}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{5}{12}\approx 0.417$.
• $k=2$: $\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx 0.433$.
• $k=3$: $\frac{3}{5}\left(\frac{1}{3}+\frac{1}{4}\right)=\frac{7}{20}=0.35$.
• $k=0$ (hire the first one) gives $\frac{1}{5}$.

Step 3. The best strategy rejects the first two candidates and wins with probability $\frac{13}{30}$.

For large $n$. The best cut-off is about $\frac{n}{e}$ and the success probability tends to $\frac{1}{e}\approx 0.368$: you can hire the best of a million candidates more than a third of the time.