## November 25, 2019

### Random Permutations (Part 4)

#### Posted by John Baez

Last time I listed a bunch of facts designed to improve our mental picture of a typical randomly chosen permutation. Many of these facts are fun to prove using generating functions. But one has a more elementary proof.

Namely: a random permutation of a large finite set has an almost 70% chance of having a single cycle that contains at least half the elements!

This really solidifies my image of a typical permutation of a large finite set. It consists of one big cycle involving most of the elements… and the rest, which is a typical permutation of the remaining smaller set.

Suppose $f \colon X \to X$ is a permutation of an $n$-element set. Let’s say a cycle of $f$ is a giant cycle if it has length $\gt n/2$. A permutation can contain at most one giant cycle — and as we shall see, this makes this puzzle easy:

Puzzle 10. What is the probability that a randomly chosen permutation of an $n$-element set has a giant cycle?

We’ll actually solve a more detailed problem. Suppose $k \gt n/2$. What is the probability that our permutation has a cycle of length $k$?

To solve this, we can just count permutations with a cycle of length $k$ and divide by $n!$. There is no problem with double counting, since each permutation has at most one giant cycle.

Take an $n$-element set $X$. Choosing a permutation of $X$ with a cycle of length $k$ is the same as choosing a $k$-element subset $S \subseteq X$, a cyclic ordering on $S$, and an arbitrary permutation of $X - S$.

There are $\binom{n}{k}$ choices of $S$, $(k-1)!$ cyclic orderings on $S$, and $(n-k)!$ permutations of $X - S$. Multiplying these, we get

$\binom{n}{k} (k-1)! (n-k)! = \frac{n! (k-1)! (n-k)!}{k! (n-k)!} = \frac{n!}{k}$

So that’s the number of permutations of an $n$-element set with a cycle of length $k$.

Dividing by $n!$, we get

$\frac{1}{k}$

So that’s the probability that a random permutation of an $n$-element set has a cycle of length $k$, assuming $k \ge n/2$.

Now we can answer the puzzle! The probability that a random permutation of an $n$-element set has a giant cycle is just the sum of $1/k$ over all $k$ with $n/2 \lt k \le n$:

$\frac{1}{\lfloor n/2 \rfloor + 1} + \cdots + \frac{1}{n-1} + \frac{1}{n}$

Again there’s no double-counting problem, since these cases are exclusive.

As $n \to \infty$ this sum approaches

$\ln n - \ln (n/2) = \ln 2 \approx 0.693$

So, a random permutation of a huge set has about a 69.3% chance of containing a giant cycle.

We can have a bit more fun with this: in the limit as $n \to \infty$, there’s a 50% probability that a random permutation of an $n$-element set will have a cycle of length at least $e^{-1/2}n$. Since

$e^{-1/2} \approx 0.6065$

we know the median length of the largest cycle in a random permutation of a huge set! It’s about 60.6% the size of the set itself.

This is a nice counterpart to a harder result we saw before: the mean length of the longest cycle is about 62.4% times the size of the set. Sometimes the mean and median are vastly different, but not here.

In all these calculations it was crucial that we worked with giant cycles. With more work perhaps we could handle subgiant cycles: that is, those containing more than 1/3 of the elements of our set. A permutation can have at most two subgiant cycles, so the double-counting problems we dodged above might still be manageable. But in general, computing the probability that a random permutation has a certain number of cycles of lengths in certain ranges will call for better techniques.

Posted at November 25, 2019 8:27 PM UTC

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

### Re: Random Permutations (Part 4)

Thank you for these posts on random permutations. I have been enjoying them. A while ago I was looking at the expected transposition distance (normalized so that the max distance is 1. If I recall correctly, in the limit almost all had distance 1.) Also, it seems like random partitians should be both independently interesting and relevant here (since permutations fiber over the partitians).

Posted by: ana N mouse on November 26, 2019 1:21 PM | Permalink | Reply to this

### Re: Random Permutations (Part 4)

Small mistake; can’t there be at most 3 subgiant cycles, each between 1/4 and 1/3 the total? In general if we define an $(n-1)$th-subgiant cycle as containing more then $1/n$ of the total, won’t there be at most $n-1$ of them?

Posted by: mark biggar on November 28, 2019 6:08 PM | Permalink | Reply to this

### Re: Random Permutations (Part 4)

Whoops! Thanks! I’ll fix my article. I guess I’ll define a subgiant cycle to mean one that contains more than 1/3 the elements of our set, and say that a permutation can’t have more than 2 subgiant cycles.

There are various alternatives and generalizations, and trying to actually prove something would help clarify what’s best. But I’m too lazy for that right now!

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

### Re: Random Permutations (Part 4)

Isn’t there a more direct way to see that the fraction of permutations with a giant k-cycle is 1/k?

It’s clear enough that the product of the three factors reduces to 1/k, but it would be nice with a simpler and direct argument why it is so.

Posted by: Hans Hurvig on September 5, 2022 8:30 PM | Permalink | Reply to this

### Re: Random Permutations (Part 4)

I asked this question on Math Stackexchange, and Greg Martin gave an interesting answer.

First step: suppose you have a random permutation of an $n$-element set $X$. Then he shows that for any $1 \le k \le n$, the probability that $x \in X$ is contained in a $k$-cycle is $1/n$. I think this is the really fundamental fact in this game.

Next suppose $\frac{n}{2} \, <\, k \le n$. Now there’s at most one $k$-cycle. Since fraction of elements in a $k$-cycle is $k/n$ if it exists, the expected number of $k$-cycles must be $1/k$. The argument here does involve some cancellation:

$\frac{1}{n} = \frac{k}{n} \cdot \frac{1}{k}$

However, he has a nice argument that for any $1 \le k \le n$, the probability of $x \in X$ being contained in a $k$-cycle is $1/n$.

Posted by: John Baez on September 6, 2022 10:09 AM | Permalink | Reply to this

Post a New Comment