Prove that in the array \(P\) in procedure \(\textsc{Permute-By-Sorting}\), the probability that all elements are unique is at least \(1 - 1/n\).
Recall that \(\textsc{Permute-By-Sorting}\) assigns each element \(A\)[\(i\)] a random priority \(P\)[\(i\)] chosen uniformly from \(\{1, 2, \ldots, n^3\}\), then sorts the array based on these priorities. For the algorithm to work correctly, all priorities should be distinct.
We’ll use a counting argument combined with the union bound (Boole’s inequality) to show that collisions are unlikely.
Let \(E_{ij}\) be the event that \(P\)[\(i\)] = \(P\)[\(j\)] for \(i < j\). We want to find the probability that all priorities are unique, which is the complement of the probability that at least two priorities collide:
\[\Pr\{\text{all unique}\} = 1 - \Pr\left\{\bigcup_{1 \le i < j \le n} E_{ij}\right\}\]For any pair \(i, j\) with \(i \neq j\), the probability that \(P\)[\(i\)] = \(P\)[\(j\)] is:
\[\Pr\{E_{ij}\} = \Pr\{P[i] = P[j]\}\]Since \(P\)[\(i\)] and \(P\)[\(j\)] are chosen independently and uniformly from \(\{1, 2, \ldots, n^3\}\):
\[\Pr\{P[i] = P[j]\} = \sum_{k=1}^{n^3} \Pr\{P[i] = k\} \cdot \Pr\{P[j] = k\} = \sum_{k=1}^{n^3} \frac{1}{n^3} \cdot \frac{1}{n^3} = n^3 \cdot \frac{1}{n^6} = \frac{1}{n^3}\]By Boole’s inequality (the union bound), the probability of at least one collision is at most the sum of individual collision probabilities:
\[\Pr\left\{\bigcup_{1 \le i < j \le n} E_{ij}\right\} \le \sum_{1 \le i < j \le n} \Pr\{E_{ij}\}\]The number of pairs \((i, j)\) with \(i < j\) is \(\binom{n}{2} = \frac{n(n-1)}{2}\). Therefore:
\[\Pr\{\text{at least one collision}\} \le \frac{n(n-1)}{2} \cdot \frac{1}{n^3} = \frac{n(n-1)}{2n^3} = \frac{n-1}{2n^2}\]
For \(n \ge 1\):
\[\frac{n-1}{2n^2} < \frac{n}{2n^2} = \frac{1}{2n} < \frac{1}{n}\](The last inequality holds because \(1/(2n) < 1/n\) is equivalent to \(n < 2n\), which is always true for \(n > 0\).)
Therefore:
\[\begin{align*} \Pr\{\text{all unique}\} &= 1 - \Pr\{\text{at least one collision}\} \\ &\ge 1 - \frac{1}{n} \end{align*}\]This completes the proof. ∎
The probability that all priorities are distinct is at least \(1 - 1/n\). For large \(n\), this approaches 1 very quickly:
- For \(n = 10\): probability \(\ge 0.9\)
- For \(n = 100\): probability \(\ge 0.99\)
- For \(n = 1000\): probability \(\ge 0.999\)
This shows that choosing priorities from the range \([1, n^3]\) makes collisions very unlikely. The \(n^3\) factor provides a “safety margin” that grows cubically with the input size.