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.

  • 1
    $\begingroup$ 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)? $\endgroup$ – David Benson-Putnins Nov 26 '15 at 4:46
  • $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.