Is there an entropy proof for bounding a weighted sum of binomial coefficients?

Question

Given a probability $p \in (0,1)$ and parameter $\alpha \in (0,1)$, is there an entropy-based proof which yields a good upper bound for the sum $$\sum_{\ell = 0}^{\alpha n} \binom{n}{\ell}p^\ell(1-p)^{n-\ell}$$ when $n$ is large?

When $p = 1/2$, there is very simple proof (for example, see section 3.1 of this paper) which upper bounds the above quantity by $$2^{(H(\alpha) - 1)n}$$ when $H(\cdot)$ denotes the binary entropy function.

Is there a proof using similar techniques which gives a bound for the more general sum above (which can be interpreted as the CDF of a binomial distribution with parameter $p$)?

I'd also be interested in other proofs for bounds on the above sum. The appropriate bound has already noted in this answer, but doesn't sketch out a proof establishing this result.

Answer 1

Yes, if $\alpha<p$ (if $\alpha>p$, the sum is almost 1). To see this, write $$ \sum_{\ell = 0}^{\alpha n} \binom{n}{\ell}p^\ell(1-p)^{n-\ell}\leqslant t^{-\alpha n}(pt+(1-p))^n $$ for every $t\in (0,1]$. Choose a positive $t=t_0$ for which RHS is minimal possible, taking the logarithmic derivative equal to 0 we get $-\alpha/t_0+p/(pt_0+1-p)=0$, $-\alpha p t_0-\alpha(1-p)+pt_0=0$, $pt_0(1-\alpha)=\alpha(1-p)$, $t_0=\frac{\alpha(1-p)}{p(1-\alpha)}$. We see that if $\alpha\leqslant p$, this $t_0$ is indeed in $(0,1]$, thus we get the upper bound $\theta^n$, where $$ \theta=\frac{p^\alpha(1-p)^{1-\alpha}}{\alpha^\alpha (1-\alpha)^{1-\alpha}}. $$

Answer 2

By the Chernoff–Hoeffding theorem, the sum in question is $\le\exp(-nD(a||p))$ for $a\le p$, where $a:=\alpha$ and $$D(a||p):=a\ln\frac ap+(1-a)\ln\frac{1-a}{1-p},$$ the Kullback–Leibler divergence between the distributions of Bernoulli random variables with parameters $a$ and $p$. In particular, this gives your bound for $p=1/2$.

On the other hand, if $a>p$ then, by the the law of large numbers, the sum in question converges to $1$ as $n\to\infty$. This convergence is actually exponentially fast -- because, if $a>p$, then $1-(\text{your sum})$ is $\le\exp(-nD(a||p))$ and $D(a||p)>0$.

Answer 3

As you said, the sum is $\Pr[X \leq \alpha n]$ where $X$ is drawn from a Binomial distribution with $n$ trials having $p$ probability of success. Bounds on this sum (for $\alpha < p$) are called "tail bounds", "concentration inequalities", etc. These bounds are proven for many settings, especially sums of independent random variables, of which Binomials are the nicest special case.

A typical proof approach, which some of us call the Chernoff method, looks like this: if $X = \sum_{i=1}^n Y_i$ where each $Y_i$ is an i.i.d. Bernoulli$(p)$, then

\begin{align} \Pr[X \leq k] &= \Pr[e^X \leq e^k] \\ &\leq e^{-k} \mathbb{E} e^X & \text{Markov's inequality} \\ &= e^{-k} \prod_{i=1}^n \mathbb{E} e^{Y_i} & \text{Indpendence} \\ &= e^{-k} \left(pe + (1-p)\right)^n \\ &\dots \end{align} etc. I omitted a detail -- we scale both $X$ and $k$ by some factor $\lambda$, which we choose later -- and stopped the analysis early, but that's how many proofs start.

Starting points:

• https://en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds
• https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
• https://en.wikipedia.org/wiki/Chernoff_bound
• https://en.wikipedia.org/wiki/Concentration_inequality
• Concentration Inequalities: A Nonasymptotic Theory of Independence by Stephane Boucheron, Gabor Lugosi, Pascal Massart.