Hiring one person out of n — rank and probablity

Question

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

Answer 1

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.