In the book Randomized Algorithms from Motwani and Raghavan, it is stated in page 44 that

$$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$

This inequality is used to prove the theorem "With probability at least $1 - \frac{1}{n}$, no bin has more than $k^\ast = (e \ln n)/ \ln \ln n$ balls in it".

This problem arises from a balls and bins game. The proof starts like this.

Consider first the case $m = n$, and let $X_j(k)$ denote the event that bin $j$ has $k$ or more balls in it. We concentrate on analyzing $X_1(k)$. The probability that bin 1 receives exactly $i$ balls is $$\binom{n}{i} \left( \frac{1}{n} \right)^i \left( 1 - \frac{1}{n} \right)^{n-i} \leq \binom{n}{i} \left( \frac{1}{n} \right)^i \leq \left(\frac{ne}{i} \right)^i \left( \frac{1}{n} \right)^i = \left( \frac{e}{i} \right)^i.$$ The second inequality results from an upper bound for binomial coefficients (for reference). Thus $$\mathbb{P}[X_1(k)] \leq \sum_{i = k}^n \left( \frac{e}{i} \right)^i \leq \left( \frac{e}{k} \right)^k \left( 1 + \frac{e}{k} + \left( \frac{e}{k} \right)^2 + \cdots \right).$$ Let $k^\ast = \lceil(e \ln n)/ \ln \ln n \rceil$. Then, $$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$

However, I don't understand how the authors can go so fast on the second inequality.

I tried to developp $k^\ast$ and simplify it a bit, I tried to use that $x = \exp(\ln x)$, I tried to reproduce the proof of theorem 7.1.1 here but I just could not arrive to the conclusion.

Could someone explain this to me?

Edit: Actually, this inequality might be wrong. I plotted it in mathematica, and here is the result:

Mathematica's plot

If the inequality was correct, the plot should be below 0, and this is clearly not the case. Even for greater $n$, the function seems to be increasing. I was to lazy too compute the derivative and check it out formally. (The discontinuity may come from the ceiling approximation, I did not check it out. I tried with $k = \frac{e \ln n}{\ln \ln n}$ and the plot was continous).

What do you think? Am I wrong, or is it possible that there is an error in the book?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.