## November 24, 2019

### Random Permutations (Part 3)

#### Posted by John Baez I’m trying to understand what a random permutation of a large set is typically like. While I’ve been solving some puzzles that shed a bit of light on this question, I now realize there are some other puzzles that would help more!

When I started, I had a wrong mental image of a random permutation of a large finite set. I foolishly imagined it would be made of many small orbits. But that’s far from true!

It’s easy to see why if you think about it. Given a random permutation $f\colon X \to X$ of a large $n$-element set, it’s very unlikely for $x \in X$ to be mapped to itself by $f$, or even by $f^k$ for some small $k$. So we should instead imagine our random permutation as consisting mainly of quite large orbits!

Here are the facts I’ve proved or at least stated so far:

• As $n \to \infty$, the probability that a random permutation of an $n$-element set has $k$ fixed points approaches

$\frac{1}{e \, k!}$

So there’s about a 37% chance of having no fixed points, a 37% chance of having one, an 18% chance of having two, a 6% chance of having three, and it drops off rapidly from there. I showed this in Part 1.

• The expected number of fixed points of a random permutation of a nonempty finite set is exactly 1.

In the $n \to \infty$ limit this follows from the previous remark. But in fact there’s an easy way to show it’s true for any $n \gt 0$. Do you see how?

• In the limit as $n \to \infty$, the probability that the shortest cycle in a random permutation of an $n$-element set has length $\gt k$ is

$e^{-\left(1 + \frac{1}{2} + \cdots + \frac{1}{k}\right)}$

So, there’s a 37% chance that the shortest cycle has length $\gt 1$, a 22% chance that it has length $\gt 2$, a 16% chance that it has length $\gt 3$, a 12% chance that it has length $\gt 4$, and it drops off slowly from there. I proved this in Part 2.

This is potentially misleading to the unwary. It says a random permutation of a huge set is quite likely to have at least one short cycle. But you shouldn’t assume it has lots of short cycles. Indeed, remark 2) says that it has just one cycle of length 1, on average.

• In the limit as $n \to \infty$, the average length of the longest cycle in a random permutation is $\lambda n$, where

$\lambda \approx 0.624$

I discussed in this in my post on the Golomb–Dickman constant, which is the name for this number $\lambda$. Dickman proved more: he computed the probability that the longest cycle in a random permutation of an $n$-element set has length $\le c n$, in the $n \to \infty$ limit. He showed it drops off very rapidly as $c$ decreases. For example, the probability that the longest permutation has length $\le n/10$ is less than $10^{-10}$, for large $n$.

This is makes it very interesting to probe the nature of large cycles. But the details of these, and many other aspects of random permutations, remain mysterious to me!

So, let me resume my puzzle series. These are puzzles for myself, or anyone who wants to help:

Puzzle 5. What is the expected number of cycles in a random permutation of an $n$-element set? What about the mode, or median?

Apparently the expected number of cycles is

$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$

As $n \to \infty$ this is asymptotically $\ln n$. That’s very small compared to the size of our set! This goes along with the fact that typically there are some rather large cycles. A proof is here, but it’s not easy to follow unless you go back and figure out the notation. I should write up a nice one.

I don’t know the mode or median.

Puzzle 6. What is the expected length of a cycle in a random permutation of an $n$-element set, asymptotically as $n \to \infty$? What about the mode, or median?

I haven’t worked this out, but I want the expected value to be asymptotically $n/ln n$.

Puzzle 7. What is the expected number of cycles of length $k$ in a random permutation of an $n$-element set?

The answer is apparently $1/k$ when $1 \le k \le n$. A proof is here, but I should explain it. Note that when $k = 1$ we’re back to my claim that the expected number of fixed points is $1$.

Here are some more puzzles designed to shed light on the large cycles in a random permutation:

Puzzle 8. If we choose an element of an $n$-element set, what is the probability that it lies in a cycle of length $k$?

The answer is very simple: $1/n$, for $1 \le k \le n$. In other words, it’s equally likely to be on a cycle of any allowed size! A proof is here, and again I want to explain it.

