Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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:XXf\colon X \to X of a large nn-element set, it’s very unlikely for xXx \in X to be mapped to itself by ff, or even by f kf^k for some small kk. 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 nn \to \infty, the probability that a random permutation of an nn-element set has kk fixed points approaches

1ek! \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 nn \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>0n \gt 0. Do you see how?

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

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

So, there’s a 37% chance that the shortest cycle has length >1\gt 1, a 22% chance that it has length >2\gt 2, a 16% chance that it has length >3\gt 3, a 12% chance that it has length >4\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 nn \to \infty, the average length of the longest cycle in a random permutation is λn\lambda n, where

λ0.624 \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 nn-element set has length cn\le c n, in the nn \to \infty limit. He showed it drops off very rapidly as cc decreases. For example, the probability that the longest permutation has length n/10\le n/10 is less than 10 1010^{-10}, for large nn.

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 nn-element set? What about the mode, or median?

Apparently the expected number of cycles is

1+12+13++1n 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}

As nn \to \infty this is asymptotically lnn\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 nn-element set, asymptotically as nn \to \infty? What about the mode, or median?

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

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

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

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 nn-element set, what is the probability that it lies in a cycle of length kk?

The answer is very simple: 1/n1/n, for 1kn1 \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 nn-element set, what is the expected length of the cycle it lies on?

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

Note that there can be at most one cycle of length >n/2\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 nn is even, the probability is

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

This is connected to the hundred prisoners problem. Something similar is true when nn is odd. As nn \to \infty the probability approaches ln2\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

5 Comments & 0 Trackbacks

Re: Random Permutations (Part 3)

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

There’s also a “hard” way of finding the expected number of fixed points: decompose the natural linear representation of S nS_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 GG on a finite set XX, we get a representation ρ\rho of GG on L 2(X)L^2(X). For each gGg \in G, the trace

χ ρ(g):=tr(ρ(g))\chi_\rho(g) \,\colon\!\!= tr(\rho(g))

is the number of fixed points of the action of gg on XX. The sum

1|G| gGχ ρ(g) \frac{1}{|G|} \sum_{g \in G} \chi_\rho(g)

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

1,χ ρ \langle 1, \chi_\rho \rangle

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

χ τ,χ ρ \langle \chi_\tau, \chi_\rho \rangle

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

When GG acts in a doubly transitive way on XX 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 nG = S_n acting on the nn-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)

Regarding this talk, Akshay Venkatesh suggested this paper by Andrew Granville:

https://dms.umontreal.ca/~andrew/PDF/Anatomy.pdf

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