5.3-5

Prove that in the array P in procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least 1 - 1/n.

The algorithm is as below
PERMUTE-BY-SORTING(A)
1 n = A.length
2 letP(1...n) be a new array
3 for i = 1 to n
4 P [i] = $RANDOM(1, n^3)$
5 sortA, using P as sort keys
For P[] to unique lets go through one element at a time. For the first since no element is there in the Array P the probability is 1 bcoz it is the first element.The probability of picking the first element $1/n^3$ since every element has a fair chance in a set of $n^3$
For the second element we have to make sure we don't pick the first element again.
for example consider the tossing of a coin the probability of not getting a tail is 1 -(1/2)(probability of getting a head).
Similarly the probability of not getting the first element when we pick the first element is $1 - (1/n^3)$ (we might tempted in doing 1/n^3-1 but this is wrong since we are not selecting element from a smaller set of $1..n^3$ all elements will be there)
Similarly the probability of not getting the first and second element when we pick the third element is $1 - (1/n^3+1/n^3)$
Let us Indicator random variables $E_i$ be the event in which we pick unique prioroty for element i and E the indicator random variable for all elements of array p $$ P\{E\}=P\{E_1 \cap E_2 \cap .. \cap E_n\} = P\{E_2|E_1\} P\{E_1\} P\{E_3|E_2 \cap E_1\} P\{E_2 \cap E_1\} .... P\{E_n|E_n-1 \cap E_n-2... \cap E_1\} p\{E_n \cap E_n-1.... \cap E_1\}$$ $$ P\{E\} = 1 . 1 - (1/n^3) . 1 - (1/n^3+1/n^3) ... 1 - (n-1/n^3) $$
the last term has to be n - 1 because we would want substract the probability of not getting n-1 terms while picking the last element.
$$ P\{E\} = 1 . (n^3 - 1)/n^3 . (n^3 - 2)/n^3 ... (n^3 - n+1)/n^3 $$ $$ > 1 . (n^3 - n)/n^3 . (n^3 - n)/n^3 ... (n^3 - n)/n^3 $$ $$ > (1 - 1/n^2) . (1 - 1/n^2) . (1 - 1/n^2) ... (1 - 1/n^2) $$ even $1 > (1 - 1/n^2)$ $$ > (1 - 1/n^2)^n $$ The above equation look in the form of $(1+x)^n$ the binomial theorem has an expansion see Wikipedia or any other source. $$(1+x)^n ={n \choose 0} x^0 + {n \choose 1} x^1+{n \choose 2} x^2+....+{n \choose n} x^n$$ $$ (1 - 1/n^2)^n = 1 - 1/n+(n-1/2n^2)-(n-1/6n^2)+...$$ $$ > 1-1/n$$ even for odd and even powers of n