2
$\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.

* Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ According to this solution, the answer is the same as yours. $\endgroup$
    – Swa1n Suen
    Commented Jul 10, 2020 at 5:08

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 3, 2018 at 9:55
  • 2
    $\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$
    – John L.
    Commented Nov 3, 2018 at 10:53
  • $\begingroup$ @JohnL. How is the probability $\frac{1}{n - i}$? Note that not all of the numbers $1, 2, ..., i - 1$ are between $i$ and $n$. Some of them might be after $n$. If all of them were before $n$, then you could say the probability is $\frac{1}{n - i}$. $\endgroup$
    – Emad
    Commented Jul 25, 2021 at 7:50
0
$\begingroup$

I think there is some problem in your approach, you are considering events in which there will be hire at 2nd or 3rd or 4th .......or n-1th place but what you didn't consider is the fact that ii should be the only hire other than the 1st one.

Improve this answer
$\endgroup$

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