Probability of being close to a cycle permutation is $o(1)$

Question

I'm trying to prove that in some sense, cycle (maybe circular is a better wording?) permutations are "sparse" in the set of all permutations $S_n$. Let's assume permutations distribute uniformly out of the $n!$ combinations. It is clear that the probability of getting a cycle permutation is $\frac{1}{n}$. My question is what happens when we "dilate" the set according the the Hamming distance
$$d(\sigma, \pi) = \frac{1}{n}\left |\left \{ i: \sigma(i)\ne \pi(i)\right \}\right |$$
Then denote the event of being $\epsilon$-close to a cycle, i.e. $d(\sigma, \text{set of all cycles})<\epsilon$, for instance for $\epsilon = \frac{1}{4}$. How can I show this occurs in probability $o(1)$ if this is even true? I tried to upper-bound the probability by considering in how many ways I can degrade any $\frac{n}{4}$ indices of a given cycle, while still remaining a permutation, and got the bound $\frac{(n-1)!\binom{n}{n/4}(\frac{n}{4})!}{n!}$ which is way too loose. I thought of maybe representing the number of changes to get a cycle as a sum of indicator random variables somehow, and bound the probability to deviate from the expectation.

Answer 1

Let our permutation consists of $k$ cycles $(a^1_1\ldots a^1_{n_1})(a^2_1 \ldots a^2_{n_2})\ldots(a^k_1\ldots a^k_{n_k})$. Then its Hamming distance to the cycle $a^1_1 \ldots a^1_{n_1} a^2_1 \ldots a^k_{n_k})$ is just $k$ (we need to change where $a^i_{n_i}$ go).

Now, let's count expected number of cycles of length $x$ in random permutation. Probability of any given point to be in such cycle is $\frac{1}{n}$: to have a cycle of length $x$ with point $a_1$ we need $a_1$ go to some point $a_2 \neq a_1$, probability of this is $\frac{n - 1}{n}$, then we need $a_2$ go to some point other then $a_1$ - probability of this, conditional on $a_1$ goes to $a_2$, is $\frac{n - 2}{n - 1}$, etc., and finally $a_x$ needs to go to $a_1$, probability of it conditionally on everything before is $\frac{1}{n - x + 1}$. Multiplying, we get $\frac{n - 1}{n} \cdot \frac{n - 2}{n - 1} \cdot \ldots \cdot \frac{n - x + 1}{n - x + 2} \cdot \frac{1}{n - x + 1} = \frac{1}{n}$.

Number of cycles of length $x$ is equal to number of points in such cycles divided by $x$, expected number of points in such cycles is $1$, thus expected number of cycles of length $x$ is $\frac{1}{x}$.

Expected total number of cycles (of any length) is $\sum_{i=1}^n \frac{1}{i} = \log(n) + O(1)$.

It's probably should not be too hard to get much better estimation, but for your question it's enough to note that probability of having more than $4\log n$ cycles is less than $\frac{1}{2}$ (otherwise average number of cycles would be higher than $2\log(n)$).

So, random permutation with probability at least $\frac{1}{2}$ has at most $4\log n$ cycles, and thus is at distance of at most $\frac{4 \log n}{n}$ from a cycle.

And as $\frac{4 \log n}{n} < \frac{1}{4}$ for large enough $n$, we have that probability of random permutation to be $\epsilon$-close to set of cycles is at least $\frac{1}{2}$, which isn't $o(1)$.