Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question
3  
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
add comment

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.