Seeking proof of the Cuckoo Cycle Conjecture

Question

Allow me to introduce the Cuckoo Cycle Proof of Work, and conclude with a closely related Conjecture about random graphs, which I hope someone can find a proof for.

Cuckoo Cycle is named after the Cuckoo Hashtable, in which each data item can be stored at two possible locations, one in each of two arrays. A hash function maps the pair of item and choice of array to its location in that array. When a newly stored item finds both its locations already occupied, one is kicked out and replaced by the new item. This forces the kicked-out item to move to its alternate location, possibly kicking out yet another item. Problems arise if the corresponding Cuckoo graph, a bipartite graph with array locations as nodes and item location pairs as edges, has cycles.

While $n$ items, whose edges form a cycle, could barely be stored in the table, any $n+1$st item mapping within the same set of locations (a chord in the cycle) would not fit, as the pigeonhole principle tells us.

In the Proof-of-Work problem, we typically set $n \ge 29$, and use edge indices (items) $0 \dots N-1$, where $N = 2^n$. The endpoints of edge $i$ are (siphash(i|0) % N, siphash(i|1) % N), with siphash being a popular keyed hash function. A solution is a cycle of length $L$ in this bipartite Cuckoo graph, where typically $L = 42$.

Cuckoo Cycle solvers spend nearly all cycles on edge trimming; identifying and removing edges that end in a leaf node (of degree 1), as such edges cannot be part of a cycle. Trimming rounds alternate between the two node partitions.

The fraction $f_i$ of remaining edges after $i$ trimming rounds (in the limit as $N$ goes to infinity) appears to obey

The Cuckoo Cycle Conjecture: $f_i = a_{i-1} * a_i$, where $a_{-1} = a_0 = 1$, and $a_{i+1} = 1 - e^{-a_i}$

$f_i$ could equivalently be defined as the fraction of edges whose first endpoint is the middle of a (not necessarily simple) path of length $2i$. So far I have only been able to prove the conjecture for $i \le 3$. For instance, for i = 1, the probability that an edge endpoint is not the endpoint of any other edge is (1-1/N)^N-1 ~ 1/e.

Here's hoping someone finds an elegant proof...

Answer 1

Theorem. Let $f_i$ be expected value of fraction of remaining edges after $i$ trimming rounds for Cuckoo graph; here $i \in \mathbb{N}_0$. Then $f_i = a_i a_{i-1}$; here $a_{-1} = a_{0} = 1$, $a_{i+1} = (1-e^{-a_i})$.

Proof. The proof is by induction over the trimming round $i$. For $i = 0$ it is evident.

Let us prove for $i+1$. By $E$ denote a set of edges for initial Cuckoo graph. By $E'$ denote a set of edges that end in a leaf node for trimmed graph after $i-1$ rounds, $i > 0$. Let us introduce indicator random variable for edge $e$: $$ \xi(e) = \begin{cases} 1, & e \in E' \\ 0, & e \not\in E'. \\ \end{cases} $$

Consider the following Bernoulli scheme for edge $e$. Succes is $e \in E'$. The probability of success is $\frac{1}{|E|}$. Then the probability that number of successes on the $(|E|a_i)^{th}$ trial is equal to one the following: $$ C^1_{|E|a_i} \left(\frac{1}{|E|}\right)^1 \left(1 - \frac{1}{|E|}\right)^{|E|a_i-1} = \frac{a_i}{e^{a_i}} $$ as $|E| \to \infty$.

So $\mathbb{E}[\xi(e)] = \frac{a_i}{e^{a_i}}$. Then using linearity of expectation, we get $\mathbb{E}[|E'|] = \frac{|E|a_i}{e^{a_i}}$.

Further by the inductive assumption: $f_{i+1} = a_{i+1}a_i = (1-e^{-a_i})a_i = (a_i-a_ie^{-a_i})$. Then using linearity of expectation, we get $f_{i+1}|E| = a_{i+1}a_i|E| = (a_i-a_ie^{-a_i})|E|$ $=$ $a_i|E| - |E|a_ie^{-a_i}$. It follows that $a_{i+1}a_i|E| = a_i|E| - |E'|$ and it is clear. Finally, we get the following: $a_{i+1} = 1 - a_ie^{-a_i}$. This completes the proof of theorem.