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.

What I don't understand is how to get the lower bound on probability to have a double cycle on two vertices (without self-loops). To estimate it, the authors first calculate the expected number of double cycles on two vertices. It is ${m}\choose{3}$ $(1 - \frac{1}{n}) (\frac{2}{n^2})^2$. Here $(1 - \frac{1}{n})$ is probability that the first edge doesn't form a self-loop. And $(\frac{2}{n^2})^2$ is probability that two remaining edges are between the same two vertices as the first one. Next the authors write:

We easily observe that when $m = \Omega(n)$ this expectation is $\Omega(1/n)$. A calculation of the variance readily yields the probability that there is such a triple is also $\Omega(1/n)$, using the second moment method.

As I understood the authors mean that using the second moment method ($P(X = 0) \le \frac{Var[X]}{(E[X])^2}$), we can get that $P(X \ge 1) = 1 - P(X = 0) \ge 1 - \frac{Var[X]}{(E[X])^2} \ge 1 - n^2 Var[X] = \Omega(1/n)$. Here $X$ is a random variable that equals to the number of triples of edges that form double cycle on two vertices. So this means that Var[X] should be $\frac{1}{n^2} - \Theta(\frac{1}{n^3})$. I tried to calculate variance using the formula $Var[\sum_i X] = \sum_i Var[X_i] + \sum_{i \not=j} Cov(X_i, X_j)$ since $X_i$ and $X_j$ aren't independent. Here $X_i$ is an indicator random variable that equals one when $i$-th triple of edges form a double cycle on two vertices. But I always receive a complicated formula that looks like $c_1 \cdot \frac{1}{n} + c_2 \cdot \frac{1}{n^2} + c_3 \frac{1}{n^3}$. Here $c_1 \cdot \frac{1}{n}$ appears due to term $\sum_i Var[X_i]$ and since $Var[X_i] = \Theta(1/n^2)$. Is there a simpler way to calculate variance and show that $P(X \ge 1) = \Omega(1/n)$ or I have a mistake somewhere?

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.