[Solved]: Hiring one person out of n — rank and probablity

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.