3
$\begingroup$

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

Does anyone have a clearer way of thinking about this problem?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Kelsey Dec 1 '14 at 22:02
  • $\begingroup$ @Kelsey: I extended my answer $\endgroup$ – A.Schulz Dec 2 '14 at 7:27
  • $\begingroup$ 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? $\endgroup$ – Kelsey Dec 2 '14 at 7:40
  • $\begingroup$ $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. $\endgroup$ – A.Schulz Dec 2 '14 at 8:13
  • $\begingroup$ 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$)? $\endgroup$ – Kelsey Dec 2 '14 at 8:16

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.