# Probability lower bound on a double cycle on two vertices in random cuckoo graph

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!