2
$\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, 2016 at 3:33
  • $\begingroup$ @A.S. The link is the web site for the book not book itself. $\endgroup$ Mar 4, 2016 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, 2016 at 6:33
  • $\begingroup$ This might help en.wikipedia.org/wiki/Poisson_limit_theorem $\endgroup$
    – Rol
    Mar 4, 2016 at 6:45
  • 3
    $\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, 2016 at 7:02

1 Answer 1

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

You must log in to answer this question.

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