<p>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})$.</p>

<p>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.</p>

<p>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|$.</p>

<p>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.</p>

<p>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 [<a href="http://www.ic.unicamp.br/~celio/peer2peer/math/balls-into-bins.pdf" rel="noreferrer">Thm. 1</a>]. (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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-12-03T21:09:26.250Z
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})$.
Yuval Filmus
CC BY-SA 3.0
2012-12-03T23:14:45.657Z
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?
Neal Young
CC BY-SA 3.0
2012-12-04T00:35:34.933Z
Ah - I guess you're right. I subtracted inside the square root and that's how I got my figure.
Yuval Filmus
CC BY-SA 3.0
2012-11-29T23:16:03.743Z
2012-11-30T16:37:39.853Z
2012-11-30T16:37:39.853Z
Neal Young
<p><strong>Answer:</strong> $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.</p>

<p>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$ <em>is</em> 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.$$</p>

<p>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$.</p>

<blockquote>
  <p><strong>Problem.</strong> 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}}$.</p>
</blockquote>

<p><strong>Answer:</strong> $\Theta\left(\frac{1}{\sqrt{\log n}}\right)$.</p>

<p><strong>Informal Proof.</strong> 
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 &gt; 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}.$$</p>

<p>Note that</p>

<ul>
<li><p>$\Phi(\gamma_i)$ are uniformly and independently distributed on $[0,1]$, </p></li>
<li><p>$\Phi(\gamma_{\mathrm{max}})$ is the smallest among $\Phi(\gamma_i)$,</p></li>
<li><p>$\Phi(\gamma_{\mathrm{sec-max})}$ is the second smallest among $\Phi(\gamma_i)$.</p></li>
</ul>

<p>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)}.
$$</p>

<p>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}}.$$ </p>

<p><strong>QED</strong></p>

<p>We get that 
\begin{align}
\mathbb{E}[{X_{\mathrm{max}} - X_{\mathrm{sec-max}}}] &amp;= \mathbb{E}[{Y_{\mathrm{max}} - Y_{\mathrm{sec-max}}}] \\
&amp;= \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}</p>

<blockquote>
  <p>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.$$</p>
</blockquote>

CC BY-SA 3.0
2012-11-30T00:25:49.877Z
Thanks! I'll remember to try the multivariate Gaussian approximation next time.
Yuval Filmus
CC BY-SA 3.0
2012-11-30T01:22:22.573Z
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.
Neal Young
CC BY-SA 3.0
2012-11-30T04:17:34.680Z
@NealYoung: What I wrote was not very clear. I edited my post to clarify what I meant.
Yury
CC BY-SA 3.0
2012-11-30T08:24:10.943Z
Huh.  So if I have variables with negative pairwise correlation, I can add a single new random variable (independent of the original variables) to each of them, and the sums will be independent.  That is a neat trick.  I'm still not sure I understand it :-).
Neal Young
CC BY-SA 3.0
2012-11-30T13:47:45.857Z
@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$.
Yury
CC BY-SA 3.0
2012-11-30T16:56:29.687Z
Ah I see. at least algebraically, all it rests on is the pairwise independence of Z and each $X_i$. very cool.
Suresh Venkat
CC BY-SA 3.0
2012-11-30T22:11:33.160Z
@Yury, is there a reference/pointer to the fact that you used? Is this Like Neal I am not sure I "get" it.
Chandra Chekuri
CC BY-SA 3.0
2012-11-30T22:16:32.603Z
@Chandra, do you mean the fact that we can add a Gaussian $Z$ to all r.v.? I prove it in my post. I don't think that there is any reference for it — it's just a basic geometric fact.
Yury
CC BY-SA 3.0
2012-12-04T23:16:47.083Z
One point to make is that, in general, two random variables can have covariance 0 and still be dependent.  To get the independence in this proof, Yuri is relying specifically on the distributions (Gaussian) of the $X_i$'s.  [[reference](http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Correlations_and_independence)].  Also, for the record, here is a [related post](http://math.stackexchange.com/questions/89030/expectation-of-the-maximum-of-gaussian-random-variables) on math.stackexchange.
Neal Young
CC BY-SA 3.0
2015-07-19T16:53:15.703Z
This argument now appears (with attribution) in an EC'14 paper: http://dl.acm.org/citation.cfm?id=2602829.
Yuval Filmus
CC BY-SA 3.0
2015-12-09T18:00:20.550Z
Can you really approximate the binomial by a normal far in the right tail? I think you'd make a huge error as the normal approximation is good only relatively close to the mean.
A.S.
CC BY-SA 3.0
2015-12-09T18:31:23.823Z
A.S., in this problem $n$ is fixed and $m$ goes to infinity. Note that we use the normal approximation in the range that depends only on $n$ (and not on $m$).
Yury
CC BY-SA 3.0
2012-11-29T23:03:37.853Z
2012-11-30T23:21:30.430Z
2012-11-30T23:21:30.430Z
Yury
<p>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 <em>fixed</em> $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.</p>

