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 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:XXf \colon X \to X is a permutation of an nn-element set. Let’s say a cycle of ff is a giant cycle if it has length >n/2\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 nn-element set has a giant cycle?

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

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

Take an nn-element set XX. Choosing a permutation of XX with a cycle of length kk is the same as choosing a kk-element subset SXS \subseteq X, a cyclic ordering on SS, and an arbitrary permutation of XSX - S.

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

(nk)(k1)!(nk)!=n!(k1)!(nk)!k!(nk)!=n!k \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 nn-element set with a cycle of length kk.

Dividing by n!n!, we get

1k \frac{1}{k}

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

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

1n/2+1++1n1+1n \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 nn \to \infty this sum approaches

lnnln(n/2)=ln20.693 \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 nn \to \infty, there’s a 50% probability that a random permutation of an nn-element set will have a cycle of length at least e 1/2ne^{-1/2}n. Since

e 1/20.6065e^{-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

3 Comments & 0 Trackbacks

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 (n1)(n-1)th-subgiant cycle as containing more then 1/n1/n of the total, won’t there be at most n1n-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

Post a New Comment