7
$\begingroup$

I came across the following fact in a paper and am having trouble understanding why it is true:

Consider the error made when truncating the expansion for $e^a$ at the $K$th term. By choosing $K = O(\frac{\log N}{\log \log N})$, we can upper bound the error by $1/N$, in other words $$\sum_{j={K+1}}^\infty \frac{a^j}{j!} \leq \frac{1}{N}.$$

Here, the $O$ is "big-O" notation. I'm thinking a Stirling approximation probably has to be used in the denominator but still can't reproduce this result. Maybe this is some well-known result that I'm not aware of?

$\endgroup$
0
$\begingroup$

What we are asked to prove is this: there is a constant $C$ such that if $$ K \ge C \frac{\log N}{\log \log N} $$ then $$ \sum_{j=K+1}^\infty \frac{a^j}{j!} \le \frac1N. \tag1$$ Now clearly the left hand side of (1) grows to infinity as $a \to \infty$, so it must be that $C$ depends upon $a$. Suppose $K \ge 2a$ (which follows if $C \ge 2a$). Then the left hand side of (1) can be bounded above by a geometric series $$ \sum_{j=K+1}^\infty \frac{a^{K}}{K!} 2^{j-K} = \frac{a^K}{K!} .$$ Now use Stirling's formula, noting that if $$ K \ge C \frac{\log N}{\log \log N} $$ then $$ \log(K^K) = K \log K \ge C \frac{\log N}{\log\log N} (\log\log N - \log\log\log N) $$ and that if $N$ is sufficiently large then $$ \log\log N - \log\log\log N \ge \tfrac12 \log\log N .$$


By the way, if you want a much sharper result, use the approximation of the Poisson distribution by the normal distribution, and Proof of upper-tail inequality for standard normal distribution, to get $$ K \ge C \sqrt{\log N} .$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.