You have a single position to fill for a secretary. There are $n$ applicants for the position. After interviewing each of the applicants you can immediately rank the applicant from worst to best with the previous interviewed applicants. However, immediately after the interview you must make the decision to hire the applicant. You only have one chance to hire the applicant directly after the interview. The question is: how many applicants must you interview before hiring the current applicant?
If you make your decision too early you might not hire the best applicant. But if you wait to long you might have rejected the best applicant already. More realistic, this is a problem that happens quite regular in real life as well:
- If you want to buy a house, how many potential houses must you visit before buying your favorite house? If you reject a house, someone else will buy it.
- How often should you change jobs before hoping you’ll end up with the best job you will get? If you resign a job, you (usually) can’t return to your old job.
There is a mathematical optimum for this problem. Suppose we have $n$ applicants. Our strategy is as follows: we reject the first $r – 1$ applicants. Then we continue with the $n – r$ other applicants. When there is a applicant better than the first $r – 1$ applicants, we take this applicant as our best choice. The goal is to find the optimal $r$ such that the probability that we chose the best applicant is optimal. Let $P(r)$ be the probability that we select the best applicant after rejecting the first $r – 1$ applicants, then
$$
\begin{align*}
P(r) &= \sum_{i = r}^{n} P(\text{$i$ is the best applicant} \cap \text{we choose $i$}) \\
&= \sum_{i = r}^{n} P(\text{$i$ is the best applicant}) P(\text{we choose $i$} | \text{$i$ is the best applicant}).
\end{align*}
$$
We have $P(\text{$i$ is the best applicant}) = \frac{1}{n}$. The second part of the equation is a bit more work. Given $i$ is the best applicant, what is the probability that we would choose $i$? This is only possible if applicants $r, r+1, …, i-1$ were worse than one of the first $r – 1$ applicants. Therefore, the second best applicant before $i$ must be in the first $r – 1$ applicants. The probability of this is $\frac{r – 1}{i – 1}$. We now have
$$
\begin{align*}
P(r) &= \sum_{i = r}^{n} \frac{1}{n} \frac{r\, -\, 1}{i\, -\, 1} = \frac{r\, -\, 1}{n} \sum_{i = r}^{n} \frac{1}{i\, -\, 1}.
\end{align*}
$$
We can try to compute the sum for each $r$ and find the optimal $P(r)$, but there is another way. We try to approximate the sum with a continuous function. Take $x = \frac{r – 1}{n}$, for large $n$ we have
$$
P(r) = \frac{r\, -\, 1}{n} \sum_{i = r}^{n} \frac{1}{i\, -\, 1} \approx x \int_{x}^{1} \frac{dt}{t} = – x\, \mathrm{log}(x) = \tilde{P}(x).
$$
$\tilde{P}(x)$ takes its optimum when its derivative is zero. I.e.
$$
\begin{align*}
0 = \tilde{P}'(x) &= -\mathrm{log}(x)\, -\, 1 \\
\mathrm{log}(x) &= -1, \qquad x = \frac{1}{e}.
\end{align*}
$$
Because $x = \frac{r – 1}{n}$ we find that $r = \frac{n}{e} + 1$, so the optimal strategy is to reject the first $\left[\frac{n}{e}\right]$ (round down) applicants.
So what are the mathematical optimal solutions to the real-life questions asked above? It depends per person, but you should first figure out how many options (applicants) you want to take at maximum. If you have found your maximum you can use the secretary problem to figure out how many options you have to reject by default. Then, you should select the first try that’s better than the options you have rejected before.
- When should you bid on a house that you visited? Depending on how much you like visiting houses, but you probably don’t want to visit more than 10 houses at maximum. This means that you should reject the first $\left[\frac{10}{e}\right] = 3$ houses straight. Afterwards, every other house you visit that’s better than the first 3 I should try to buy.
- When should you change jobs? First compute how many jobs you could have at maximum in my life? You work for around 45 years and I think you should work at least 2.5 years for the same employer before being able to say if you like the job or not. This means that you can have around 18 jobs maximum in your working life. This means that you should switch jobs after 2.5 years for the first $\left[\frac{18}{e}\right] = 6$ jobs. Afterwards you should continue switching jobs, until you find a job that’s better than any of the previous jobs. Another way to look at this problem is saying that the first $\left[\frac{45}{e}\right] = 16$ years of your working life you can switch jobs regardless. Afterwards you should become more selective and stick to any job that’s better than any of the previous jobs. You will probably not get anything better.
What is the main takeaway from the secretary problem? We probably make decisions too soon. We stick too long with our current situation. Mathematically it’s probably better to reject offers more often and only after the first $\left[\frac{n}{e}\right]$ options we should become more picky. On the other hand we can’t continue rejecting all our options thinking something better will eventually appear. There is a clearly defined threshold that tells you went to stop looking for other options.