1
$\begingroup$

$ \begin{align*} \Pr[\text{bin } i \text{ has at least } k \text{ balls}] &\leqslant \left( \frac{e}{k} \right)^k = \left( \frac{e \ln \ln n}{3 \ln n} \right)^{\frac{3 \ln n}{\ln \ln n}} \\ &\leqslant \exp \left( \frac{3 \ln n}{\ln \ln n} (\ln \ln \ln n - \ln \ln n) \right) \\ &= \exp \left( - 3 \ln n + \frac{3 \ln n \cdot \ln \ln \ln n}{\ln \ln n} \right) \end{align*} $

When $n$ is large enough, $ \Pr[\text{bin } i \text{ has at least } k \text{ balls}] \leqslant \exp ( - 2 \ln n ) = \frac{1}{n^2}. $

This was found in this set of lecture notes.

Can anyone explain why the last step ("When n is large enough..") is true?

1 Answers 1

2

All you need is that for large enough $n$, we have $3\ln (\ln(\ln(n))) < \ln(\ln(n))$ which is true since for large enough $m$, $3 \ln(m) < m$ and take $m = \ln(\ln(n))$. For instance, take $n \geq e^{e^5}$.

Since $3\ln (\ln(\ln(n))) < \ln(\ln(n))$, we have $-3 \ln(n) + \frac{3 \ln (n) \ln (\ln(\ln(n)))}{\ln(\ln(n))} < -3 \ln(n) + \ln(n) = - 2 \ln(n).$

Hope it is clear now.

  • 0
    @Leo: That gets added to $-3\ln(n)$ to give $-2\ln(n)$.2011-12-09