2
$\begingroup$

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got stuck with a problem.

We have $m$ elements and $n$ buckets. Each element is hashed into two random buckets (we assume that two our hash functions are completely random). If each bucket corresponds to a vertex and each element corresponds to an edge. Then we have a random graph with $n$ vertices and $m$ edges. Loops and multi-edges are allowed.

I don't understand how to get the probability to reconstruct the whole cuckoo hash table. We reconstruct (reinsert all elements with new hash functions) a cuckoo hash table when a connected component has a double cycle. We can calculate probability that after inserting an element a double cycle occurs. This probability is $\mathcal{O}(1/n^2)$. To prove this, we consider the situation when the last inserted element creates a double cycle on exactly $k$ elements. Then before the insertion there were $k$ edges among these $k$ vertices. There are ${n}\choose{k}$ ways of choosing these vertices, and ${m}\choose{k}$ ways of choosing the items that correspond to the edges. Then the authors write the following sentence which I don't understand but I think it's kind of crucial:

After adding the new edge for the inserted item, the k + 1 edges must form a spanning tree, as well as two additional edges.

Don't $k + 1$ edges suppose to form double cycle not a spanning tree? Wasn't the spanning tree formed even before the insertion since we had $k$ vertices and $k$ edges among them? Also I don't understand why two additional edges must form a spanning tree and how is this fact connected to what we want to prove at all?

Next, the authors write the formula for probability we want to calculate:

${n}\choose{k}$ ${m}\choose{k}$ $k^{k - 2}$ ${k + 1}\choose{2}$ $(k - 1)! \cdot \dots$.

This formula isn't complete but my question about this part. Here $k^{k - 2}$ -- the number of trees on $k$ vertices, $(k-1)!$ -- the number of ways to map $k-1$ elements into $k-1$ edges. I don't understand the term ${k + 1}\choose{2}$. Why do we choose $2$ edges from $k + 1$? Shouldn't we choose only one edge from $k$ edges? My point is that $k - 1$ edges form a spanning tree on $k$ vertices and one remaining edge as well as the edge that corresponds to the new item should form two cycles. Then we can choose the remaining edge in $k$ ways. I think the formula should be:

${n}\choose{k}$ ${m}\choose{k}$ $k^{k - 2}$ $k$ $(k - 1)! \cdot \dots$.

Could you please explain me the details. May be I don't understand something?

Thank you!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.