4
$\begingroup$

The question Evaluating $\lim\limits_{n\to\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$ has been asked many times here, and there are different approaches for answering it.

Motivated by this other question, I'm interested in how to attack the modified problem where the number of terms grows as a fraction of $n$. I.e. the behaviour of

$$S(n;a) = \sum\limits_{k=0}^{an} \frac{n^k}{k!}$$

for large $n$, with fixed $a \in (0,1)$ (the upper limit of the summation is understood to be taken as the nearest integer).

Or more specifically,

$$ \lim_{n\to \infty} \left(\sum\limits_{k=0}^{an} \frac{n^k}{k!} \right)^{1/n}$$

Improve this question
$\endgroup$
  • $\begingroup$ Notice that $\displaystyle \sum\limits_{k=0}^{an} \frac{n^k}{k!} = \frac{e^n \Gamma (a n+1,n)}{\Gamma (a n+1)}$. I am not quite sure if this will help. $\endgroup$ – FFjet Aug 30 '19 at 15:04
  • $\begingroup$ @JackD'Aurizio Yes, the problem is that (if I'm not mistaken) the probability (that in the original problem corresponded to half the gaussian curve) now corresponds to a vanishing tail, with probability tending to zero - and it becomes more problematic to use the CLT (as $n$ grows, the $z$ value of the normalized CDF decreases...) $\endgroup$ – leonbloy Aug 30 '19 at 15:30
  • $\begingroup$ Are you saying that the last limit does not depend on $a$ ? I'm not sure about that, because $f(a)$ tends to zero (as $n$ grows) for fixed $a<1$ $\endgroup$ – leonbloy Aug 30 '19 at 15:54
  • $\begingroup$ @JackD'Aurizio I've worked out an answer (not rigorous, but it looks right numerically), unless I'm mistaken the limit definitely depends on $a$. $\endgroup$ – leonbloy Aug 30 '19 at 19:51
  • 1
    $\begingroup$ Using the convergence of the Poisson distribution to the normal distribution for large parameters, $$ e^{-n}\sum_{k\leq an}\frac{n^k}{k!}=\mathbb{P}[\text{Pois}(n)\leq an]\to\mathbb{P}[\mathcal{N}(n,n)\leq an]=\int_{-\infty}^{an}\frac{1}{\sqrt{2\pi n}}e^{-\frac{(x-n)^2}{2n}}\,dx = \frac{1}{2}\left[1+\text{Erf}\left((a-1)\sqrt{n/2}\right)\right]$$ so I would expect $$ \sqrt[n]{\sum_{k\leq an}\frac{n^k}{k!}}\to \exp\left(1-\frac{(1-a)^2}{2}\right)$$ for any $a\in(0,1]$. $\endgroup$ – Jack D'Aurizio Aug 31 '19 at 12:12
1
$\begingroup$

Ok, here's my (not very rigorous) try. Other approaches or refinements are welcomed.

Let's change notation $m = a n$, $x = n = mb$ with $b = 1/a$.

Then $$e^x = \sum_{k=0}^m \frac{x^k}{k!} + R_m(x) \tag1$$

with the remainder:

$$ \begin{align} R_m(x) &= \int_0^x \frac{(x-t)^m}{m!} e^t dt\\ &=\frac{e^x}{m!}\int_0^x y^m e^{-y} dt\\ &=\frac{e^x}{m!} \left(m!- \int_x^\infty y^m e^{-y} dt\right) \tag2\\ \end{align} $$

Because $b>1$, we can approximate the complement of the gamma integral by abusing Laplace's method. Namely, for a differentiable positive decreasing function (more in general, a function that has its global maximum at the start of the interval of integration) and for $m\to \infty$ we approximate

$$ \int_c^\infty e^{m h(x)}dx\approx \int_c^\infty e^{m [h(c) + h'(c)(x-c)]}dx=\frac{e^{m \, h(c)}}{m \,|h'(c)|} \tag{3}$$

Then we can write $$ \int_x^\infty y^m e^{-y} dt =\int_x^\infty e^{m (\log(y)-y/m)} \approx x^m e^{-x} \frac{b}{b-1} \tag 4\\ $$

Actually we are abusing the method here because our $h()$ depends also on $m$ - this would need some justification. Passing over this and putting all together:

$$\begin{align} \sum_{k=0}^m \frac{x^k}{k!} &= e^x - R_m(x) \\ & \approx \frac{x^m}{m!} \frac{b}{b-1} \\ \tag{5} &= \frac{n^{an}}{(an)!} \frac{1}{1-a} \\ & \approx \left(\frac{e}{a}\right)^{an} \frac{1} {(1-a) \, \sqrt{ 2 \pi a} \, \sqrt{n}} \tag{6} \end{align} $$

Finally

$$\lim_{n\to \infty} \left(\sum\limits_{k=0}^{an} \frac{n^k}{k!} \right)^{1/n}= \left(\frac{e}{a}\right)^a \tag 7$$

Added: As rightly comments @Maxim, if we are interested in correcting the rounding (when $m$ in $(5)$ is not an integer we round down to the nearest integer), we should multiply $(6)$ by the correction factor $a^{\{an\}}$, where $\{\}$ denotes the fraction part. Of course, this correction is asymptotically negligible ($O(1)$) and does not change the limit $(7)$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ If $m = n/b \in \mathbb N$, then $$\sum_{k = 0}^m \frac {(b m)^k} {k!} = \frac {e^{b m} \Gamma(m + 1, b m)} {\Gamma(m + 1)} = \frac {(b m)^{m + 1} e^{b m}} {\Gamma(m + 1)} \int_1^\infty e^{m (-b t + \ln t)} dt \sim \frac {b (e b)^m} {(b - 1) \sqrt {2 \pi m}}.$$ The last term in the sum is not negligible, so it appears that without the assumption $a n \in \mathbb N$, we'll get $$\sum_{k = 0}^{\lfloor a n \rfloor} \frac {n^k} {k!} \sim \left( \frac e a \right)^{a n} \frac {a^{\{a n\}}} {(1 - a) \sqrt {2 \pi a n}}.$$ $\endgroup$ – Maxim Aug 30 '19 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.