Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Each score is in [0,1]? –  Neal Young Nov 29 '12 at 21:52
    
It doesn't really matter, you can always scale it so that it's in $[0,1]$. –  Yuval Filmus Nov 29 '12 at 22:49

2 Answers 2

up vote 16 down vote accepted

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

share|improve this answer
2  
Thanks! I'll remember to try the multivariate Gaussian approximation next time. –  Yuval Filmus Nov 30 '12 at 0:25
5  
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 Nov 30 '12 at 1:22
    
@NealYoung: What I wrote was not very clear. I edited my post to clarify what I meant. –  Yury Nov 30 '12 at 4:17
1  
@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 Nov 30 '12 at 13:47
1  
Ah I see. at least algebraically, all it rests on is the pairwise independence of Z and each $X_i$. very cool. –  Suresh Venkat Nov 30 '12 at 16:56

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.

share|improve this answer
2  
Thanks. That's a very neat argument! –  Yuval Filmus Nov 30 '12 at 0:27
    
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 Dec 3 '12 at 21:09
    
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 Dec 3 '12 at 23:14
    
Ah - I guess you're right. I subtracted inside the square root and that's how I got my figure. –  Yuval Filmus Dec 4 '12 at 0:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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