6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Do you have a response to the answers on this page? $\endgroup$ Jan 13, 2022 at 1:18

3 Answers 3

7
$\begingroup$

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}}. $$

$\endgroup$
2
  • $\begingroup$ Just noting, this proves the same bound mentioned in Iosif Pinelis' answer, expressed a bit differently here. $\endgroup$
    – usul
    Sep 23, 2021 at 20:25
  • $\begingroup$ @usul yes, and the proof is the same, just self-contained $\endgroup$ Sep 24, 2021 at 6:51
10
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Why the downvote? Is there anything wrong with this answer? $\endgroup$ Sep 24, 2021 at 14:58
4
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.