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!


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.