PROBABILITY HIRE- ASISTANT [closed]

Question

Here is an algorithm for the HIRE-ASSISTANT problem.

HIRE-ASSISTANT(n)
best <- 0
for i <- 1 to n do
      if candidate[i] is better than candidate[best]
          best <- i
          hire candidate i

Now some 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.

Now the problem is what is the probability of hiring twice?

My approach:

Now before nth rank candidate, I can interview any number of candidates as I want to but the order of their rank is fixed.Therefore for i candidates being interviewed before nth rank candidate=C(n-1,i)*(n-i-1)! total cases are possible.So varying i=1 from n-1 and summing and dividing by total possibilities that are n! I calculate the answer, but it does not match with the standard answer so I need help in finding what is wrong?

Answer 1

The probability to hire At least twice is (n-1)/n.
Assuming you have a random permutation of the candidates, you hire only one candidate if and only if the first candidate is also the best. The probability for it to happen is 1/n. Thus, the probability that it won't happen (and you will hire twice or more) is 1-1/n = (n-1)/n

To hire exactly twice:

• Choose a location (not first) for the 'best': n-1 possibilities. Let the place be i
• For each such place, choose i-1 candidates to be placed before the best: Choose(n-1,i-1)
• The first from these i-1 candidates is the best out of them. Need to permute the rest: (i-2)!
• In addition, still need to permute for (n-i-1) candidates after the 'best': (n-i-1)!.

This gives us the total number of 'valid' permutations that exactly two candidates are hired are:

f(n) = Sum[ Choose(n-1,i-1)*(i-2)!*(n-i-1)! | for i=2,...,n]

And the probability is simply P=f(n)/n!

Answer 2

Actually, in the 4th bullet we need to permute (n-i) candidates so the final answer reduces to P = 1/n*H_(n-1) where H_(n-1) is the (n-1)^th harmonic number.