Upper bounds on $\mathbb{P}[X \leq k]$ when $k > \mathbb{E}[X]$, for binomial rand. variable $X$

Question

Let $X$ be a binomial random variable, $X \sim \mathcal{B}(n,p)$.

When $k > \mathbb{E}[X] = np$, are there no Hoeffding-like bounds on the probability $\mathbb{P}[X \leq k]$?

When $k \leq \mathbb{E}[X]$, it is easy to find that $\mathbb{P}[X \leq k] \leq \exp\{-2n(p-k/n)^2\}$, by means of the Hoeffding bound. When $k > \mathbb{E}[X]$, the Hoeffding bound no longer applies (as far as I can understand), essentially beacuse this would mean taking $t<0$ in the usual formulation of the bound, which is not allowed.

I understand that Markov's bound should still apply, and that $\mathbb{P}[X \leq k] \equiv \sum_{j=0}^k \binom{n}{j} p^j (1-p)^{n-j}$. I also note that when $p=1/2$, the distribution is symmetric, but this is not the case for general $p$. This said, are there no tighter bounds?

Answer 1

Update: This again provides lower bounds for $\mathbb{P}[X \leq k]$, rather than upper bounds, as suspected. Thus it's not substantially different from using Hoeffding's bound. I'm leaving the question here for the record, but have un-marked it as the answer.

---

A friend gave me the answer (and permission to post it here).

The starting point is Arora and Barak's [Arora, S., Barak, B. (2009). Computational Complexity: A Modern Approach. Alemanha: Cambridge University Press, Appendix A.2.4] formulation of a Chernoff bound for a binomial distribuiton*:

Theorem A.14: Let $X_1$, $X_2$, $\ldots$, $X_n$ be mutually independent random variables over $\{0,1\}$, and let $\mu = \sum_{i=1}^n \mathbb{E}(X_i)$. Then, for every $\delta > 0$, $$\mathrm{Pr}[\sum_{i=1}^n X_i \geq (1+\delta)\mu] \leq \left[\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right]^\mu$$ $$\mathrm{Pr}[\sum_{i=1}^n X_i \leq (1-\delta)\mu] \leq \left[\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right]^\mu$$

...and the corollary stated immediately after:

Corollary A.15: Under the above conditions, for every $c>0$, $$\mathrm{Pr}\left[\left\vert\sum_{i=1}^n X_i - \mu\right\vert \geq c\mu \right] \leq 2 \cdot e^{-\mathrm{min}\{c^2/4,c/2\} \mu}$$

Then just note that $\{x: \; \vert{x-\mu}\vert \geq c\mu\} \supseteq \{x:\; x-\mu \geq c\mu\}$. Letting $S_n = \sum_i X_i$ for ease of notation, we have that

$$\mathrm{Pr}[S_n-\mu \geq c\mu] \leq \mathrm{Pr}[\vert{S_n-\mu}\vert \geq c\mu] \leq e^{-\Omega(\mu)}.$$

For any $k > \mathbf{E}[S_n] \equiv \mu \equiv np$, $k$ can be written as $\mu+c\mu$ with $c > 0$. Therefore, the bound above applies.

---

* I'm not super sure on how Theorem A.14 relates to the usual formulation of Chernoff bounds, based on the moment generating function, or if it is a misnomer. I would appreciate any comments clarifying this point.

Answer 2

You could get some sort of bound from the Berry-Esseen theorem, which gives bounds on $\sup_x |F(x)-\Phi(x)|$, where $F(x)$ is the CDF of an appropriately scaled sum and $\Phi(x)$ is the Normal CDF. The bound is of the form $C\kappa/\sqrt{n}$, where $\kappa$ is the scaled kurtosis and $C$ is a universal constant. The Wikipedia page has links to papers with bounds on $C$ and with variation of the result. I don't have a feeling for how sharp these bounds are in the binomial setting.