Best Secretary Problem - Mysterious 1/e

Problem

Suppose you were a boss of a large company and you would like to recruit only one secretary. The offer looks so good that candidates line up in front of your office eagering to be interviewed by you. However, you have to make your decision after interviewing one candidate. Once a candidate is announced to be recruited, all waiting candidates are no longer able to be considered.

What’s the best strategy to pick out the best candidate?

Modeling

There are in all \(N\) candidates. The best candidate locates at the \(i^{th}\) position. You decide to interview the first \(k\) candidates and pick the best among them as a benchmark. For the following candidates at location \(k+1\), \(k+2\), \(...\), \(N\), once you find one with better performance than the benchmark one, you pick. Let’s denote \(P(k)\) to be the probability of successfully picking up the \(i^{th}\) candidate following our strategy.

For a given \(k\), the \(i^{th}\) candidate can be picked up if and only if

Candidates among k+1, k+2 … i-1 are all no better than the best among the first k candidates. The condition is equivalent to the best among the first i-1 candidates locates no later than k.

Since the best among the first i-1 candidates can uniformly and randomly located anywhere in the first i-1 positions. The probability of the best located no later than k is

\[\frac{1}{i-1} \times k = \frac{k}{i-1}.\]

Remember that, \(i\) can also be any number between (inclusive) \(k+1\) and \(N\). So

\[P(k) = \sum_{i=k+1}^{N} \frac{1}{N}\frac{k}{i-1} = \frac{k}{N} \sum_{i=k+1}^{N} \frac{1}{i-1} = \frac{k}{N} \sum_{i=k}^{N-1} \frac{1}{i},\]

where the \(1/N\) is the probability of the best candidate locating at position \(i\).

Now, we need to relex the discret requirement of \(k\) by assume \(N\) to be sufficiently large. Then

\[\begin{split}P(k) =& \frac{k}{N} \sum_{i=k}^{N-1} \frac{1}{i}\\ \approx& \frac{k}{N} \int_{i=k}^{N-1} \frac{1}{t} dt\\ \approx& \frac{k}{N} \int_{i=k}^{N} \frac{1}{t} dt\\ =& \frac{k}{N} ( \ln n - \ln k).\end{split}\]

Now take derivative to \(P(k)\) w.r.t \(k\) to find the maximum, we have

\[\begin{split}& \frac{\partial }{\partial k} P(k) = \frac{1}{N} (\ln N - \ln k - 1) = 0\\ \Rightarrow& \ln \frac{N}{k} = \ln e\\ \Rightarrow& k = \frac{N}{e}.\end{split}\]

Conclusion

So you should set the best among first \(\frac{N}{e}\) candidates as benchmark and pick the next candidate who is beyond the benchmark.