<p>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}}$?</p>

<p>More generally, suppose that each ball is associated with a non-negative <em>score</em> 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}}$?</p>

CC BY-SA 3.0
2012-11-29T21:52:40.180Z
Each score is in [0,1]?
Neal Young
CC BY-SA 3.0
2012-11-29T22:49:01.037Z
It doesn't really matter, you can always scale it so that it's in $[0,1]$.
Yuval Filmus
<reference-request><pr.probability>
Balls and Bins analysis in the $m \gg n$ regime: gaps
Yuval Filmus
# Balls and Bins analysis in the $m \gg n$ regime: gaps

(Asked by: username_0 on 2012-11-29)

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}}$?

**Tags:** reference-request, pr.probability

> **Comments:**
> **username_1**: Each score is in [0,1]?  
> **username_0**: It doesn't really matter, you can always scale it so that it's in $[0,1]$.  

---

## 2 answers

### Answer by username_2 on 2012-11-29. Score: 22 | Accepted answer

**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}}.$$

**QED**

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.$$

> **Comments:**
> **username_0**: Thanks! I'll remember to try the multivariate Gaussian approximation next time.  
> **username_1**: username_2, 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.  
> **username_2**: @NealYoung: What I wrote was not very clear. I edited my post to clarify what I meant.  
> **username_1**: Huh.  So if I have variables with negative pairwise correlation, I can add a single new random variable (independent of the original variables) to each of them, and the sums will be independent.  That is a neat trick.  I'm still not sure I understand it :-).  
> **username_2**: @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$.  
> **username_3**: Ah I see. at least algebraically, all it rests on is the pairwise independence of Z and each $X_i$. very cool.  
> **username_4**: @username_2, is there a reference/pointer to the fact that you used? Is this Like Neal I am not sure I "get" it.  
> **username_2**: @Chandra, do you mean the fact that we can add a Gaussian $Z$ to all r.v.? I prove it in my post. I don't think that there is any reference for it — it's just a basic geometric fact.  
> **username_1**: One point to make is that, in general, two random variables can have covariance 0 and still be dependent.  To get the independence in this proof, Yuri is relying specifically on the distributions (Gaussian) of the $X_i$'s.  [[reference](http://en.wikipedia.org/wiki/Multivariate_normal_distribution#Correlations_and_independence)].  Also, for the record, here is a [related post](http://math.stackexchange.com/questions/89030/expectation-of-the-maximum-of-gaussian-random-variables) on math.stackexchange.  
> **username_0**: This argument now appears (with attribution) in an EC'14 paper: http://dl.acm.org/citation.cfm?id=2602829.  
> **username_5**: Can you really approximate the binomial by a normal far in the right tail? I think you'd make a huge error as the normal approximation is good only relatively close to the mean.  
> **username_2**: username_5, in this problem $n$ is fixed and $m$ goes to infinity. Note that we use the normal approximation in the range that depends only on $n$ (and not on $m$).  

---

### Answer by username_1 on 2012-11-29. Score: 14

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](http://www.ic.unicamp.br/~celio/peer2peer/math/balls-into-bins.pdf)]. (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.

> **Comments:**
> **username_0**: 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})$.  
> **username_1**: 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?  
> **username_0**: Ah - I guess you're right. I subtracted inside the square root and that's how I got my figure.  

---

