Suma de términos exponenciales y binomiales

Question

Me gustaría calcular la siguiente expresión con un $m$ grande:

$$\sum^{m}_{q=1} \frac{(-1)^{q+1}}{q+1} {{m}\choose{q}} e^{-\frac{q}{q+1}\Gamma}.$$

Pero, debido al binomial, la computadora se queda atascada cuando $m$ crece mucho. En este problema tenemos que $\Gamma > 0$. Estoy tratando de encontrar una simplificación o una solución alternativa, pero no encontré nada que pueda ayudarme. ¿Alguien puede darme algunas pistas?

Answer 1

Calculando eficientemente los coeficientes binomiales

Si con "se queda atascado" te refieres a que la computación es lenta, supondría que estás calculando el término binomial de forma ineficiente. De hecho, no deberías recalcular el término binomial para cada sumando, sino que en su lugar utilizar el hecho de que $$ \binom{m}{q}=\frac{m!}{q!\left(m-q\right)!}=\frac{m-\left(q-1\right)}{q}\frac{m!}{\left(q-1\right)!\left(m-\left(q-1\right)\right)!}=\frac{m-q+1}{q}\binom{m}{q-1}. $$ Definiendo $$ C_{q}=\frac{m-q+1}{q}C_{q-1}\text{ si }q\geq1\qquad\text{y}\qquad C_{0}=1, $$ se sigue de la afirmación anterior que $C_{q}=\binom{m}{q}$. Por lo tanto, puedes reescribir la suma en la que estás interesado como $$ S\equiv \sum_{q=1}^{m}\frac{\left(-1\right)^{q+1}}{q+1}C_{q}\exp\left(-\frac{q}{q+1}\Gamma\right). $$

Eliminando algunos términos por simetría

Podemos utilizar el hecho de que $C_{q}=C_{m-q}$ para reducir la cantidad de términos. Observa que $$ S-1=\sum_{q=0}^{m}\frac{\left(-1\right)^{q+1}}{q+1}\exp\left(-\frac{q}{q+1}\Gamma\right)C_{q}. $$ Suponiendo que $m=2j+1$ es impar, obtenemos $$ S-1=\sum_{q=0}^{j}\left(-1\right)^{q+1}\left(\frac{1}{q+1}\exp\left(-\frac{q}{q+1}\Gamma\right)-\frac{1}{m-q+1}\exp\left(-\frac{m-q}{m-q+1}\Gamma\right)\right)C_{q}. $$ Suponiendo que $m=2j$ es par, obtenemos \begin{multline*} S-1=\frac{\left(-1\right)^{j+1}}{j+1}\exp\left(-\frac{j}{j+1}\Gamma\right)C_{j}\\ +\sum_{q=0}^{j}\left(-1\right)^{q+1}\left(\frac{1}{q+1}\exp\left(-\frac{q}{q+1}\Gamma\right)+\frac{1}{m-q+1}\exp\left(-\frac{m-q}{m-q+1}\Gamma\right)\right)C_{q}. \end{multline*}

Answer 2

Este cálculo se puede hacer numéricamente sin problema hasta $m=2^{13}$. Tomó alrededor de 15 segundos de tiempo de CPU usando Mathematica en mi computadora portátil Mac de 2 años para $m=2^{13}$.

Aquí tienes un ejemplo del código de Mathematica:

s[m_, g_] := Sum[ (-1)^(q+1)/(q + 1) Binomial[ m , q] Exp[ - q g/(q + 1)], {q, 1, m}];
Print[ Timing[ s[10000, N[1/4, 10000]]//N]; 

La salida del programa anterior es {27.7445,0.999574} indicando que tomó 27 segundos para calcular la respuesta. Ten en cuenta que ${1000\choose 500}$ tiene alrededor de 3000 dígitos, por lo que el programa usó 10000 dígitos de precisión. El tiempo de ejecución es del orden $m^3$.

La respuesta suele estar cerca de 1 cuando $0 y $m> 2^{10}$.

---

Escribí el código en Python y obtuve el mismo resultado para $m=2^{13}$ y $q=1/4$.

from mpmath import mp

mp.dps =5000;

m = 2**13;

mp.pretty = True

rS = mp.mpf(0);

g = mp.mpf(1)/mp.mpf(4);

for q in range(1, m+1):
    rS = rS + mp.mpf((-1)**(q+1))* mp.binomial(m, q)/(q+1)*mp.exp(-q*g/(q+1));

mp.nprint(rS, 10)