CLRS 5.2-2 HIRE-ASSISTANT

http://hi.baidu.com/fredyl/blog/item/5aa4d6309c93a848ad4b5f73.html

Question

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

Answer

We make three observations:

1 Candidate 1 is always hired.

2 The best candidate ,i.e.,the one whose rank is n , is always hired.

3 If the best candidate is candidate 1, then that is the only candidate hired.

Therefore, in order for HIRE-ASSISTANT to hire exactly twice, candidate 1 must have rank i<=n-1 and all candidates whose ranks are i+1, i+2,...,n-1 must be interviewed after the candidate whose rank is n.

Let Ei be the event in which candidate 1 have rank i, clearly, P(Ei) = 1/n for any given value of i.

Letting j denote the position in the interview order of the best candidate , let F be the event in which candidate 2,3 ,j-1 have ranks strictly less than the rank of candidate 1, Given that event Ei has occurs,event F occurs when the best candidate is the first one interviewed out of the n-i candidates whose ranks are i+1, i+2,...n. Thus, P(F | Ei) = 1/(n-i).

Our final event is A, which occurs when HIRE-ASSISTANT hires exactly twice.Noting that the events E1,E2,...En are disjoint, we have

A = F && ( E1 || E2 || ... || En) = (F && E1) || (F && E2) || ... || (F && En)

P(A) = 1/n *(1+1/2 +1/3 +... + 1/(n-1))