Compute a truncated binomial expectation accurately

External question — Cross Validated Stack Exchange Author: John Jiang Original post: https://stats.stackexchange.com/questions/653081 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. I need to compute the following expectation over a binomial random variable $$E_{S \sim \rm{Binom}(\frac{k}{M}; N)} \left[\left(\frac{k-1}{k}\right)^S 1_{\{S \leq k\}}\right] = \sum_{s=0}^k \binom{N}{s} \left(\frac{k}{M}\right)^s \left(1 - \frac{k}{M}\right)^{N-s} \left(\frac{k-1}{k}\right)^s.$$ Typical ranges of the variables are $0 < k \leq 256$ , $M = N = 10^9$ . If $k = N$ , this can be evaluated nicely using the decomposition of a Binomial RV in terms of independent Bernoulli's. If the term $\left(\frac{k-1}{k}\right)^s$ is not there, this is the cumulative distribution function of a Binomial, which equals an incomplete Beta integral , and is numerically quite stable. But how do I deal with the above hybrid formula, in a numerically stable manner? I don't need it to be fast, just giving me sensible numbers instead of nan or something $> 1$ . Update: for completeness, the sum can be rewritten by a hypergeometric function $$\sum_{s=0}^k \binom{N}{s} p^s q^{N-s} = q^N\left((1 + p/q)^N - (p/q)^{k+1} \binom{N}{k+1} {}_2F_1(1, k-N + 1; k + 2; -p/q)\right),$$ where \begin{align*} {}_2F_1(a, b; c; z) := \sum_{n=0}^\infty \frac{(a)_n(b)_n}{(c)_n} \frac{z^n}{n!}. \end{align*} But for $N$ very large, this runs into numeric overflow. The sum terminates after $n > N - k + 1$ , but it's not worth trading off a sum of $k+1$ terms with one with many more terms.

External answer — Cross Validated Stack Exchange Author: Glen_b Original post: https://stats.stackexchange.com/a/653102 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. This expression appears to cancel down to a simpler form: \begin{eqnarray} \text{Your Expectation} &\equiv& \mathbb{E} \bigg[ \left(1-\frac{k}{M}\right)^S \cdot \mathbb{I}(S \leqslant k) \bigg| S \sim \text{Bin}(N,\tfrac{k}{M}) \bigg] \\[10pt] &=& \sum_{s=0}^k \left(1-\frac{k}{M}\right)^s \text{Bin}(s|N,\tfrac{k}{M}) \\[6pt] &=& \sum_{s=0}^k \left(1-\frac{k}{M}\right)^s {{N}\choose{s}} \left(\frac{k}{M}\right)^s \left(1-\frac{k}{M}\right)^{N-s} \\[6pt] &=& \left(1-\frac{k}{M}\right)^N \sum_{s=0}^k {{N}\choose{s}} \frac{\left(\frac{k}{M}\right)^s}{\left(1-\frac{k}{M}\right)^s} \cdot \left(\frac{k-1}{k}\right)^s \\[6pt] &=& \left(1-\frac{k}{M}\right)^N \sum_{s=0}^k {{N}\choose{s}}\frac{\left(\frac{k-1}{M}\right)^s}{\left(1-\frac{k}{M}\right)^s} \\[6pt] &=& \left(1-\frac{k}{M}\right)^N \sum_{s=0}^k {{N}\choose{s}}\left(\frac{k-1}{M-k}\right)^s \\[6pt] &=& \left[\frac{1-\frac{k}{M}}{1-\frac{k-1}{M-k}}\right]^N \sum_{s=0}^k {{N}\choose{s}}\left[\frac{k-1}{M-1}\right]^s \left[1-\frac{k-1}{M-1}\right]^{N-s} \\[6pt] &=& \left[\frac{1-\frac{k}{M}}{1-\frac{k-1}{M-k}}\right]^N \sum_{s=0}^k \text{Bin} \bigg( s \bigg| N, \frac{k-1}{M-k} \bigg) \\[6pt] &=& \left[\frac{1-\frac{k}{M}}{1-\frac{k-1}{M-k}}\right]^N \mathbb{P}\bigg( S \leqslant k \bigg| S \sim \text{Bin}(N, \tfrac{k-1}{M-k}) \bigg), \\[6pt] \end{eqnarray} which is a simple product involving the binomial CDF with adjusted probability parameter $p=\tfrac{k-1}{M-1}$ . You'd still want to work with logs for the calculation (presumably) and maybe you'd choose to simplify the term out the front, but this expression should be easier than what you started with.