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 and acknowledge you have read our privacy policy.