Throw n balls independently and uniformly into n bins

Throw \(n\) balls independently and uniformly into \(n\) bins. Let \(X_i\) be the number of balls in bin \(i\), and let \(X=\max_i X_i\). You may use linearity of expectation and Markov’s inequality. You may not use Chernoff bounds, moment-generating functions, or the known \(\Theta(\log n/\log\log n)\) maximum-load theorem. (a) Prove that \(\mathbb{E}[X_i(X_i-1)]=1-1/n\) for each \(i\). (b) Prove that \(\mathbb{E}[X_i^2]\le 2\). (c) Let \(Y\) be the number of bins with \(X_i\ge\sqrt n\). Using Markov’s inequality on a random variable built from the \(X_i\) (specify it), prove that \(\Pr[X\ge\sqrt n]=O(1/\sqrt n)\) for \(n\ge 1\), or give any bound of the form \(\Pr[X\ge\sqrt n]\le c/\sqrt n\) with an explicit constant \(c\). (d) Deduce that \(\mathbb{E}[X]=O(\sqrt n)\). (Use \(X\le n\) always, and split the expectation according to whether \(X\ge\sqrt n\).)

\(X_i(X_i-1)\) counts ordered pairs of distinct balls in bin \(i\).