Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-max}}$ be the second heaviest bin. Roughly speaking, $X_i - X_j \sim N(0,2m/n)$, and so we expect $|X_i - X_j| = \Theta(\sqrt{m/n})$ for any two fixed $i,j$. Using a union bound, we expect $X_{\max} - X_{\min} = O(\sqrt{m\log n/n})$; presumably, we can get a matching lower bound by considering $n/2$ pairs of disjoint bins. This (not completely formal) argument leads us to expect that the gap between $X_{\max}$ and $X_{\min}$ is $\Theta(\sqrt{m\log n/n})$ with high probability.

I am interested in the gap between $X_\max$ and $X_{\mathrm{sec-max}}$. The argument outlined above shows that $X_\max - X_{\mathrm{sec-max}} = O(\sqrt{m\log n/n})$ with high probability, but the $\sqrt{\log n}$ factor seems extraneous. Is anything known about the distribution of $X_\max - X_{\mathrm{sec-max}}$?

More generally, suppose that each ball is associated with a non-negative score for each bin, and we are interested in the total score of each bin after throwing $m$ balls. The usual scenario corresponds to scores of the form $(0,\ldots,0,1,0,\ldots,0)$. Suppose that the probability distribution of the scores is invariant under permutation of the bins (in the usual scenario, this corresponds to the fact that all bins are equiprobable). Given the distribution of the scores, we can use the method of the first paragraph to get a good bound on $X_{\max} - X_{\min}$. The bound will contain a factor of $\sqrt{\log n}$ that comes from a union bound (via the tail probabilities of a normal variable). Can this factor be reduced if we're interested in bounding $X_{\max} - X_{\mathrm{sec-max}}$?

  • $\begingroup$ Each score is in [0,1]? $\endgroup$
    – Neal Young
    Nov 29, 2012 at 21:52
  • $\begingroup$ It doesn't really matter, you can always scale it so that it's in $[0,1]$. $\endgroup$ Nov 29, 2012 at 22:49

2 Answers 2


Answer: $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.

Applying a multidimensional version of the Central Limit Theorem, we get that the vector $(X_1,\dots, X_n)$ has asymptotically multivariate Gaussian distribution with $$\mathrm{Var}[X_i] = m\left(\frac{1}{n} - \frac{1}{n^2}\right),$$ and $$\mathrm{Cov}(X_i, X_j) = -m/n^2.$$ We will assume below that $X$ is a Gaussian vector (and not only approximately a Gaussian vector). Let us add a Gaussian random variable $Z$ with variance $m/n^2$ to all $X_i$ ($Z$ is independent from all $X_i$). That is, let $$ \begin{pmatrix} Y_1\\Y_2\\ \vdots\\Y_n \end{pmatrix} = \begin{pmatrix} X_1+Z\\X_2+Z\\ \vdots\\X_n +Z \end{pmatrix}. $$ We get a Gaussian vector $(Y_1, \dots, Y_n)$. Now each $Y_i$ has variance $m/n$: $$\mathrm{Var}[Y_i] = \mathrm{Var}[X_i] + \underbrace{2\mathrm{Cov}(X_i,Z)}_{=\, 0}+\mathrm{Var}[Z] = m/n,$$ and all $Y_i$ are independent: $$\mathrm{Cov}(Y_i, Y_j) = \mathrm{Cov}(X_i, X_j) + \underbrace{\mathrm{Cov}(X_i,Z) + \mathrm{Cov}(X_j,Z)}_{=\, 0} +\mathrm{Cov}(Z, Z) = 0.$$

Note that $Y_i - Y_j = X_i - X_j$. Thus our original problem is equivalent to the problem of finding $Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}$. Let us first for simplicity analyze the case when all $Y_i$ have variance $1$.

Problem. We are given $n$ independent Gaussian r.v. $\gamma_1,\dots, \gamma_n$ with mean $\mu$ and variance $1$. Estimate the expectation of $\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}$.

Answer: $\Theta\left(\frac{1}{\sqrt{\log n}}\right)$.

