I need a lower bound for the upper tail of $X \sim Bin(n,\beta^m)$. In general concentration inequalities (Hoeffding) give us upper bounds for $\mathbb{P}(X>t)$ (if $t > \mathbb{E}[X]$), but no lower bounds. Are there any references that you can point me towards where lower bounds for those probabilities are shown.

My concrete setting is that $\beta \approx 1/2$ or larger by a small amount. If I then assume $t \in [ \mathbb{E}[X],\mathbb{E}[X]+\epsilon]$ ($\epsilon >0$ small), I would expect to encounter behaviour of the form $\mathbb{P}(X>t)\geq C_1 \exp(-C_2 t^{C_3})$.


Wikipedia has this one, on the page for Binomial Distribution:

$$\Pr(X \ge k) =F(n-k;n,1-p)\geq \frac{1}{(n+1)^2} \exp\left(-nD\left(\frac{k}{n}\left|\right|p\right)\right) \quad\quad\mbox{if }p<\frac{k}{n}<1$$

See also my question where I conjecture an even tighter bound.

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