Say that \(X\sim Binomial(n,p)\). The Chernoff Bound that I like to use states: \(\forall \delta\in (0,1)\), \[\Pr[X>(1+\delta)np]\leq exp(-np \frac{\delta^2}{3}).\] This is great. But today I faced the following situation: \(p=\frac{1}{n}\), and I wanted to figure out the largest \(\delta\) such that this bound is still “high probability”. I, trusting in my Chernoff bound went and plugged in some large values of \(\delta\) to see what happens. You may have already realized my mistake. The above formula is only valid for \(\delta < 1\).

In general, the formula is really this: \(\forall \delta > 0,\) \[\Pr[X>(1+\delta)np]\leq exp(-np \frac{\delta^2}{\delta+2}).\] Ah, now it becomes clear what was wrong with what I was doing above.

Anyways, if you use the correct formula you find that \(X\) with high probability is at most \(\log n\). This is actually correct. Good.