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

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.

• what's a cycle permutation? a full single cycle? Commented Jun 22, 2022 at 14:55
• @kodlu Yes, one of the $(n-1)!$ options. The "closeness" is measured by taking to minimal distance to one of them. Commented Jun 22, 2022 at 15:00

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)$$.

• Thank you! I have 2 follow-ups. 1. How do you know that for a given point, it has an equal odds to be in each cycle length i.e. prob. $\frac{1}{n}$? am I missing a symmetry here? 2. The bottom line you stated that in a constant probability we are at distance $o(1)$ from a cycle, how does that relate to what I wanted: at probability $o(1)$ we are $\frac{1}{4}$-close to a cycle? Commented Jun 22, 2022 at 20:45