# A good upper bound of $S_n := \sum_{k=1}^n e^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{(k \varepsilon)^k}$ in terms of $\varepsilon,\lambda,n$

Fix $$\varepsilon \in (0, 1), \lambda >0$$, and a positive integer $$n$$. I'm interested in upper bound the quantity $$S_n := \sum_{k=1}^n e^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{(k \varepsilon)^k}$$ in terms of $$\varepsilon,\lambda,n$$. The term $$e^{-\lambda} \frac{\lambda^k}{k!}$$ is the probability mass from Poisson distribution with parameter $$\lambda$$. The term $$\frac{1}{(k \varepsilon)^k}$$ can be considered the loss associated to $$k$$. So $$S_n$$ can be seen as the average loss up to $$n$$. Of course, we have a trivial upper bound $$S_n \le \sum_{k=1}^\infty e^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{\varepsilon^k} = \exp \left (-\lambda + \frac{\lambda}{\varepsilon} \right ).$$

Could you elaborate on some techniques to have a tight upper boud of $$S_n$$? Any reference is appreciated!

We can use the asymptotically sharp inequality $$\Gamma\! \left( {k + \tfrac{1}{2}} \right) \le k^k {\rm e}^{ - k} \sqrt {2\pi }$$ valid for all $$k\ge 1$$ (see, e.g., this paper). This yields \begin{align*} \sum\limits_{k = 1}^n {{\rm e}^{ - \lambda } \frac{{\lambda ^k }}{{k!}}\frac{1}{{(\varepsilon k)^k }}} & \le \sqrt {2\pi } {\rm e}^{ - \lambda } \sum\limits_{k = 1}^n {\frac{1}{{k!\Gamma\! \left( {k + \frac{1}{2}} \right)}}\left( {\frac{\lambda }{{{\rm e}\varepsilon }}} \right)^k } \\ & = \sqrt 2 {\rm e}^{ - \lambda } \sum\limits_{k = 1}^n {\frac{1}{{(2k)!}}\left( {\frac{{4\lambda }}{{{\rm e}\varepsilon }}} \right)^k } \\ & \le \sqrt 2 {\rm e}^{ - \lambda } \sum\limits_{k = 1}^\infty {\frac{1}{{(2k)!}}\left( {\frac{{4\lambda }}{{{\rm e}\varepsilon }}} \right)^k } \\ &= \sqrt 2 {\rm e}^{ - \lambda } \left( {\cosh \left( {2\sqrt {\frac{\lambda }{{{\rm e}\varepsilon }}} } \right) - 1} \right). \end{align*} You may obtain better bounds by estimating $$2\sum\limits_{k = 1}^n {\frac{{z^{2k} }}{{(2k)!}}} = {\rm e}^z Q(2n + 1,z) + {\rm e}^{ - z} Q(2n + 1, - z) - 2$$ in a different manner (here $$Q$$ is the normalised incomplete gamma function).

• I checked some values of $\lambda, \varepsilon$. Sometimes, your result (the first one) is better than mine (even optimal i.e. min over $a > 0$). Sometimes my result (even $a=1$) is better than yours. Jan 17, 2023 at 7:52

Fact 1: $$x^{-x} \le a^{-x} \mathrm{e}^{-x + a}$$ for all $$x, a > 0$$.
(Proof: Taking logarithm on both sides, letting $$u = \frac{a}{x} > 0$$, it is equivalent to $$\ln u \le u - 1$$ which is true (easy).)

By Fact 1, we have, for all $$a > 0$$, \begin{align*} \sum_{k=1}^n \mathrm{e}^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{(k \varepsilon)^k} &\le \sum_{k=1}^n \mathrm{e}^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{ \varepsilon^k} \cdot a^{-k} \mathrm{e}^{-k + a}\\[6pt] &= \mathrm{e}^{-\lambda + a} \sum_{k=1}^n \frac{1}{k!}\left(\frac{\lambda}{\mathrm{e} a \varepsilon }\right)^k\\[6pt] &\le \mathrm{e}^{-\lambda + a} \sum_{k=1}^\infty \frac{1}{k!}\left(\frac{\lambda}{\mathrm{e} a \varepsilon }\right)^k\\[6pt] &= \mathrm{e}^{-\lambda + a + \lambda/(\mathrm{e} a \varepsilon) } - \mathrm{e}^{-\lambda + a}. \end{align*} Thus, we have $$\sum_{k=1}^n \mathrm{e}^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{(k \varepsilon)^k} \le \min_{a>0} \left(\mathrm{e}^{-\lambda + a + \lambda/(\mathrm{e} a \varepsilon) } - \mathrm{e}^{-\lambda + a}\right).$$ Since the RHS does not admit a simple solution, we may let e.g. $$a = 1$$ to get $$\sum_{k=1}^n \mathrm{e}^{-\lambda} \frac{\lambda^k}{k!} \frac{1}{(k \varepsilon)^k} \le \mathrm{e}^{-\lambda + 1 + \lambda/(\mathrm{e} \varepsilon) } - \mathrm{e}^{-\lambda + 1}.$$

• Perhaps $$a = \sqrt {\frac{\lambda }{{{\rm e}\varepsilon }}}$$ is a better choice.
– Gary
Jan 17, 2023 at 7:26
• @Gary I think it depends on $\lambda, \varepsilon$. Numerically, I check some values, sometimes it is better, sometimes, $a = 1\sim 2$ is better. Jan 17, 2023 at 7:33