Prove that in the array $P$ in procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least $1 - \frac{1}{n}$.

Let $X_i$ be an indicator random variable for the event that $P[i]$ is not unique. $P[i]$ being unique means that it holds a different value from the values found in $P[1, \dots, i-1]$ which has at most $i-1$ distinct elements and so we have $Pr\{X_i\} = E[X_i] \leq \frac{i-1}{n^3}$. Let $X$ be a random variable for the event that $P$ holds at least one duplicate element. This gives us

$$X = (X_1 \cup X_2 \cup \cdots \cup X_n) = X_1 + X_2 + \cdots + X_n \textrm{.}$$

We can then calculate

$$\begin{split} E[X] &= E \left[ \sum\limits^n_{i=1} X_i \right] \\ &= \sum\limits^n_{i=1} E[X_i] \\ & \leq \sum\limits^n_{i=1} \frac{i - 1}{n^3} \\ &= \frac{1}{n^3} \sum\limits^{n-1}_{i=0} i \\ &= \frac{1}{n^3} \frac{(n-1)n}{2} \textit{ //(arithmetic series)} \\ &= \frac{n-1}{2n^2} \\ & \leq \frac{1}{n} \\ \end{split}$$

And so the probability that all elements in $P$ are unique is $E[\bar{X}] = 1 - E[X] \geq 1 - \frac{1}{n}$.