1
$\begingroup$

I am studying algorithms from CLRS book. I try to understand the difference between

  • probability of hiring the $i$th person out of $n$ and
  • probability of hiring the $i$th person out of $n$ persons based on ranks.

Using the normal probability, we know the answer for the first one is $\frac{1}{n-i}$ and the answer for the second is given as $\frac{1}{i}$ in the CLRS book. I am unable to understand the concept here. How is it $\frac{1}{i}$? Can it also be $\frac{1}{n-i}$ taking in ranks, too?

We have n candidates lined up for an intertiew.Once a candidate is interviewed he is given a rank.If the rank of the next candidate is greater the current greatest rank he is hired and his rank is now the current greatest rank

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i
$\endgroup$
  • $\begingroup$ Is there a particular algorithm this is about? What does "based on ranks" mean exactly? $\endgroup$ – Raphael Sep 29 '12 at 11:58
  • $\begingroup$ @Raphael i have edited the question and included the algorithm. I wanted to know why can't we use the notation 1/(n-i) to calculate the probability of a person being hired $\endgroup$ – Sid Sep 29 '12 at 19:05
3
$\begingroup$

When people are interviewed following a random arrival order, the probability of candidate $i$ being hired is $\frac{1}{i}$. This follows from the fact that, assuming a random order of arrivals, for each $i$ the group of initial $i$ candidates is random, so that the $i$-th candidate has probability $\frac{1}{i}$ of being chosen which happens if he/she is better qualified than the previous $i-1$ candidates.

Now instead of considering a random order on the arrivals, impose your own order, based on ranks: the first candidate is the less qualified, and the last one is the one which is the best overall. In this case, if the group is made of $n$ candidates, numbering them from $0$ to $n-1$ you get for the $i$th candidate a probability of being hired which is $\frac{1}{n-i}$, since candidates are now arriving on the basis of their ranks, and the $i$-th candidate is always better qualified than the previous $i-1$.

This is why you want to permute the group of candidates: so that no particular input elicits the worst case behavior associated to the permutation in which candidates are sorted by rank.

CLRS explains how this minor modifications allows you to hire, on average, $O(\lg n)$ candidates instead of $n$ in the worst case. Note that this is only a probabilistic guarantee: nothing prevents the pseudorandom generator, if you are really unlucky, from generating the permutation corresponding to the candidates sorted by rank. But we do not expect this to happen frequently: the probability of generating the bad permutation is only $\frac{1}{n!}$ which, for large $n$, is very low.

$\endgroup$
  • $\begingroup$ if the candidates are coming in the order of ranks imposed by us isn't it obvious we are going to hire the last person which gives us a probability of 1 when i=n and 0 for all others? $\endgroup$ – Sid Sep 29 '12 at 7:41
  • $\begingroup$ @Sid: yes of course. This is just for explaining how the algorithm's behavior changes depending on the actual input permutation. You requested an explanation related to the particular permutation in which the candidates arrive sorted by rank; but if you know in advance the ranks you do not interview n-1 candidates and hire directly the n-th candidate obviously ;-) Assuming you do not know in advance the situation, the analysis tells you what to expect on average and why it is better than in the worst case. $\endgroup$ – Massimo Cafaro Sep 29 '12 at 7:53
  • $\begingroup$ Sorry, I forgot to mention the following important fact: remember that you are not the algorithm, so you would assume directly the n-th candidate, but the algorithm as no way of inspecting in advance the ranks (no statement in the pseudocode does this): therefore you actually assume n candidates, each with probability 1/(n-i) when running the algorithm if the input is that particular bad permutation. $\endgroup$ – Massimo Cafaro Sep 29 '12 at 8:06
  • $\begingroup$ You do a lot of restating the problem, but apparently it helped the OP... $\endgroup$ – Raphael Sep 29 '12 at 12:03
  • $\begingroup$ @Raphael, I am not really restating the problem: see chapter 5 of CLRS for the exact definition of the problem. I am just explaining to the OP the reasoning behind the derivation of the complexity in the average and worst cases. $\endgroup$ – Massimo Cafaro Sep 29 '12 at 14:04

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.