# Why $(\alpha\frac{e}{t})^t e^{-\alpha}$ is an approximation for $P(X > t\alpha)$ for Poisson distribution $\frac{\alpha^ke^{k}}{k!}$?

I am reading Section 3.4 of Algorithms, 4th Edition. Page 466 is a proof of the following proposition:

In a separate-chaining hash table with $$M$$ lists and $$N$$ keys, the probability (under Assumption J) that the number of keys in a list is within a small constant factor of $$N/M$$ is extremely close to 1.

The proof:

The probability that a given list will contain exactly k keys is given by the binomial distribution

$$\binom{N}{k}(\frac{1}{M})^k(\frac{M-1}{M})^{N-k}$$

When $$N$$ is large and $$p=\frac{1}{M}$$ is small, binomial distribution can be approximated by Poisson distribution (The book uses $$\alpha$$ for $$\lambda$$):

$$\frac{\alpha^ke^{k}}{k!}$$

It follows that the probability that a list has more than $$t\alpha$$ keys on it is bounded by the quantity $$(\alpha\frac{e}{t})^t e^{-\alpha}$$.

In other words, the probability that $$P(X > t\alpha)$$ is bounded by the quantity $$(\alpha\frac{e}{t})^t e^{-\alpha}$$.

I searched the web and browsed https://en.wikipedia.org/wiki/Poisson_distribution. But I couldn't find a reference for the formula $$(\alpha\frac{e}{t})^t e^{-\alpha}$$.

From the background in the book, we can assume that $$\alpha \geqslant 10$$ and $$t \geqslant 2$$.

For $$s > 0$$, $$\{X \geqslant t\alpha \} = \{sX \geqslant st\alpha\} = \{e^{sX} \geqslant e^{st\alpha}\}$$, so

$$P(X > t\alpha ) \leqslant P(X \geqslant t\alpha) \leqslant \frac{E[e^{sX}]}{e^{st\alpha}}$$

by Markov's inequality. Since $$E[e^{sX}] = e^{\alpha(e^{s}-1)}$$, we have:

$$P(X > t\alpha ) \leqslant \frac{e^{\alpha(e^{s}-1)}}{e^{st\alpha}} = e^{\alpha(e^{s}-1)-st\alpha}$$

Maximizing this bound is equivalent to maximizing $$\alpha(e^{s}-1)-st\alpha$$. And it is obvious that maximizing $$\alpha(e^{s}-1)-st\alpha$$ is equivalent to maximizing $$f(s) = e^{s}-st$$ since $$\alpha > 0$$.

$$f\prime(s) = e^{s} - t$$

$$f\prime\prime(s) = e^{s}$$

Solve $$f\prime(s) = 0$$, we have $$s = \ln{t}$$. And $$f\prime\prime(\ln{t}) = t > 0$$. So $$s = \ln{t}$$ maximizes $$f(s)$$.

$$P(X > t\alpha ) \leqslant \frac{e^{\alpha(t-1)}}{t^{t\alpha}} = (\frac{e^{\alpha}}{t^{\alpha}})^t e^{-\alpha}$$

Now let's compare $$\frac{e^{\alpha}}{t^{\alpha}}$$ with $$\alpha \frac{e}{t}$$. When $$t \geqslant 3$$, we have $$\frac{e^{\alpha}}{t^{\alpha}} < \alpha \frac{e}{t}$$.

When $$t= 2$$, we have $$(\frac{e}{2})^\alpha$$ and $$\alpha \frac{e}{2}$$. When $$\alpha = 10$$, we have $$(\frac{e}{2})^\alpha = 21.51022050274092$$ and $$\alpha \frac{e}{2} = 13.591409142295225$$. When $$\alpha = 20$$, we have $$(\frac{e}{2})^\alpha = 462.68958607653593$$ and $$\alpha \frac{e}{2} = 27.18281828459045$$. So when $$t = 2$$, $$\frac{e^{\alpha}}{t^{\alpha}} < \alpha \frac{e}{t}$$ is not true.

By the above discussion, we can prove $$P(X > t\alpha ) \leqslant (\alpha \frac{e}{t})^{t} e^{-\alpha}$$ for $$t \geqslant 3$$. But we can't prove the $$t = 2$$ case.

• Can you provide more details about the statement you reproduced? I.e., what exactly is the Poisson r.v. there? Mar 4 '16 at 3:33
• @A.S. The link is the web site for the book not book itself. Mar 4 '16 at 6:27
• @A.S. I will edit my question to give enough background so that you can have a try. Mar 4 '16 at 6:33
• This might help en.wikipedia.org/wiki/Poisson_limit_theorem
– Rol
Mar 4 '16 at 6:45
• The question was modified and now seems to ask how to bound $P(X_a\geqslant xa)$ for $x>1$ fixed, when $a\to\infty$. The standard approach is to optimize the exponential bound $P(X_a\geqslant xa)\leqslant e^{-sxa}E(e^{sX_a})$ over $s>0$. Note that $E(e^{sX_a})=\exp(a(e^s-1))$ hence one wants to minimize $a(e^s-1)-sxa$, which happens when $e^s=x$, then the upper bound reads $$P(X_a\geqslant xa)\leqslant x^{-xa}e^{a(x-1)}=(e^x/(x^xe))^a.$$
– Did
Mar 4 '16 at 7:02

It turns out that the formula $$(\alpha e/t)^t e^{-\alpha}$$ is incorrect. The correct formula is $$(e/t)^{\alpha t}e^{-\alpha}$$.