0
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ You might find this useful. mathoverflow.net/questions/55585/… $\endgroup$
    – Ben Barber
    Nov 20, 2013 at 15:46
  • $\begingroup$ en.wikipedia.org/wiki/Error_function $\endgroup$ Nov 20, 2013 at 16:19
  • $\begingroup$ 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. $\endgroup$
    – user25199
    Nov 20, 2013 at 16:33

1 Answer 1

1
$\begingroup$

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

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