# Calculating $\lim\limits_{C \rightarrow \infty} -\frac{1}{C} \log(1 + (e^{-p \gamma C} - 1) \sum\limits_{k=0}^{C}e^{-\gamma C} (\gamma C)^k/k!)$

How to calculate the following limit:

$$\lim_{C\rightarrow \infty} -\frac{1}{C} \log\left(1 + (e^{-p \gamma C} - 1) \sum_{k=0}^{C}\frac{e^{-\gamma C} (\gamma C)^k}{k!}\right)$$

Given that $0 \leq \gamma \leq 1$ and $0 \leq p \leq 1$. This is a modified version of a problem I've posted earlier here.

-
Got something from the answer below? –  Did Jun 30 '12 at 12:07
Not much. BTW, I want to find the solution as a function of $\gamma$ –  Osama Gamal Jul 3 '12 at 10:47
Not much is not very enlightening as an explanation about what is lacking from the answer or about what you do not understand in it. See an explicit formula (which you could have computed yourself, afaik) in the revised version. –  Did Jul 3 '12 at 12:18

The argument in the logarithm is $A(C)=\mathrm e^{-p\gamma C}+(1-\mathrm e^{-p\gamma C})\mathrm P(X_{\gamma C}\geqslant C)$ where $X_{\gamma C}$ is a Poisson random variable with parameter $\gamma C$.

Assume that $\gamma\lt1$. When $C\to\infty$, $[X_{\gamma C}\geqslant C]$ is a large deviations event and $$\mathrm P(X_{\gamma C}\geqslant C)=\mathrm e^{-CI(\gamma)+o(C)}$$ for some positive $I(\gamma)$ I will let you discover. Thus, $\log A(C)=-\inf\{p\gamma,I(\gamma)\}C+o(C)$ and the limit you are after is: $\inf\{p\gamma,I(\gamma)\}$.

When $\gamma=1$, $I(\gamma)=0$ and the limit is $0$ for every $p$.

Edit: The large deviations estimate mentioned above is deduced from the usual exponential inequality. Namely, for every nonnegative $t$, $$\mathrm P(X_{\gamma C}\geqslant C)\leqslant\mathrm e^{-tC}\cdot\mathrm E(\mathrm e^{tX_{\gamma C}})=\mathrm e^{-tC}\cdot\mathrm e^{\gamma C(\mathrm e^t-1)}.$$ Hence, for every $\gamma\lt1$, the estimate above holds with $$I(\gamma)=\sup\limits_{t\gt0}\left(t-\gamma(\mathrm e^t-1)\right)=\gamma-1-\log\gamma.$$

-
How did you get $A(C) = - \inf \{p\gamma, I(\gamma)\}C + o(C)$? –  Osama Gamal Jul 8 '12 at 12:36
Read better: this is not what I got. –  Did Sep 13 '12 at 19:02

Another thought: (I use $(n,a,b)$ instead of $(C,\gamma,p)$)

Claim 1 $\hspace{5ex}$ Let $a_n,b_n>0$ with $a_n,b_n=\mathcal O(n^p)$ for some $p\in\mathbb R$ and $a,b>0$. Then $$\lim_{n\to+\infty}-\frac{1}{n}\ln\left(1+(a_ne^{-an}-1)(1-b_ne^{-bn})\right)=\min\{a,b\}.$$

Indeed $\hspace{5ex}$ For $a\leq b$, (the other case is similar) \begin{aligned}-\frac{1}{n}\ln\left(1+(a_ne^{-an}-1)(1-b_ne^{-bn})\right)&=a-\frac{\ln a_n}{n}-\frac{1}{n}\ln\left(1+b_ne^{-(b-a)n}-a_nb_ne^{-bn}\right)\\ \stackrel{a_n,b_n=\mathcal O(n^p)}{=}&a+o(1)\hspace{40ex}\Box\end{aligned}

$\bullet$ If $a=0$ or $b=0$ the quantity equals $0$.

$\bullet$ For $a,b\neq0$ and $a\neq1$, from Taylor's theorem we can write

$$\sum_{k=0}^{n}\frac{(an)^k}{k!}=e^{an}-\frac{1}{n!}\int_{0}^{1}e^t(an-t)^n\,dt:=e^{an}-A_n,$$

and

$$A_n\stackrel{t=any}{=}\frac{(an)^{n+1}}{n!}\int_{0}^{1}e^{any}(1-y)^n\,dy=\frac{(an)^{n+1}}{n!}\mathcal O(1),$$

so

