# Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

I was told this question may be better received here.

Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, where $n$ is the number of elements in the set.

I'm trying to use induction, but I don't know if this is the best method to go about proving this.

The worst case to probe $1$ array location would be when all $n$ element are stored in the first table, and we get probability $\frac{n}{2n} = \frac{1}{2} = O(\frac{1}{\sqrt{2}})$ for insertion.

The worst case to probe $2$ array locations would be when all $n$ elements are stored in the first table, we hit the first table, and we succeed in the second table. This has the same probability as it does to probe $1$ array location.

However, I don't know how to continue the analysis. For example, what's the worst case probability to probe $4$ array locations? The question statement implies that the worst case is $O(\frac{1}4)$, but how do we achieve this result? If the first and second tables each have $\frac{1}4$ of their array locations occupied, then the worst case to probe $4$ elements would be hitting in the first table, hitting in the second table, hitting in the first table again, then finally inserting into the second table $\Rightarrow \frac{1}4\cdot\frac{1}4\cdot\frac{1}{4}\cdot\frac{3}4 = \frac{3}{256} \not = \frac{1}4$.

Basically, you just write down everything that is necessary to have $t$ evictions and then use the universality of your hash functions to bound the probability.

Assume you want to insert $x$ and your hash functions are $f,g$. Then if you have $t$ probes if $f(x)$ is occupied that is \begin{align} \mathbb{P}[t=1]& =\sum_{y \neq x} \mathbb{P}[f(x)=f(y)]\\ &\le n \cdot 1/s \le 1/2. \end{align} since your hash function are $(1,k)$-universal (I assume).

Now for $t=2$, the place of $f(x)$ have to be occupied by some element $y$ (that is $f(x)=f(y)$), and the alternative for $y$ is blocked by some other element $z$ (that is $g(y)=g(z)$). Summing up over all possible values for $y$ and $z$ gives \begin{align} \mathbb{P}[t=2]& =\sum_{y,z \neq x} \mathbb{P}[f(x)=f(y) \text { and } g(y)=g(z) ]]\\ &\le n^2 \cdot 1/s^2 \le 1/4. \end{align}

The summands of the sum are bounded by $1/s^2$ due to the universality of the hash functions, and you have less than $n^2$ summands.

I think from here you can continue by yourself.

• Thank you for your answer. Can you please explain what the summation precisely means? I'm having trouble understanding, for example, when $t=2$, why the summation is what it is. What does it mean when we have the probability of $f(x)=f(y)$ and $g(y)=g(z)$. Why is this $n^2 \cdot 1/s^2$? Dec 1 '14 at 22:02
• @Kelsey: I extended my answer Dec 2 '14 at 7:27
• Sorry, I'm at a relatively elementary understanding with this material. What does the statement $\Pr[f(x)=f(y)]$ really mean? Why does this represent the fact that we're probing $1$ time? Similarly, why does $\Pr[f(x)=f(y)\wedge g(y)=g(z)]$ represent that we're probing $2$ times? Dec 2 '14 at 7:40
• $f(x)=f(y)$ just describes that the cell where you want to put $x$ is already occupied with some other element ($y$). So you probe at least once/ The bounds on the probabilities comes from the definition of the $(k,\ell)$-universal hash function. I really couldn't say more. If you still have questions you might have a look at the analysis of cuckoo hashing as done in some lecture notes you might find in the www. Dec 2 '14 at 8:13
• That makes sense. Thank you. So for $t=k$, the probability is just $\le n^k\cdot 1/s^k \le 1/2^k$ (for some $k > 2$)? Dec 2 '14 at 8:16