6
$\begingroup$

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$?
  • 0
    @Moron: the inequality seems to work, but does not ;-)2011-03-03

1 Answers 1

7

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

  • 0
    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...2011-03-07