Is there an entropy proof for bounding a weighted sum of binomial coefficients? 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.
 A: 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}}.
$$
A: 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.

A: 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$.
