6
$\begingroup$

I have the following limit:

$\lim_{n\rightarrow\infty}e^{-\alpha\sqrt{n}}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}\sum_{m=0}^{n-1-k}\frac{(\alpha\sqrt{n})^m}{m!}$

where $\alpha>0$.

Evaluating this in Mathematica suggests that this converges, but I don't know how to evaluate it. Any help would be appreciated.

4 Answers 4

6

Let $A_n$ denote the formula inside the limit. By noting that the double summation is taken for those non-negative integers $k, m$ with $l := k+m \leq n-1$, by changing the order of summation,

$\begin{align*} A_n &= e^{-\alpha\sqrt{n}} \sum_{m=0}^{n-1}\sum_{k=0}^{n-1-m} \binom{n-1+k}{k} 2^{-n-k}\frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \sum_{m=0}^{n-1} \left( \sum_{k=0}^{n-1-m} \frac{1}{k!} \frac{(n-1+k)!}{2^{n+k}} \right) \frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \sum_{m=0}^{n-1} \left( \sum_{k=0}^{n-1-m} \frac{1}{k!} \int_{0}^{\infty} x^{n+k-1}e^{-2x}\;dx \right) \frac{(\alpha \sqrt{n})^m}{m!} \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{m=0}^{n-1} \sum_{k=0}^{n-1-m} \frac{x^k}{k!} \frac{(\alpha \sqrt{n})^m}{m!} \right) x^{n-1} e^{-2x}\;dx \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \sum_{k=0}^{l} \frac{x^k}{k!} \frac{(\alpha \sqrt{n})^{l-k}}{(l-k)!} \right) x^{n-1} e^{-2x}\;dx \\ &= \frac{e^{-\alpha\sqrt{n}}}{(n-1)!} \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} \right) x^{n-1} e^{-2x}\;dxdx \\ &= \int_{0}^{\infty} \left( \sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} e^{-(x+\alpha\sqrt{n})} \right) \frac{x^{n-1} e^{-x}}{(n-1)!}\;dx. \end{align*}$

Now, observe that

$ \begin{align*} &\sum_{l=0}^{n-1} \frac{(x+\alpha\sqrt{n})^l}{l!} e^{-(x+\alpha\sqrt{n})} \\ &\hspace{5em}= \frac{1}{(n-1)!}\sum_{l=0}^{n-1} \binom{n-1}{l} (x+\alpha\sqrt{n})^l e^{-(x+\alpha\sqrt{n})} \int_{0}^{\infty} t^{n-1-l}e^{-t} \; dt \\ &\hspace{5em}= \frac{1}{(n-1)!} \int_{0}^{\infty} (t+x+\alpha\sqrt{n})^{n-1} e^{-(t+x+\alpha\sqrt{n})} \; dt \\ &\hspace{5em}= \frac{1}{(n-1)!} \int_{x+\alpha\sqrt{n}}^{\infty} t^{n-1}e^{-t} \; dt = \frac{\Gamma(n,x+\alpha\sqrt{n})}{\Gamma(n)}, \end{align*} $

where $\Gamma(s,x)$ is the incomplete gamma function. So if we define $G_n(x)$ as

$G_n(x) = \frac{\Gamma(n,x)}{\Gamma(n)} ,$

the above calculation shows that we can write

$ A_n = - \int_{0}^{\infty} G_n(x+\alpha\sqrt{n})G_n'(x)\;dx. \tag{1} $

Now let $\{ X_1, X_2, \cdots, Y_1, Y_2, \cdots \}$ be a family of independent random variables each having an exponential distribution of parameter $1$. Then for its partial sums $S_n = X_1 + \cdots + X_n$ and $T_n = Y_1 + \cdots + Y_n$, it is easy to see that

$ F_{S_n}(x) = \Bbb{P}(S_n \leq x) = 1 - G_n (x) $

and likewise for $F_{T_n}(x) = \Bbb{P}(T_n \leq x)$. Thus $(1)$ reduces to

$ \begin{align*} A_n &= \int_{0}^{\infty} \Bbb{P}\left(T_n > x+\alpha\sqrt{n}\right) \; dF_{S_n}(x) \\ & = \Bbb{P}\left(T_n > S_n +\alpha\sqrt{n}\right) = \Bbb{P}\left(\frac{T_n - n}{\sqrt{n}} > \frac{S_n - n}{\sqrt{n}} +\alpha\right). \end{align*}$

Since $\Bbb{E}S_n = \Bbb{E}S_n = n$ and $\Bbb{V}S_n = \Bbb{V}T_n = n$, central limit theorem yields

$ \lim_{n\to\infty} A_n = \Bbb{P}\left(Z_2 > Z_1 +\alpha\right), $

where $Z_i \sim N(0, 1)$ are independent random variables each having a standard normal distribution. Therefore we have

$ \lim_{n\to\infty} A_n = \frac{1}{2}\left[ 1 - \mathrm{erf}\left(\frac{\alpha}{2}\right)\right] $

2

Let $X_n$ denote a Poisson random variable with parameter $\alpha\sqrt{n}$ and $Y_n$ a negative binomial random variable with parameters $(n,\frac12)$. Recall that this means that, for every $k\geqslant0$, $ P[X_n=k]=\mathrm e^{-\alpha\sqrt{n}}\frac{(\alpha\sqrt{n})^k}{k!},\qquad P[Y_n=k]=2^{-n-k} {n-1+k\choose k}. $ Thus, assuming that $X_n$ and $Y_n$ are independent, the $n$th sum you are considering is $ S_n=P[X_n+Y_n\leqslant n-1]. $ First, $Y_n$ can be realized as the sum of $n$ i.i.d. random variables with geometric distribution of parameter $\frac12$, in particular, the central limit theorem states that $Y_n=n+\sqrt{2n}Z_n$ where $Z_n$ converges in distribution to a standard random variable $Z$. Second, the variance of a Poisson random variable being equal to its mean, $X_n=\alpha\sqrt{n}+\sqrt{n}T_n$ where $T_n\to0$ in distribution. Hence, $ \frac{X_n+Y_n-n+1}{\sqrt{n}}=\alpha+T_n+\sqrt{2}Z_n+\frac1{\sqrt{n}} $ converges in distribution to $\alpha+\sqrt{2}Z$. Thus, $ S_n=P\left[\frac{X_n+Y_n-n+1}{\sqrt{n}}\leqslant0\right]\to S=P[\alpha+\sqrt{2}Z\leqslant0], $ and $ S=1-\Phi\left(\frac{\alpha}{\sqrt2}\right)=\frac12\left(1-\mathrm{erf}\left(\frac{\alpha}{2}\right)\right). $

1

Maybe start by doing something along the lines of noting that

$\sum_{m=0}^{\infty}\frac{(\alpha\sqrt{n})^m}{m!} = e^{\alpha \sqrt{n}}$

so that the final sum is

$e^{\alpha \sqrt{n}} - \sum_{m=n-k}^{\infty}\frac{(\alpha\sqrt{n})^m}{m!}$

1

I would start even more simple-mindedly by replacing the inner sum with its infinite $n$ value of $e^{\alpha \sqrt{n}}$. This cancels out the outer expression, so we are left with

$\lim_{n\rightarrow\infty}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}$.

Doing some manipulation, $\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k} = \sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose {n-1}} = \sum_{k=n-1}^{2n-2}2^{-k-1} {{k}\choose {n-1}} $.

As often happens, it is late and I am tired and not sure exectly what to do next, so I'll leave it at this.