2
$\begingroup$

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?

$\endgroup$

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.