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})$.
Best Answer
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.