0
$\begingroup$

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions.

However, for Exercise question 5.2-2 my solution deviates from the one given in the reference and mine seems be correct. I am still not satisfied with the reasoning of my solution though. Here it goes.

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

My solution: 1. First candidate is always going to be hired so all we have to do is to calculate the probability that only one candidate is hired from the remaining n - 1 candidates. So I divided it into n - 1 cases where like

case 1: If the second candidate is hired. (other than the first one only)

case 2: If the third candidate is hired.

and so on..

Now the probability of case 1:

1(anyone will be hired) * 1/2(the probability of this being more than the first) * 2/3(probability of this not being the highest till now) * 3/4 * 4/5 * 5/6.... * (n-1)/n = 1/n

Similarly for case 2: 1 * 1/2 * 1/3(must be highest till now) *1/4... * (n - 1)/n = 1/2n

case 3: 1/3n and n-1 th case : 1/(n-1)*n

so my answer is

1/n * (1 + 1/2 + 1/3 + 1/4... 1/(n-1))

but the solutions pdf mentions

(2^n - n - 1)/n!

My solution seems correct for n == 3 where the answer should be 3/6. So can anyone please validate this approach and guide me if this is wrong.

$\endgroup$
0
$\begingroup$

In fact, your result is correct and that reference solution is wrong!

Here is where that reference solution goes wrong.

Since we view the candidate ranking as reading an random permutation, this is equivalent to the probability that a random permutation is a decreasing sequence followed by an increase, followed by another decreasing sequence.

A permutation that leads to hiring of two candidates if and only if the first candidate is not the best candidate and is better than all others candidates that come before the best candidate. There is no requirement of sequences being decreasing or increasing.

(There is a minor typo in your case 2. You meant 3/4 instead of 1/4.)

I would not say your reasoning is fully correct yet, though you have got the correct result, since I have not found a natural way to explain rigorously your way of computing the probability of each case by a product of probabilities. I am even more far away from being certain that your reasoning is wrong. It looks like you shared my feeling as well.

There are better or more rigorous ways to produce the correct result. I will let you think about it.

$\endgroup$
  • $\begingroup$ Thanks, this has been itching my brain for a while. But now this is troublesome. I wonder how much of that reference is correct. If you can point me to another reference solution that would be very helpful. $\endgroup$ – Siddharth Shishulkar Nov 3 '18 at 9:55
  • $\begingroup$ Here is a reference solution. Suppose the first candidate is ranked $i$, which happens with probability $1/n$. To hire exactly one more candidate is equivalent to require the best candidate should be the first one coming to interview among all $n-i$ candidates that are better than $i$ (who are ranked $i+1, i+2, \cdots,n$). That happens with a probability $1/(n-i)$. So we have $1/n\cdot1/(n-i)$. Summation over $i, 1\le i\lt n$ will give the result. $\endgroup$ – Apass.Jack Nov 3 '18 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.