In \(\textsc{Hire-Assistant}\), assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?
Hiring exactly twice means we update our current best candidate exactly two times: once for the first candidate (who we always hire), and once more for exactly one subsequent candidate.
Let’s rank the candidates from 1 (worst) to \(n\) (best). For us to hire exactly twice, the best-qualified candidate (rank \(n\)) must appear at some position \(k \geq 2\), and when they arrive, they must be better than our current best. More importantly, for this to be only the second hire, no candidate between positions 2 and \(k-1\) can trigger a hire.
Building the Solution
Consider the best candidate appearing at position \(k\) where \(2 \leq k \leq n\). For exactly two hires to occur:
- The best candidate is at position \(k\) (probability \(1/n\))
- Among the first \(k-1\) positions, position 1 must have the highest rank (otherwise we’d hire someone between positions 2 and \(k-1\))
Given that we have \(k-1\) candidates in positions 1 through \(k-1\), the probability that position 1 has the maximum rank among them is \(1/(k-1)\).
Using the law of total probability, we sum over all possible positions \(k\) for the best candidate:
\[\begin{align*} \Pr\{\text{hire exactly twice}\} &= \sum_{k=2}^{n} \Pr\{\text{best at position } k\} \cdot \Pr\{\text{position 1 best in } 1..k-1\} \\ &= \sum_{k=2}^{n} \frac{1}{n} \cdot \frac{1}{k-1} \\ &= \frac{1}{n} \sum_{k=2}^{n} \frac{1}{k-1} \\ &= \frac{1}{n} \sum_{j=1}^{n-1} \frac{1}{j} \\ &= \frac{1}{n} H_{n-1} \end{align*}\]where \(H_{n-1} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n-1}\) is the \((n-1)\)-th harmonic number.
Final Answer
\[\Pr\{\text{hire exactly twice}\} = \frac{H_{n-1}}{n} \approx \frac{\ln n}{n}\]For large \(n\), this probability decreases as \(\Theta(\ln n / n)\).