# Tight binomial left tail bound

Let $X \sim \text{Bin}(n,p)$. Wikipedia claims $$\mathbf P[X \leq (p-\epsilon)n ] \leq e^{ - 2 \epsilon^2 n}.$$ This follows from Hoeffding's inequality (https://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case).

Is this tight? Could a more clever application of Hoeffding, or perhaps Chernoff bounds yield a larger exponent? I am trying to optimize a constant in a calculation and would like the best bound possible.

• Are you just trying to optimize the constant multiplier 2 in the exponent, or do you need to improve the behavior in $\epsilon$ or $n$ to make it worth doing (which I don't think either of are really possible)? – David Benson-Putnins Nov 26 '15 at 4:46
• I am taking $\epsilon \to 0$ and would like an exponent that is larger than $2p^2$. So either something larger than $2$ or larger order than $\epsilon^2$ would be good. – Matthew Junge Nov 26 '15 at 6:40

This is tight, at least when $p=\frac12$. You simply need to approximate $\log\big({n \choose \frac{n}{2}-\varepsilon n} \frac1{2^{n}}\big)$ using Stirling's formula and you'll see that the leading coefficient is indeed $-2\varepsilon^2 n$.