9
$\begingroup$

I would like to have an estimate for the infinite series $$ \sum_{k=B}^\infty \frac{A^k}{k!}, $$ where $A$ is a large positive quantity and $B$ is just a little bit bigger than $A$, namely, $B = A + C \sqrt A$ for some fixed large positive constant $C$. (In my application, $A$ and thus $B$ are increasing functions of some other variable, but $C$ really will stay fixed.)

I expect that the answer should look something like $$ ?\ \sum_{k=B}^\infty \frac{A^k}{k!} \ll e^{-C^2/2} \ \ ? $$ uniformly in $A$, $B$, and $C$. (Possibly there should even be an asymptotic formula.) It would be great to be able to just quote such an estimate "off the shelf". I've only been able to find such estimates when $B$ is substantially larger than $A$, such as $B > 5A$.

Does anyone know of a bound of this type in the literature? Many thanks.

$\endgroup$
1
  • 1
    $\begingroup$ Suppose you try Stirling's approximation for factorial. Does that get you far enough? Or is C too small for that to work? (I can imagine Stirling's estimate useful if B were A + C(A)^(c + 1/2), for small positive c.) Gerhard "Ask Me About System Design" Paseman, 2010.04.01, no fooling. $\endgroup$ Apr 1, 2010 at 23:37

3 Answers 3

17
$\begingroup$

Let's instead consider the sum

$$ \sum_{k = A + C \sqrt{A}}^\infty {e^{-A} A^k \over k!} $$ which of course differs from yours just by a factor of $e^{-A}$.

Then this sum is the probability that a Poisson random variable of mean $A$ is at least $A + C\sqrt{A}$.

A Poisson with mean $A$ has standard deviation $\sqrt{A}$, and as $A \to \infty$ the Poissons become asymptotically normal. So we have

$$ \sum_{k = A + C \sqrt{A}}^\infty {e^{-A} A^k \over k!} \to \Phi(C) $$

as $A \to \infty$, where $\Phi$ is the CDF of the standard normal. So your sum is asymptotic to $e^A \Phi(C)$.

Alternatively, if you'd like an explicit inequality, your sum can be bounded above by the geometric series with first term $A^B/B!$ and common term ratio $A/B$. Therefore, your sum is less than $$ {A^B \over B!} {1 \over 1-A/B} $$ and this can be rewritten as $$ {A^B \over B!} \left( 1 + {\sqrt{A} \over C} \right) $$ The product $A^B/B!$ is, as $A \to \infty$ with $B = A + C \sqrt{A}$, $$ {1 \over \sqrt{2\pi}} e^{-C^2/2} A^{-1/2} e^A (1+o(1))$$ by Stirling's formula. In the factor $1 + \sqrt{A}/C$ we can neglect $1$ as $A \to \infty$, so we get that

$$ \sum_{k = A+C\sqrt{A}}^\infty {e^{-A} A^k \over k!} \le {1 \over \sqrt{2\pi}} C e^{-C^2/2} e^A (1 + o(1)) $$

By, say, the double inequality (26) here it should be possible to get explicit bounds.

$\endgroup$
6
  • $\begingroup$ Aside from Douglas's comment, from $e^{-A} f(A) = \Phi(C) + o(1)$ you can't conclude that $f(A) = e^A \Phi(C) + o(1)$ unless you know the convergence in the first approximation is superexponentially fast as $A \to \infty$, which it is not in this case. $\endgroup$ Apr 2, 2010 at 13:42
  • $\begingroup$ I should add, though, that although Douglas is right that there are some errors in the geometric series bound, I think it can be fixed to give essentially the same final result. $\endgroup$ Apr 2, 2010 at 13:47
  • $\begingroup$ By "$f$ is asymptotic to $g$" I mean that $f = g(1+o(1))$, not that $f = g + o(1)$. $\endgroup$ Apr 2, 2010 at 14:03
  • $\begingroup$ The geometric series bound should be fixed now. $\endgroup$ Apr 2, 2010 at 14:14
  • $\begingroup$ Sorry, my language wasn't clear in the original post: I do want an explicit inequality, rather than an asymptotic without an error term (although the limit $\sum_{k = A + C \sqrt{A}}^\infty {e^{-A} A^k \over k!} \to \Phi(C)$ is what motivates the choice of B, to be sure). $\endgroup$ Apr 3, 2010 at 5:39
6
$\begingroup$

The exponential inequality yields explicit bounds as follows. For every $B\ge A$, consider the series $$ S(A,B)=\sum_{k=B}^{+\infty}\frac{A^k}{k!}. $$ Then, as Michael Lugo noticed, $\mathrm{e}^{-A}S(A,B)=P(N_A\ge B)$, where $N_A$ is a Poisson random variable with parameter $A$.

For every positive $t$, $N_A\ge B$ if and only if $\mathrm{e}^{tN_A-tB}\ge1$, and for every nonnegative random variable $X$, $P(X\ge1)\le E(X)$. Using this for $X=\mathrm{e}^{tN_A-tB}$, one gets $$ \mathrm{e}^{-A}S(A,B)\le E(X)=E(\mathrm{e}^{tN_A})\ \mathrm{e}^{-tB}. $$ To go further, one uses the fact that the Laplace transform $E(\mathrm{e}^{tN_A})$ of a Poisson distribution is $\mathrm{e}^{A(\mathrm{e}^t-1)}$ and one optimizes the upper bound with respect to $t\ge0$. That is, one plugs in the inequality the value of $t$ such that $\mathrm{e}^t=B/A$, which yields $$ S(A,B)\le\mathrm{e}^{B-B\log(B/A)}. $$ Note that this upper bound is not asymptotic (which is nice) but that, in general, it is not optimal in the regime of the central limit theorem you are interested in (which is not so nice).

Turning to the case where $A\to\infty$ and $B=A+C\sqrt{A}$ with $C>0$ fixed, the expansion of $\log(B/A)$ up to the order $o(1/A)$ yields $$ S(A,A+C\sqrt{A})\le\mathrm{e}^{A-C^2/2+o(1)}=\mathrm{e}^{-C^2/2}\mathrm{e}^A(1+o(1)). $$ Which is a (very odd) way to check that $\Phi(C)\le\mathrm{e}^{-C^2/2}$...

Edit : Non asymptotic upper bound : $$ S(A,A+C\sqrt{A})\le\mathrm{e}^{-C^2/2}\mathrm{e}^{A}\exp(C^3/(2\sqrt{A})). $$

$\endgroup$
1
  • $\begingroup$ The non-asymptotic upper bound seems rather vacuous? For instance when $B \gg A$, $C \approx B$ and $e^{C^3}$ is no good? $\endgroup$
    – John Jiang
    Dec 13, 2020 at 4:23
0
$\begingroup$

It can be shown, using $(8.12.18)$ and Stirling's formula that $$ \sum\limits_{k = A + C\sqrt A }^\infty {\frac{{A^k }}{{k!}}} = \frac{{\gamma (A + C\sqrt A ,A)}}{{\Gamma (A)}} = \Phi (C)\, {\rm e}^A + {\rm e}^{ - \frac{{C^2 - 2A}}{2}}\, \mathcal{O}\!\left( {\frac{{C^2 }}{{\sqrt A }}} \right) $$ as $A\to+\infty$, uniformly with respect to $C$ provided $C =\mathcal{O}(A^{1/6-\varepsilon})$.

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