1
$\begingroup$

Suppose that we randomly drop n3/2 balls into n bins. Give an upper bound on the expectation of the maximum number of balls in any bin.

I have seen somewhat similar questions but no good answer for this kind of problem. First, we know that the expected number of balls in any bin is n1/2. Then, I think we need to use Chernoff bounds but that's the part I am struggling with. Usually, we have to set a δ but I don't know equal to what.

Thanks for your help.

$\endgroup$
2
  • 1
    $\begingroup$ Let $Y$ be the maximum number of balls in any bin. Chernoff like arguments give you $P(Y \ge k) \le f(k)$ for some $f$. Since $Y\ge 0$ surely, you can now use $\mathbb{E}[Y] = \sum_{k \ge 1} P(Y \ge k) \le \sum_{k\ge 1} f(k)$ for an upper bound on the expectation. $\endgroup$ Mar 20, 2017 at 2:50
  • $\begingroup$ Thanks for your answer, I follow what you are doing. My question is how do we find that f(k) ? @stochasticboy321 $\endgroup$
    – TedMosby
    Mar 20, 2017 at 2:56

1 Answer 1

1
$\begingroup$

Let $X_i$ be the # of balls in the $i$th bin and $X = \max\{X_1, X_2, \cdots, X_n\}$. We have $$ \mathsf{E}(X) = \sum_{i \geq 1} \Pr(X \geq i) \leq \sum_{i > 2n^{1/2} + 9\ln n} \Pr(X \geq i) + 2n^{1/2} + 9\ln n $$ and for $i > 2n^{1/2} + 9\ln n$, \begin{align} \Pr(X \geq i) &= \Pr(X_1 \geq i\ \lor\ X_2 \geq i\ \lor\ \cdots\ \lor\ X_n \geq i) \\ &\leq \sum_{j = 1}^n \Pr(X_j \geq i) \\ &\leq \sum_{j=1}^n \mathsf{exp}\left( - \frac{i - n^{1/2}}{3}\right) \\ &\leq \sum_{j=1}^n \mathsf{exp}\left(-3\ln n\right) \\ &= \frac{1}{n^2} \end{align} where

  • $X_j \sim \mathsf{Binomial}~(n^{3/2}, \frac{1}{n})$ and $\mathsf{E}(X_j) = \sqrt{n}$;

  • the first inequality uses the union bound;

  • the second inequality uses a loose form of Chernoff bound: $$ \Pr(X \geq (1 + \delta)\mu) \leq \mathsf{exp}(-\frac{\delta\mu}{3}) \quad\text{for}\ \delta > 1 $$ Therefore, $$ \sum_{i > 2n^{1/2} + 9\ln n} \Pr(X \geq i) \leq n^{3/2} \cdot \frac{1}{n^2} = \frac{1}{\sqrt{n}} $$ implying an upper bound $$ \mathsf{E}(X) \leq 2\sqrt{n} + \frac{1}{\sqrt{n}} + 9 \ln n $$

$\endgroup$
3
  • $\begingroup$ Very neat thank you ! $\endgroup$
    – TedMosby
    Mar 21, 2017 at 2:35
  • $\begingroup$ Sorry but I don't understand where $2n^{1/2}+9 ln n$ comes from $\endgroup$
    – Rob
    Mar 23, 2017 at 18:24
  • $\begingroup$ @Rob It is a value selected such that when we apply the Chernoff bound, the formula would not be too tedious. $\endgroup$
    – PSPACEhard
    Mar 24, 2017 at 1:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .