Difficulty to prove this inequality in Binomial Coefficient.

Question

This inequality is found in a book titled as Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, in Chapter 3, during explaining Occupancy Problems, to see the book click here PP. 43-44

suppose we have m := balls. n := bins. each ball is placed in a bin chosen independently and uniformly at random.

$EV_j(k) :=$ denote the event that bin j has k or more balls in it.

The probability that bin 1 receives exactly i balls is: $$\binom {n}{i} ({\frac{1}{n}})^i ({1 - \frac{1}{n}})^{n-i} \leq \binom {n}{i} ({\frac{1}{n}})^i \leq ({\frac{ne}{i}})^i ({\frac{1}{n}})^i = ({\frac{e}{i}})^i $$ so far so good, Now, let's get the upper bound of the probability of the event $\Pr [EV_j(k)]$.

$\Pr [EV_j(k)] \leq \sum_{i=k}^{n}({\dfrac{e}{i}})^i \leq ({\dfrac{e}{k}})^k (1 + \dfrac{e}{k} + ({\dfrac {e}{k}})^2 + ... ) \leq ({\dfrac{e}{k^*}})^{k^*} \times \dfrac {1}{1 - e/k^*} \leq n^{-2} $

for $k^* = \lceil (3 \ln n)/ \ln \ln n \rceil $

First inequality is because Boole's Inequality, I have a difficult time to deal with inequality in 2nd, 3rd and 4th, so If there is a property to help me to understand this inequality would be very grateful.

Answer 1

Here's the details for the second inequality: \begin{align*} \operatorname{Pr}(\mathcal E_j(k)) \le \sum_{i=k}^n \left(\frac ei\right)^i \le \sum_{i=k}^n \left(\frac ek\right)^i \le \sum_{i=k}^\infty \left(\frac ek\right)^i = \sum_{i=0}^\infty \left(\frac ek\right)^{i+k} = \left(\frac ek\right)^k \sum_{i=0}^\infty \left(\frac ek\right)^i = \left(\frac ek\right)^k \frac1{1-\frac ek} \end{align*} The third inequality is not in the book you linked. Rather, at this point, having proved the above inequality for all $k$, they apply it for one specific $k$. They announced their intention to do this at the start of the paragraph:

Let us try now to make a statement of the form "with very high probability, no bin receives more than $k$ balls", for a suitably chosen $k$.

(Emphasis mine.) What they actually write, instead of your third inequality, is

Let $k^\ast = \lceil(3\ln n)/\ln\ln n\rceil$. Then

$$ \operatorname{Pr}(\mathcal E_j(k^\ast)) \le \left(\frac e{k^\ast}\right)^{k^\ast} \frac1{1-\frac e{k^\ast}} \le n^{-2} $$

Note that $k^\ast$ is on the far left here too.

So that leaves the fourth inequality, $\le n^{-2}$. They chose $k^\ast$ so that this inequality would hold (which is why they call it "suitably chosen"). Here's a partially-worked-out approach to this inequality. We have $$ \frac{k^\ast}{e} \ge \frac{k^\ast}{3} \ge \frac{\ln n}{\ln\ln n} $$ Now, $x\mapsto x\ln x$ is an increasing function for $x>\frac1e$; we have $\frac{k^\ast}{e} \ge \frac1e$ because $k^\ast$ is a positive integer, and we have $\frac{\ln n}{\ln\ln n}\ge 1\ge\frac1e$ provided that $n\ge 3$ (so that both numerator and denominator are positive). Applying this increasing function to both sides, we get $$ \frac{k^\ast}{e} \ln \frac{k^\ast}{e} \ge \frac{\ln n}{\ln\ln n} \ln \frac{\ln n}{\ln\ln n} = \ln n \left(1 - \frac{\ln\ln\ln n}{\ln\ln n}\right) $$ Rearranging, $$ \left(\frac{k^\ast}{e}\right)^{k^\ast} \ge n^{e(1 - \ln\ln\ln n / \ln\ln n)} $$ For large enough $n$, the exponent on the RHS will be strictly greater than 2, so we get what we want. (I leave the detailed estimates to you. Note that the factor I haven't considered, $(1-\frac e{k^\ast})^{-1}$, is less than 2, so it can be defeated by the other factor.)

Also, note that in the statement of the theorem on the next page, the authors write $e$ where above they had written 3. So don't be too certain that all the constants are entirely correct. (I'm also pretty sure they didn't think too hard about how large $n$ had to be for their estimates to be correct. It's typical in this kind of topic to be chiefly concerned with the asymptotics as $n\to\infty$, so they might just be ignoring the issue.)