In HIRE-ASSITANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?

Hiring exactly twice only occurs when a specific pattern is present wherein after we hire the first candidate the next candidate hired is the candidate ranked \(n\) and so we make no additional hire beyond the second.

So our first candidate must have rank \(i \leq n - 1\). Let’s call this event \(E_i\), and we know that this event has probability \(\frac{1}{n}\) for any value of \(i\).

If the best candidate (rank \(n\)) is at position \(j\), we are interested in the cases where positions \(2, 3, \dots, j-1\) have ranks that are less than the rank of candidate \(1\). Call this event \(F\). Given that event \(E_i\) has occurred, event \(F\) only occurs when the first candidate interviewed out of the \(n - i\) candidates with ranks \(i+1, i+2, \dots, n\) is the best candidate. So the conditional probability of \(F\) occurring given that \(E_i\) has occurred is \(\frac{1}{n-1}\).

So the total probability that we hire exactly twice is

\[\begin{split} \sum\limits_{i=1}^{n-1} P(E_i) \cdot P(F) & = \sum\limits_{i=1}^{n-1}\frac{1}{n} \cdot \frac{1}{n-i} \\ & = \frac{1}{n} \sum\limits_{i=1}^{n-1} \frac{1}{n - i} \\ & = \frac{1}{n} \left( \frac{1}{n-1} + \frac{1}{n-2} + \cdots + \frac{1}{1} \right) \\ \end{split}\]

The summation conveniently takes the recognizable form of a harmonic series, and so we can reduce the result to \(\frac{1}{n}H_{n-1}\) were \(H_{n-1}\) is the \(n\)th harmonic number.