In this blog post I’ll deposit two useful anti-concentration bounds for the binomial distribution that one could use for a variety of situations in algorithmic analysis, lower bounds and beyond.
Let $X_1,\dots,X_m$ be i.i.d. Bernoulli random variables with parameter $p$. If $p \leq 1/4$, then for any $t \geq 0$, we have:
$$ \Pr\left[\sum_{i=1}^m X_i \ge mp + t\right] \ge \frac{1}{4} \exp\left(-\frac{2t^2}{mp}\right) $$
Proof:
Proof pending.
Let $X_1,\dots,X_m$ be i.i.d. Bernoulli random variables with parameter $p$. Then, if $p \leq 1/2$:
$$ \Pr\left[\sum_{i=1}^m X_i \le mp - t\right] \ge \frac{1}{\sqrt{2m}} \exp\left(-1 - \frac{8t^2}{mp}\right) $$
Proof:
We start by first proving the following bound:
$$ \Pr\left[\sum_{i=1}^m X_i \le mp - t\right] \ge \frac{1}{\sqrt{2m}} \exp\left(-m \cdot D_{\text{KL}}\left(\frac{\lfloor mp - t \rfloor}{m} \,\middle\|\, p\right)\right) $$
where
$$ D_{\text{KL}}(p\|q) := p \log \frac{p}{q} + (1 - p) \log \frac{1 - p}{1 - q} $$
Let $k := \lfloor mp - t \rfloor$. Then:
$$ \begin{aligned} \Pr\left[\sum_{i=1}^m X_i \le k \right] &= \sum_{i=0}^{k} {m \choose i} p^i (1 - p)^{m - i} \\ &\ge {m \choose k} \exp\left(-m \left( \frac{k}{m} \log \frac{1}{p} + \left(1 - \frac{k}{m} \right) \log \frac{1}{1 - p} \right) \right) \\ &= {m \choose k} \exp\left(-m \left( D_{\text{KL}}\left(\frac{k}{m} \| p\right) - H\left(\frac{k}{m}\right) \right) \right) \\ &\ge \frac{1}{\sqrt{8m \cdot \frac{k}{m} \left(1 - \frac{k}{m} \right)}} \exp\left(-m \cdot D_{\text{KL}}\left(\frac{k}{m} \| p\right) \right) \\ &\ge \frac{1}{\sqrt{2m}} \exp\left(-m \cdot D_{\text{KL}}\left(\frac{k}{m} \| p\right) \right)\end{aligned} $$
We used the bound:
$$ {n \choose \alpha n} \ge \frac{\exp(n H(\alpha))}{\sqrt{8n\alpha(1 - \alpha)}} $$
with binary entropy function