# Why is this true for large enough n?

\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?

-

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).$$
@Leo: That gets added to $-3\ln(n)$ to give $-2\ln(n)$. – user17762 Dec 9 '11 at 23:20