2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 26, 2015 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
    Commented Nov 26, 2015 at 6:40

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .