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}\).