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.
Lemma (Anti-concentration of upper tail)
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) $$
Lemma (Anti-concentration of lower tail)
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
$$ H(\alpha) := -\alpha \log \alpha - (1 - \alpha) \log (1 - \alpha) $$
and the inequality:
$$ 8k(1 - k/m) \le 2k \quad \text{(since } \beta(1 - \beta) \le 1/4 \text{ for } \beta \in (0,1) \text{)} $$
Next, we bound the KL divergence:
$$ \begin{aligned} D_{\text{KL}}\left(\frac{k}{m} \| p\right) &= \frac{k}{m} \log \frac{k}{mp} + \left(1 - \frac{k}{m} \right) \log \frac{1 - \frac{k}{m}}{1 - p} \\ &\le \left(p - \frac{t}{m} \right) \log\left(1 - \frac{t}{pm} \right) + \left(1 - p + \frac{t+1}{m} \right) \log \left(1 + \frac{t+1}{(1 - p)m} \right) \\ &\le \left(p - \frac{t}{m} \right) \left(-\frac{t}{pm} \right) + \left(1 - p + \frac{t+1}{m} \right) \cdot \frac{t+1}{(1 - p)m} \\ &= -\frac{t}{m} + \frac{t^2}{pm^2} + \frac{t+1}{m} + \frac{(t+1)^2}{(1 - p)m^2} \\ &\le \frac{1}{m} + \frac{(t+1)^2}{m^2} \left(\frac{1}{p} + \frac{1}{1 - p} \right) \end{aligned} $$
Using $p \le 1/2$ the tail bound simplifies to:
$$ \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) $$