Puzzle 9. If we choose one element of an $n$-element set, what is the expected length of the cycle it lies on?

Thanks to Puzzle 8, the answer is $(n+1)/2$: the average of the natural numbers from $1$ to $n$.

Note that there can be at most one cycle of length $\gt n/2$. I’ll call such a cycle a giant cycle, because it reminds me of the giant connected component of a random graph.

Puzzle 10. How probable is the existence of a giant cycle?

When $n$ is even, the probability is

$\frac{1}{n+1} + \cdots + \frac{1}{2n}$

This is connected to the hundred prisoners problem. Something similar is true when $n$ is odd. As $n \to \infty$ the probability approaches $\ln 2$, or about 69.3%.

Okay, now I need to process all this information, write up proofs for some of these things, but most importantly synthesize all this information to get a better mental picture of a random permutation.

The way I see it now, when you have a random permutation of a large set, there’s a very good chance a substantial fraction of the elements lie on the largest cycle. If this happens, what about the rest? Is the permutation restricted to the rest of the set random in the same way—all elements of the permutation group equally likely? I think so.

If so, we can recursively ‘chip away’ at a random permutation, repeatedly removing the largest cycle, getting a kind of fractal structure where each time we do this, the random permutation of the remaining elements is governed by all the same rules I’ve listed here!

Posted at November 24, 2019 11:12 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3164

### Re: Random Permutations (Part 3)

But in fact there’s an easy way to show it’s true for any $n \gt 0$.

There’s also a “hard” way of finding the expected number of fixed points: decompose the natural linear representation of $S_n$ (as permutation matrices) and use that to compute the average of its character.

Posted by: unekdoud on November 25, 2019 9:21 AM | Permalink | Reply to this

### Re: Random Permutations (Part 3)

Nice! For an action of a finite group $G$ on a finite set $X$, we get a representation $\rho$ of $G$ on $L^2(X)$. For each $g \in G$, the trace

$\chi_\rho(g) \,\colon\!\!= tr(\rho(g))$

is the number of fixed points of the action of $g$ on $X$. The sum

$\frac{1}{|G|} \sum_{g \in G} \chi_\rho(g)$

thus gives us the average number of fixed points for a randomly chosen $g$. This sum equals

$\langle 1, \chi_\rho \rangle$

where we’re taking the inner product using the normalized translation-invariant measure on $G$. But this is

$\langle \chi_\tau, \chi_\rho \rangle$

where $\tau$ is the 1-dimensional trivial representation of $G$. And this inner product is the multiplicity with which the representation $\tau$ appears as a summand of $\rho$.

When $G$ acts in a doubly transitive way on $X$ things simplify, since then $\rho$ is the direct sum of $\tau$ and some other irreducible representation. Thus $\rho$ contains $\tau$ with multiplicity 1, so the inner product is 1, so the average number of fixed points is 1.

This happens for $G = S_n$ acting on the $n$-element set.

Posted by: John Baez on November 25, 2019 9:51 PM | Permalink | Reply to this

### Re: Random Permutations (Part 3)

Hello, hello, I’ve been a while away;

Akshay Venkatesh gave a fun public lecture about some of these questions, but lifted from random permutations to random braid links— about a month ago, viewable on youtube.

Posted by: Jesse C. McKeown on November 25, 2019 2:36 PM | Permalink | Reply to this

### Re: Random Permutations (Part 3)

Posted by: Abel Wolman on November 26, 2019 12:33 AM | Permalink | Reply to this

### Re: Random Permutations (Part 3)

Wow, that paper is great, Abel! Thanks!

I’m sort of glad I didn’t know about this paper earlier, because I might have never gotten up the nerve to think about random partitions… this paper contains so much information about them, so nicely explained.

But I love how it sets up and studies the analogy between cycle decompositions of permutations and prime factorizations of numbers.

Posted by: John Baez on November 26, 2019 2:03 AM | Permalink | Reply to this

Post a New Comment