¿Cómo calcular el % de la suma $(\sum_{p = k}^{n} \binom{n}{p}) / 2^n$rápidamente?

Question

Yo era la solución de una cuestión a la que técnicamente se reduce a la siguiente

Dado $N$ artículos, es equiprobables para cada elemento a ser bueno o malo, ¿cuál es la probabilidad de que buen número de elementos en el conjunto es mayor que o igual a $K$.

Esto puede ser reducido a $\dfrac{x}{2^n}$ donde $\displaystyle x = \sum_{p = k}^{n} \binom{n}{p}$. Hay una forma más simplificada que es más fácil de calcular para grandes valores de $N, K$?

Nota: puede ser seguro asumir que no requieren de muy alta precisión, mientras que el cálculo(primera de 5 a 10 dígitos).

Gracias!

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove armada]{\displaystyle{#1}}\,} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Para los 'grandes'$\ds{n, p\ \mbox{and}\ n - p}$, $\ds{{n \choose p} \sim 2^{n}\exp\pars{-\,{\bracks{p - n/2}^{2} \over n/2}}}$.

Usted puede utilizar el $\ds{\bbox[#dfd,5px]{\ Laplace\ Method\ for\ Sums\ }}$ ( ver página $761$ $\ds{\bbox[#fdd,5px]{\ Analytic\ Combinatorics\ }}$ por Philippe Flajolet y Robert Sedgewick, Cambridge University Press $2009$ ) \begin{align} {1 \over 2^{n}}\sum_{p = k}^{n}{n \choose p} & \sim {1 \over 2^{n}} \bracks{\int_{k}^{n}{n \choose n/2}\exp\pars{-\bracks{p - n/2}^{2} \over n/2}\,\dd p} \\[5mm] & \sim {1 \over 2^{n}}\,{n \choose n/2}{\root{2} \over 2}\,n^{1/2}\int_{\pars{k -n/2}/\root{n/2}}^{\infty}\exp\pars{-p^{2}}\,\dd p \\[5mm] & = {\root{2\pi} \over 4}\,{n \choose n/2}\,{n^{1/2} \over 2^{n}}\bracks{1 + \,\mrm{erf}\pars{n - 2k \over \root{2}\root{n}}} \quad \mbox{as}\ n \to \infty \end{align} donde $\ds{\,\mrm{erfc}\pars{z} \equiv {2 \over \root{\pi}}\int_{0}^{z}\expo{-x^{2}}\,\dd x}$ es la Función De Error.

Answer 2

Un método para calcular la suma directamente y sin perder mucha precisión con aritmética de precisión finita es representar puntos flotantes como un par de mantisa y exponente y factoriales mediante la repetición $$\binom{n}{r} = \binom{n}{r-1} \frac{n-r+1}{r}.$$ Here is a simple Python implementation for $\sum\limits_{p=0}^K \binom{N} {} p}$: def binomial_sum(N,K): current_exponent, current_mantissa = 0, 1.0 total_exponent, total_mantissa = 0, 1.0 for i in range(1, K+1): current_mantissa = (N-i+1)*current_mantissa/i while current_mantissa>=2: current_mantissa/=2 current_exponent+=1 while current_mantissa=2: total_mantissa/=2 total_exponent+=1 return total_exponent, total_mantissa binomial_sum(10000000,5000000) is found to be 1.000252313246 × 2^9999999, correct to 12 decimal places. Of course, this is not going to be as efficient as the approximations using integrals but it should work reasonably well for upto $N\approx10^8$ o algo así.