1
$\begingroup$

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

Here is a candidate answer combining @Did's and @ClementC's comments:

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.

$\endgroup$
11
  • $\begingroup$ Can you provide more details about the statement you reproduced? I.e., what exactly is the Poisson r.v. there? $\endgroup$
    – Clement C.
    Mar 4 '16 at 3:33
  • $\begingroup$ @A.S. The link is the web site for the book not book itself. $\endgroup$ Mar 4 '16 at 6:27
  • $\begingroup$ @A.S. I will edit my question to give enough background so that you can have a try. $\endgroup$ Mar 4 '16 at 6:33
  • $\begingroup$ This might help en.wikipedia.org/wiki/Poisson_limit_theorem $\endgroup$
    – Rol
    Mar 4 '16 at 6:45
  • 2
    $\begingroup$ 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.$$ $\endgroup$
    – Did
    Mar 4 '16 at 7:02
0
$\begingroup$

I've been spending hours thinking about the same problem!

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

The correction is posted on the textbook website: Errata.

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