Tuesday, October 20, 2015

sequences and series - Asymptotics of partial exponential sum $ sumlimits_{k=0}^{a n} frac{n^k}{k!}$



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}$$



Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...