0

I am interested in the behaviour of:

$\gamma_k=\sum_{i=0}^{k} {n \choose i}$

as n becomes large and where $k$ could potentially be a function of $n$ rather than a constant. One line of attack I can think of is to consider it as the cumulative distribution function of a Binomial Distribution and then approximating this with the Normal Distribution.

Would this approach be productive or is there a better way to tackle this?

Stan
  • 103
  • 2
  • 2
    You might find this useful. http://mathoverflow.net/questions/55585/lower-bound-for-sum-of-binomial-coefficients – Ben Barber Nov 20 '13 at 15:46
  • http://en.wikipedia.org/wiki/Error_function – Allen Knutson Nov 20 '13 at 16:19
  • I don't suggest the normal distribution; it does not approximate the binomial in the tail. Rather try Stirling's formula. Or if your question is covered by Ben's link, consider deleting this question. –  Nov 20 '13 at 16:33

1 Answers1

1

The book by Barbour et al (whose title escapes me at the moment) discusses much more complicated versions of this; you might want to take a look at it.

For $k$ much smaller than $n$, there is a pretty simple observation.
Since the coefficients form a strongly unimodal (aka log concave) sequence, tails decay at least as fast (in fact a lot faster in the case of binomial coefficients) than geometric series, where the ratio of the second largest term in the tail to the largest one is the $r$ for the geometric series, and the ratio is trivial to calculate.

This yields a surprisingly accurate estimate for the sum of the mass in the tail, and can be refined, using several terms. It is also easy to use when $k(n) = o(n)$ (combined with Stirling's formula).

David Handelman
  • 4,659