12

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

bandini
  • 491
  • Have you tried replacing 2 by (1+lambda)? Alternatively, for large lambda and alpha far enough away from 1/2, some nice estimates occur by using geometric series approximations. Gerhard "Ask Me About System Design" Paseman, 2012.004.11 – Gerhard Paseman Apr 11 '12 at 10:12
  • There are many estimates here. Is there context as to what kind of estimate you are looking for? – Daniel Parry Apr 11 '12 at 18:34

4 Answers4

10

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

Brendan McKay
  • 37,203
  • The last assertion is actually not true, as stated: say, if $\lambda=1$ and $\alpha$ is just a tiny bit larger than $1/2$, then the sum is not equal to $(1+o(1))2^n$ (it is half of this quantity). – Seva Apr 11 '12 at 14:02
  • Perhaps you are not taking $\alpha$ to be constant as $n\to\infty$. Apart from the scaling factor of $2^n$, it is a binomial distribution $Bin(n,1/2)$, which has a standard deviation of $\sqrt{n}/2$. So if $\alpha=1/2+\epsilon$ for fixed $\epsilon>0$, the upper limit of your sum is $2\epsilon\sqrt{n}$ standard deviations above the mean, so it cuts off a negligible portion of the sum from 0 to $n$. To asymptotically get half of $2^n$ you need $\alpha=1/2+o(n^{-1/2})$, which is not constant except for $\alpha=1/2$. – Brendan McKay Apr 12 '12 at 02:08
  • What happens when $\alpha=c/n$ for $c$ a constant? Can one bound the sum in terms of $c$, $\lambda$ and $n$? – Bullmoose Nov 22 '13 at 04:33
  • @Bullmoose: In that case the sum is strongly dominated by its largest term. – Brendan McKay Nov 22 '13 at 04:50
  • I posted a question related to this here: http://mathoverflow.net/questions/149604/sum-of-binomial-coefficients-weighted-by-a-lower-incomplete-regularized-gamma-fu The question is the origin of my query. – Bullmoose Nov 22 '13 at 05:57
  • @BrendanMcKay Could you please elaborate on the "strongly dominated by its largest term", specifically, what do you mean by strongly dominated? Do you mean that, if the largest term in the partial sum is $M(c,n,\lambda)$ then the sum is $(1+C)M(c,n,\lambda)$ where $C=o(1)$ or some constant? If so, how is $C$ dependent on $c$, $n$, and $\lambda$? Thank you! – Bullmoose Nov 22 '13 at 18:03
  • In this answer, are we assuming $\lambda < 1$ or $\lambda > 1$? Or does that not matter somehow? – Naysh Sep 22 '21 at 15:31
6

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

Seva
  • 22,827
6

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.

Russell May
  • 527
  • This will only be a good estimate when the upper limit is close to the centre of the normal approximation, i.e., when $\alpha\approx p$. – Brendan McKay Apr 11 '12 at 11:39
  • Do you have an error approximation on this, @BrendanMcKay or @RussellMay? I would love to know. I have a problem in exactly this situation. – Maxim Gilula Nov 08 '18 at 03:56
  • @MaximGilula There is a large literature on normal approximation of the binomial distribution. Start with the Berry-Esseen Theorem, which gives an explicit bound on the error. – Brendan McKay Sep 23 '21 at 02:26
  • I needed something a little stronger than that theorem when I worked on the problem I had in mind. The error is relatively large for what I needed. – Maxim Gilula Sep 23 '21 at 02:27
0

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

Thomas Winckelman
  • 101