## A quick reminder

Recall the definitions: $\pi : X\toX$ is a random permutation we'd like to invert.

We prepare $m$ chains, of length $t$ each, $C_i = \big(s_i, \pi(s_i), \pi(\pi(s_i), \ldots, e_i = \pi(\pi(\cdots\pi(s_i)\cdots))\big)$.

The preprocessing step requires $mt$ applications of $\pi$, but only needs to be done once. After it, we store only $(s_i, e_i)$ for every chain, using $O(m)$ memory.

Now we can perform the $O(t)$ time algorithm shown in class to try to invert a single value $y$. This succeeds exactly when $y$ is covered by any chain.

## Calculating the success probability

### The ideal estimate

Ideally, we have $mt$ elements covered by the chains, so the probability to succeed in calculating $\pi^{-1}(y)$ is $mt / |X|$.^{1}

This is of course an over-estimation since not all $mt$ elements are distinct.

For instance, a single chain can lie in a short cycle of $\pi$ (of length $<t$), and then $|C_i| < t$; another problem is elements covered by multiple chains.

### An almost rigorous calculation

Assume for now $mt = |X|$; we'd like to show that the success probability $p$ is a constant.

We will use the following claim (try to prove it, it's really easy):

**Claim 1.** For a random permutation $\pi : X\toX$, the length of the cycle of $\pi$ to which a given $x\in X$ belongs is distributed uniformly in ${1, 2, \ldots, |X|$.

We are interested in calculating the expected size of $C_1 \cup C_2 \cup \cdots \cup C_m$.

By the inclusion-exclusion principle,

so we need to calculate two values: $A_1 = E(|C_i|)$ and $A_2 = E(|C_i \cap C_j|)$.

If the starting point $s_i$ lies in a cycle of length $k$, then $|C_i| = \min(k,t)$. Using Claim 1, we can calculate

(2)Given that the point $x\in X$ lying in a cycle of length $k$, $P(x\in C_i \cap C_j) = \min(k,t)^2/|X|^2$. Using Claim 1 again,

(3)Putting it all together,

(4)## Remarks

We stopped the inclusion-exclusion calculation after two steps; had we continued it to the end, we'd get $p = 1 - \frac12 + \frac1{3!} - \cdots + \cdots = 1-1/e$, which is the "right" constant.

Moreover, if we take $mt = \alpha|X|$, we'd get $p = \alpha - \frac{\alpha^2}{2} + \frac{\alpha^3}{3} - \cdots + \cdots = 1-e^{-\alpha}$.