Efficient evaluation of binomial series

Question

I need to evaluate $$\sum_{i=k}^n {n \choose i} \gamma^i (1-\gamma)^{(n-i)}. $$

But as my $n$ gets often to $10^7$ and $k$ is usually around $0.7n$ it takes significant time to be evaluted about $10^3$ times. Perhaps it can be simplified to avoid the sum? Binomial coefficient itself is probably not the big problem as I used built in function of Wolfram Mathematica.

I care only about some leading digits (and the exponent!) so double is more precise than I need.

EDIT

I have made mistakes when evaluating the values $\gamma$ can have. The real range is from $0.5$ to $0.75$ which makes so much more sense. Please ignore the wrong statement in the comments relevant statements in some answers.

At the moment brute forcing it on 22 cores took me 1 hour. I would be happy if I could speed it up in case I need to reevaluate.

Answer 1

Your sum is a partial sum of hypergeometric function known to have no closed form. If you need exact value nothing can help you. But if you need only some approximation then you can find asymptotic of this sum.

EDIT. As far as I see you compute each $\binom{n}{i}$ independently. That is not a good idea. Note that $\binom{n}{i} = \binom{n}{i - 1}\cdot \frac{n - i + 1}{i}$. So you can compute next summand $a_i = \binom{n}{i} \gamma^i (1 - \gamma)^{n - i}$ using previous one: $a_i = \binom{n}{i - 1} \gamma^{i - 1} (1 - \gamma)^{n - i + 1}\cdot \frac{(n - i + 1)\gamma}{i(1 - \gamma)} = a_{i - 1} \cdot \frac{(n - i + 1)\gamma}{i(1 - \gamma)}$. This should significantly speed up your computations.

(If it will be actual I'll find some time for investigating asymptotics of your function.)

Answer 2

Update: Consider the $i$'th term. For $0<\gamma<1$, all terms are positive. The term will be maximal when $ \frac{n-i}{i} \sim \frac{1-\gamma}{\gamma} $ or $$i_{\rm max}\sim {n\gamma}$$

When $k >> i_{\rm max}$ the main contributions come from the terms close to $k$,

while for $k << i_{\rm max}$ you get 1 minus the sum from 0 to $k-1$ and the main contributions come from the latter.

When $k$ is close to $i_{\rm max}$ you are probably well off by approximating by a gaussian (normal) distribution. But this depends on the accuracy you want? What is the abs/relative error you accept?