# Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

I was reading this very good summary of Cuckoo hashing.

It includes a result (page 5) that:

A stash of constant sizes reduces the probability of any failure to fall from $$\Theta(1/n)$$ to $$\Theta(1/n^{s+1})$$ for the case of $$d= 2$$ choices

It references the paper KMW08. But KMW08 only has the result (Theorem 2.1) that:

For every constant integer $$s \geq 1$$, for a sufficiently large constant $$\alpha$$, the size $$S$$ of the stash after all items have been inserted satisfies $$Pr(S \geq s) =O(n^{-s})$$.

Note that the $$s$$ in the different theorems is slightly different, in the first if the stash is of size $$s$$, it is not a failure, in the second, if the stash is of size $$s$$ it is a failure. This is why the first has $$s+1$$ and the second has $$s$$.

The difference between the two is then that the first uses theta-notation, whereas the second uses big-O notation. So my questions:

• Do we know that the failure probability is $$\Omega(n^{-(s+1)})$$?
• If so, do we know the constants in the $$\Theta(n^{-(s+1)})$$ expression?

And if so, which papers presented these results?