\begin{aligned}e^{-an}\sum_{k=0}^{n}\frac{(an)^k}{k!}&=e^{-an}\left(e^{an}-\frac{(an)^{n+1}}{n!}\mathcal O(1)\right)\\&\stackrel{(1)}{=}1-e^{(1-a+\ln a)n}\mathcal O(\sqrt{n})\mathcal O(1)\\&=1-e^{(1-a+\ln a)n}\mathcal O(\sqrt{n})\end{aligned}

Now the given quantity equals

$$-\frac{1}{n}\ln\left(1+\left(e^{-abn}-1\right)\left(1-e^{(1-a+\ln a)n}\mathcal O(\sqrt{n})\right)\right)$$

and since $1-a+\ln a<0$ from Claim 1 the quantity goes to $\min\{a-1-\ln a,ab\}$.

$(1)$ From Stirling's formula

$\bullet$ For $a=1$ and $b\neq0$, proceeding as above, we need a better estimate for $\int_{0}^{1}e^{ny}(1-y)^n\,dy$ than just $\mathcal O(1)$.

Claim 2 $\hspace{5ex}$ For $a>-1$ and $c>0$ it is $$\int_{0}^{c}t^ae^{-nt}\,dt = \frac{\Gamma(a+1)}{n^{a+1}}+\mathcal O(n^{-1}e^{-nc}).$$

Indeed $\hspace{3ex}$ for $a>-1$ and $c>0$ :

\begin{align}\int_{0}^{c}t^ae^{-nt}\,dt &= \int_{0}^{+\infty}t^ae^{-nt}\,dt-\int_{c}^{+\infty}t^ae^{-nt}\,dt\notag\\ &\stackrel{nt=x}{=} \frac{\Gamma(a+1)}{n^{a+1}}-\frac{1}{n^{a+1}}\int_{nc}^{+\infty}x^ae^{-x}\,dx\notag\\ &\stackrel{x=(1+u)nc}{=} \frac{\Gamma(a+1)}{n^{a+1}}-c^{a+1}\int_{0}^{+\infty}(1+u)^ae^{-(1+u)nc}\,du\notag\\ &\stackrel{1+u\leq e^u}{\Rightarrow} \notag\\ \left|\int_{0}^{c}t^ae^{-nt}\,dt-\frac{\Gamma(a+1)}{n^{a+1}}\right| &\leq c^{a+1}e^{-nc}\int_{0}^{+\infty}e^{u(a-nc)}\,dt=\mathcal O(n^{-1}e^{-nc})\notag\\ &\Longrightarrow \notag\\ \int_{0}^{c}t^ae^{-nt}\,dt &= \frac{\Gamma(a+1)}{n^{a+1}}+\mathcal O(n^{-1}e^{-nc}).\hspace{25ex}\Box\notag \end{align}

Now looking at

$$\int_{0}^{1}e^{nx}(1-x)^n\,dx$$

we set $\phi(x)=-x-\ln(1-x)$ so

$$\frac{1}{\phi^{'}(x)}=-1+\frac{1}{x}$$

but

$$t:=\phi(x)=\frac{x^2}{2}+\mathcal O(x^3)=\frac{x^2}{2}\left(1+\frac{2x}{3}+\mathcal O(x^2)\right)$$

so, as $t\geq0$, setting $u=\sqrt{2t}$ we get

$$u=x\left(1+\frac{2x}{3}+\mathcal O(x^2)\right)^{1/2}=x+\frac{x^2}{3}+\mathcal O(x^3)$$

and reverse setting $x=u+a_2u^2+\mathcal O(u^3)$ and equating coefficients to get

$$x=u-\frac{1}{3}u^2+\mathcal O(u^3).$$

This will give

$$\frac{1}{\phi^{'}(x)}=\frac{1}{\phi^{'}\left(\phi^{-1}(t)\right)}=\frac{\sqrt{2}}{2}t^{-1/2}-\frac{2}{3}+\mathcal O(t^{1/2})$$

and applying Claim 2

$$\int_{0}^{1}e^{ny}(1-y)^n\,dy=\frac{\Gamma(1/2)}{\sqrt{2}}n^{-1/2}+\mathcal O(n^{-1})=\sqrt{\frac{\pi}{2}}n^{-1/2}+\mathcal O(n^{-1}).$$

With Stirling's formula again

\begin{aligned}e^{-n}\sum_{k=0}^{n}\frac{n^k}{k!}&=1-\left(\frac{1}{\sqrt{2\pi}}n^{1/2}+\mathcal O(n^{-1/2})\right)\left(\sqrt{\frac{\pi}{2}}n^{-1/2}+\mathcal O(n^{-1})\right)\\&=\frac{1}{2}+\mathcal O(n^{-1/2})\end{aligned}

so the given quantity equals $-\frac{1}{n}\cdot\mathcal O(1)\to0$.

-
Thanks for your effort –  Osama Gamal Sep 24 '12 at 5:02