Informal Proof. Here is an informal solution to this problem (it's not hard to make it formal). Since the answer does not depend on the mean, we assume that $\mu = 0$. Let $\bar\Phi(t) = \Pr[\gamma > t]$, where $\gamma\sim{\cal N}(0,1)$. We have (for moderately large $t$), $$\bar\Phi(t)\approx \frac{1}{\sqrt{2\pi}t} e^{-\frac{1}{2}t^2}.$$

Note that

  • $\Phi(\gamma_i)$ are uniformly and independently distributed on $[0,1]$,

  • $\Phi(\gamma_{\mathrm{max}})$ is the smallest among $\Phi(\gamma_i)$,

  • $\Phi(\gamma_{\mathrm{sec-max})}$ is the second smallest among $\Phi(\gamma_i)$.

Thus $\Phi(\gamma_{\mathrm{max}})$ is close to $1/n$ and $\Phi(\gamma_{\mathrm{max}})$ is close to $2/n$ (there is no concentration but if we don't care about constants these estimates are good enough; in fact, they are even pretty good if we care about constants — but that needs a justification). Using the formula for $\bar\Phi(t)$, we get that $$ 2\approx \bar\Phi(\gamma_{\mathrm{sec-max}})\left/\bar\Phi(\gamma_{\mathrm{max}})\right. \approx e^{\frac{1}{2}\left(\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2\right)}. $$

Thus $\gamma_{\mathrm{max}}^2 - \gamma_{\mathrm{sec-max}}^2$ is $\Theta(1)$ w.h.p. Note that $\gamma_{\mathrm{max}}\approx \gamma_{\mathrm{sec-max}} = \Theta(\sqrt{\log n})$. We have, $$\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}\approx \frac{\Theta(1)}{\gamma_{\mathrm{max}} + \gamma_{\mathrm{sec-max}}} \approx \frac{\Theta(1)}{\sqrt{\log n}}.$$


We get that \begin{align} \mathbb{E}[{X_{\mathrm{max}} - X_{\mathrm{sec-max}}}] &= \mathbb{E}[{Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}}] \\ &= \sqrt{\mathrm{Var}[Y_i]} \times\mathbb{E}[{\gamma_{\mathrm{max}} - \gamma_{\mathrm{sec-max}}}] = \Theta\left(\sqrt{\frac{m}{n\log n}}\right). \end{align}

The same argument goes through when we have arbitrary scores. It shows that $$\mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{sec-max}}] = c\, \left. \mathbb{E}[X_{\mathrm{max}}- X_{\mathrm{min}}]\right/\log n.$$

  • 2
    $\begingroup$ Thanks! I'll remember to try the multivariate Gaussian approximation next time. $\endgroup$ Nov 30, 2012 at 0:25
  • 5
    $\begingroup$ Yury, you wrote "Let us add a Gaussian vector $Z$ with variance $m/n^2$ to all $X_i$. We get a Gaussian vector $(Y_1, \dots, Y_n)$. Now each $Y_i$ has variance $m/n$ and all $Y_i$ are not correlated... Note that $Y_i - Y_j = X_i - X_j$." Can you expand on this part? Is $Z_i = Z_j$? If the $X_i$'s are dependent, and the $Z_i$'s are independent (or uniformly the same), how can the $Y_i$'s be independent? (Seems like a neat trick but I don't understand it.) Thanks. $\endgroup$
    – Neal Young
    Nov 30, 2012 at 1:22
  • 1
    $\begingroup$ @NealYoung, yes, if we have variables $X_1,\dots,X_n$ with negative pairwise correlation and all covariances $\mathrm{Cov}(X_i,X_j)$ are equal, then we can add a single new random variable $Z$ to all $X_i$ such that the sums are independent. Also, if the variables have positive correlation and again all covariances $\mathrm{Cov}(X_i,X_j)$ are equal then we can subtract a single r.v. $Z$ from all of them so that all the differences are independent; but now $Z$ is not independent from $X_i$ but rather $Z=\alpha (X_1 + \dots+X_n)$ for some scaling parameter $\alpha$. $\endgroup$
    – Yury
    Nov 30, 2012 at 13:47
  • 1
    $\begingroup$ Ah I see. at least algebraically, all it rests on is the pairwise independence of Z and each $X_i$. very cool. $\endgroup$ Nov 30, 2012 at 16:56
  • 1
    $\begingroup$ This argument now appears (with attribution) in an EC'14 paper: dl.acm.org/citation.cfm?id=2602829. $\endgroup$ Jul 19, 2015 at 16:53

