4
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – River Li
    Jan 17, 2023 at 7:52
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .