# Inequality on balls/bins with nested logs

Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that

$$\left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ?$$

This is from p. 44 of Motwani and Raghavan, Randomized Algorithms, where they're talking about ball/bin probabilities. The $\left(\frac{e}{x}\right)^x$ is motivated but the $k$ just comes out of nowhere. Ignoring that for the moment, I don't see the derivation of the inequality; even assuming the the 3 is really an approximation for $e$, and throwing out the $\log\log n$... and the geometric series, I get (letting $k^{*}= e \log n$):

$$\left(\frac{e}{k^{*}}\right)^{k^{*}}\approx n^{-\log\log n} \le n^{-2}$$ for $n \ge e^{e^2}$.

But I changed things quite a bit, and this is quite a large constant ($\approx 3^{27}$).

So two questions:

• how does one derive the full inequality?
• why that particular $k$?
-
The last factor you can forget. Even $e^k$ is not important against $k^{-k}$. Take the "equation" $k^{-k} \approx n^{-2}$ and make things easier but applying log a few times. Guess which term is most important and try to get successively more precise estimates. –  Fabian Mar 2 '11 at 20:20
@Fabian: Why don't you make that an answer? Seems like it will work... –  Aryabhata Mar 2 '11 at 22:39
@Moron: the inequality seems to work, but does not ;-) –  Fabian Mar 3 '11 at 0:00

The inequality does not hold. If you set $n=5.6 \times 10^{6}$ (close to $e^{e^e}$) with $k=17$, you will find that the left hand side is larger than $3.4 \times 10^{-14}$ and the right hand side is smaller than $3.2 \times 10^{-14}$. To see why the inequality is wrong and why $k=\lceil \frac{4 \log n}{\log \log n} \rceil$ works, read on:

To get a "good" value for $k$, you want that the inequality becomes asymptotically $n\to\infty$ and equality. That is how you derive the particular form. Taking log of your inequality, we get (i switched the sign of the equation because I rather like positive numbers) $$L= k (\log k -1) +\log(1- e/k) \geq 2 \log n .$$

The most important term (for $n,k \to \infty$) is $k\log k$. So we would like to have $$k\sim \frac{2 \log n}{\log k}.$$ This can be solved iteratively. The first approximation is $k_0 = 2 \log n$. We set this approximation in the right hand side and obtain $k_1 = 2 \log n/ \log \log n$ (up to an irrelevant additive term $\log 2$ in the denominator). This is already almost the estimate, changing the 2 to 3 and the ceiling function are needed to have some space and make the inequality valid (and not only the expressions asymptotically equal).

Now, let us check the inequality and set $k= c \log n /\log \log n$ ($c$ we will determine in the end). We obtain $$L= \frac{c \log n}{\log \log n} ( \log c + \log \log n - \log \log \log n -1) + \log (1- e \log \log n /c \log n).$$ We will use that $(\log c -1) > 0$ (for $c>e$), $(\log \log \log n / \log \log n) \leq 1/e$ (with the maximum attained for $n=e^{e^e}$), and $\log (1- e \log \log n /c \log n)>\log(c-1)-\log c$ (with the minimum at $n=e^e$). Thereby, we can show that $$L \geq c (1- 1/e) \log n + \log (c-1) - \log c .$$

The lowest value of $c$ for which we can hope that the inequality is always fulfilled is given by $c(1-1/e) =2$, i.e., $c= 2e/(e-1) \approx 3.2$. Assuming that $n>e$ such that $\log n >1$, we can further bound the expression $$L \geq [c (1-1/e) + \log (c-1) - \log c ] \log n \geq 2 \log n$$ if $c\gtrsim 3.67$.

-
Thanks. The statement is unmotivated and the inequality is so deeply nested itself that I didn't expect a simple answer. I got 3.5E10^-14 for the left hand side, but the general form of the argument works for me. The complexity of the argument for this inequality seems beyond what is expected in the text (a derivation of Markov's inequality immediately follows). –  Mitch Mar 6 '11 at 19:13
My bad, I forgot to take the ceiling function (in fact in the whole post). But nevertheless it should show how one can get this kind of estimates without knowing more about the problem. –  Fabian Mar 6 '11 at 20:48
@Mitch: asymptotics strikes back. Close to $e^{e^e}$ is a point where the authors inequality does not hold... I changed the text in the answer. –  Fabian Mar 6 '11 at 20:58
I considered that there might be nearby values below n^-2 but I'm working with a windows calculator, which doesn't do differentiation/plotting/etc (how hard could that be for the a summer intern at MS or Apple to develop?). –  Mitch Mar 6 '11 at 22:10
I have the feeling that the authors of the book new the asymptotics and then tried to find a number ($c$ in my post) such that the inequality holds. However, they thought that small values of $n$ are important and then the asymptotics kicks in (that's when you chose $c=3$ just plotting the function for $n$ up to 100). However, the term $e^k$ (not covered in the asymptotics) is important for small $n$ and becomes subdominant against $k^k$ only for $n> e^{e^e}$. So they also should have checked around this value... –  Fabian Mar 7 '11 at 11:21