For your first question, I think you can show that w.h.p. $X_{\max}-X_{\textrm{sec-max}}$ is $$o\left(\sqrt{\frac{m}{n}\frac{\log^2\log n}{\log n}}\right).$$ Note that this is $o(\sqrt{m/n})$.

Compare your random experiment to the following alternative: Let $X_1$ be the maximum load of any of the first $n/2$ buckets. Let $X_2$ be the maximum load of any of the last $n/2$ buckets.

On consideration, $|X_1-X_2|$ is an upper bound on $X_{\max}-X_{\mathrm{sec-max}}$. Also, with probability at least one half, $|X_1-X_2| = X_{\max}-X_{\mathrm{sec-max}}$. So, speaking roughly, $X_{\max}-X_{\mathrm{sec-max}}$ is distributed similarly to $|X_1-X_2|$.

To study $|X_1-X_2|$, note that with high probability $m/2\pm O(\sqrt m)$ balls are thrown into the first $n/2$ bins, and likewise for the last $n/2$ bins. So $X_1$ and $X_2$ are each distributed essentially like the maximum load when throwing $m' = m/2\pm o(m)$ balls into $n' = n/2$ bins.

This distribution is well-studied and, luckily for this argument, is tightly concentrated around its mean. For example, if $m' \gg n\log^3 n$, then with high probability $X_1$ differs from its expectation by at most the quantity displayed at the top of this answer [Thm. 1]. (Note: this upper bound is, I think, loose, given Yuri's answer.) Thus, with high probability $X_1$ and $X_2$ also differ by at most this much, and so $X_{\max}$ and $X_{\mathrm{max-sec}}$ differ by at most this much.

Conversely, for a (somewhat weaker) lower bound, if, for any $t$, say, $\Pr[|X_1-X_2| \ge t] \ge 3/4$, then $\Pr[X_{\max}-X_{\textrm{sec-max}} \ge t]$ is at least $$\Pr\big[|X_1-X_2| \ge t ~\wedge~ X_{\max}-X_{\textrm{sec-max}} = |X_1-X_2|\big]$$ which (by the naive union bound) is at least $1 - (1/4) - (1/2) = 1/4.$ I think this should give you (for example) the expectation of $X_{\max}-X_{\textrm{sec-max}}$ within a contant factor.

  • $\begingroup$ Looking at Thm. 1, the difference from the expectation is $O(\sqrt{(m/n) \log \log n})$, and not what you wrote. That's still much better than $O(\sqrt{(m/n) \log n})$. $\endgroup$ Dec 3, 2012 at 21:09
  • $\begingroup$ By Thm. 1 (its 3rd case), for any $\epsilon>0$, with probability $1-o(1)$, the maximum in any bin (m balls in n bins) is $$\frac{m}{n} +\sqrt{\frac{2m\log n}{n}}\sqrt{1-(1\pm\epsilon) \frac{\log\log n}{2\log n}}.$$ By my math (using $\sqrt{1-\delta} = 1 - O(\delta)$), the $\pm\epsilon$ term expands to an additive absolute term of $$O(\epsilon) \sqrt{\frac{m\log n}{n}}~\frac{\log\log n}{\log n} ~=~O(\epsilon) \sqrt{\frac{m}{n}~\frac{\log^2\log n}{\log n}}.$$ What am I doing wrong? $\endgroup$
    – Neal Young
    Dec 3, 2012 at 23:14
  • $\begingroup$ Ah - I guess you're right. I subtracted inside the square root and that's how I got my figure. $\endgroup$ Dec 4, 2012 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.