Exercise 5.2.2

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

You hire twice when you first hire is the candidate with rank and all the candidates with rank come after the candidate with rank .There are better suited candidates and the probability of the best one coming first is (we can ignore the other candidates and they don't affect the probability). Thus, the probability for hiring twice if your first candidate has rank is:

$$\Pr{T_i} = \frac{1}{n}\frac{1}{n-i}$$

The first part reflects the probability of picking that particular candidate out of .

The probability to hire twice is:

$$\Pr{T} = \sum_{i=1}^{n-1}\Pr{T_i}

= \sum_{i=1}^{n-1}\frac{1}{n}\frac{1}{n-i}

= \frac{1}{n} \sum_{i=1}^{n-1}\frac{1}{i}

= \frac{1}{n} \Big(\lg(n-1) + O(1)\Big)$$