Proof. We say that \(x,y\in X\) if they hash to the same bin. Let random variable \(C\) denote the number of collisions, and random variable \(M\) denote the maxload. The bins to which distinct \(x,y\in X\) map to under \(\ULH\) are pairwise-independent, so \[\begin{equation}\label{eq:lhs7ez} \mathop{\mathrm{\mathbb{E}}}[C] = \frac{1}{2}\binom{n}{2}. \end{equation}\] On the other hand \[\begin{equation}\label{eq:rhs7ez} \mathop{\mathrm{\mathbb{E}}}[C\mid M=m] = \binom{m}{2}+\binom{n-m}{2}. \end{equation}\] Observe that is a quadratic in \(m\), and in particular convex as a function of \(m\). Combining , and applying Jensen’s Inequality gives: \[\begin{align} \frac{1}{2} \binom{n}{2}&\ge \mathop{\mathrm{\mathbb{E}}}\left[\binom{M}{2}+\binom{n-M}{2}\right]\label{eq:RHSthing}\\ &\ge \binom{\mathop{\mathrm{\mathbb{E}}}[M]}{2}+\binom{n-\mathop{\mathrm{\mathbb{E}}}[M]}{2}\label{eq:jensen}. \end{align}\] Let \(\mu\) denote \(\mathop{\mathrm{\mathbb{E}}}[M]\). Simplifying gives \[\mu^2-\mu n+n^2/4-n/2\le 0.\] Applying the quadratic formula gives \[\mu \le n/2 + \sqrt{n/2}.\]