Estimating a partial sum of weighted binomial coefficients

Question

There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$:

$$ \sum_{k=0}^{\alpha n}\binom{n}{k} = 2^{(H(\alpha) + o(1))n}$$

where $H(\alpha) = -\alpha\log_2(\alpha) - (1-\alpha)\log_2(1-\alpha)$ is the binary entropy function.

My question is whether there exists a similar estimate when we weight the $k$-th binomial coefficient by $\lambda^k$ for some $\lambda > 0$. That is, I would like to estimate the following sum:

$$ \sum_{k=0}^{\alpha n} \binom{n}{k} \lambda^k $$

Answer 1

Expanding on the previous answers. I'm taking $\lambda$ and $\alpha$ to be constants which do not vary as $n\to\infty$.

If $α<λ/(λ+1)$ then the sum is within a constant of the last term. In fact the largest terms are approximately in geometric progression so you can get it quite accurately by computing the ratio.

If $α>λ/(λ+1)$, almost all of the complete binomial expansion is present, so the sum equals $(1+o(1))(1+λ)^n$.

If $α≈p$, then Russell's normal approximation will be good. (This needs some work to clarify whether the geometric approximation of the lower tail is good right up to the point where the normal approximation begins to be good. I think it is.)

Answer 2

Your sum can also be thought of as the first $\alpha n$ terms in a binomial distribution with probability of success $p=1-\frac1{\lambda+1}$. So, it is closely approximated by a normal distribution with mean $np$ and standard deviation $\sqrt{np(1-p)}$, i.e., $$\sum_{k=0}^{\alpha n} \binom nk \lambda^k\approx (1-p)^{-n}\Phi\left((\alpha-p)\sqrt{\frac n{p(1-p)}}\right),$$ where $\Phi$ is the cumulative standard normal distribution.

Answer 3

Sums of this sort are estimated by their largest summand, and the resulting estimate will depend on the relation between $\alpha$ and $\lambda$.

The ratio of the $(k+1)$th and the $k$th terms of the untruncated sum is $$ \lambda \frac{n-k}{k+1}, $$ showing that the sequence of summands is unimodal, with the maximum value attained for $k$ about $\frac{\lambda}{\lambda+1}\,n$. Consequently, if $\alpha<\lambda/(\lambda+1)$, then your sum is between $\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$ and $n\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$, which is $2^{H((\alpha)+\alpha\log_2\lambda+o(1))n}$; similarly, if $\alpha>\lambda/(\lambda+1)$, then the sum is $2^{(H(\lambda/(\lambda+1))+(\lambda/(\lambda+1))\log_2\lambda+o(1))n}=(\lambda+1)^{1+o(1)}$. (Both estimates assume that $\alpha$ and $\lambda$ are fixed, and $n\to\infty$.)

Answer 4

There are at least two possible goals: either, estimating the rate of convergence as $\lambda \searrow 0$, or estimating the extent of the blow up for $\lambda$ "not extremely small." Although not a complete answer, there's an easy non-asymptotic bound in the latter context which, I hope, may still be worth mentioning due to its simplicity.

Let $c>0$ with $\lambda \geq c/n$. For all integers $k \geq 0$ with $k \leq c$, we have $$ \binom{n}{k} \lambda^k \:\leq\: \frac{n^k}{k!} \lambda^k \:=\: \left(\! \frac{n\lambda}{c} \!\right)^{\!k} \frac{c^k}{k!} \:\leq\: \left(\! \frac{n\lambda}{c} \!\right)^{\!c} \frac{c^k}{k!}. $$ Therefore, summing across $k \leq c$ gives $$ \sum_{k=0}^c \binom{n}{k} \lambda^k \:\leq\: \left(\! \frac{n\lambda}{c} \!\right)^{\!c} \sum_{k \leq c} \frac{c^k}{k!} \:\leq\: \left(\! \frac{n\lambda}{c} \!\right)^{\!c} e^c \:=\: \left(\! \frac{en\lambda}{c} \!\right)^{\!c}. $$

In particular, taking $c = \alpha n$, we obtain the simple bound that $$ \sum_{k=0}^{\alpha n} \binom{n}{k} \lambda^k \:\leq\: \left(\! \frac{e\lambda}{\alpha} \!\right)^{\!\alpha n} $$ whenever $\lambda \geq \alpha$.