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.

January 11, 2020

Random Permutations (Part 12)

Posted by John Baez

This time I’d like to repackage some of the results in Part 11 in a prettier way. I’ll describe the groupoid of ‘finite sets equipped with a permutation’ in terms of Young diagrams and cyclic groups. Taking groupoid cardinalities, this description will give a well-known formula for the probability that a random permutation belongs to any given conjugacy class!

Here is what we’ll prove:

Perm yY k=1 B(/k) y(k)y(k)! \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}

Let me explain the notation here.

First, Perm\mathsf{Perm} stands for the groupoid of finite sets equipped with permutation. Explicitly:

  • an object (X,σ)(X,\sigma) of Perm\mathsf{Perm} is a finite set XX with a bijection σ:XX\sigma \colon X \to X;
  • a morphism f:(X,σ)(X,σ)f \colon (X,\sigma) \to (X',\sigma') is a bijection f:XXf \colon X \to X' such that σ=fσf 1\sigma' = f \sigma f^{-1} .

Second, YY stands for the set of Young diagrams. A Young diagram looks like this:

but we will think of Young diagrams as functions y: +y \colon \mathbb{N}^+ \to \mathbb{N} that vanish at all but finitely many points. The idea is that a Young diagram yy has y(k)y(k) columns of length kk for each k=1,2,3,k = 1, 2, 3, \dots. For example, the Young diagram above has y(1)=1,y(2)=3,y(3)=1y(1) = 1, y(2) = 3, y(3) = 1 and y(n)=0y(n) = 0 for all other nn.

Third, B(G)\mathsf{B}(G) stands for the one-object groupoid corresponding to the group GG.

Fourth, for any category C\mathsf{C},

C kk! \frac{\mathsf{C}^k}{k!}

stands for the kkth symmetrized power of C\mathsf{C}. This is easiest to understand if we recall that the free symmetric monoidal category on C\mathsf{C}, say S(C)\mathsf{S}(\mathsf{C}), has a description as

S(C) k=0 C kk! \mathsf{S}(\mathsf{C}) \simeq \sum_{k = 0}^\infty \frac{\mathsf{C}^k}{k!}

where an object of C k/k!\mathsf{C}^k/k! is a kk-tuple (c 1,,c k)(c_1, \dots, c_k) of objects of C\mathsf{C} and a morphism is a kk-tuple (f 1,,f k)(f_1, \dots, f_k) of morphisms in C\mathsf{C} together with a permutation σS k\sigma \in S_k. The morphisms are composed in a manner familiar from the ‘wreath product’ of groups. Indeed, if GG is a group and B(G)\mathsf{B}(G) is the corresponding one-object groupoid, we have

B(G) kk!B(S kG k)(1) \frac{\mathsf{B}(G)^k}{k!} \simeq \mathsf{B}(S_k \ltimes G^k) \quad \quad (1)

where the semidirect product S kG kS_k \ltimes G^k is called the wreath product of S kS_k and GG.

Now that all the notation is defined, we can prove the result:

Theorem. There is an equivalence of groupoids

Perm yY k=1 B(/k) y(k)y(k)! \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}

Proof. First note that Perm\mathsf{Perm} is equivalent to its full subcategory where we use one finite set with each cardinality. It is thus equivalent to the groupoid where

  • an object is a natural number nn and an element σS n\sigma \in S_n,
  • a morphism f:(n,σ)(n,σ)f \colon (n,\sigma) \to (n, \sigma') is a permutation fS nf \in S_n such that σ=fσf 1\sigma' = f \sigma f^{-1} .

Thus, isomorphism classes of objects in Perm\mathsf{Perm} correspond to conjugacy classes of permutations. A conjugacy class of permutations is classified by its number of cycles of each length, and thus by a Young diagram y: +y \colon \mathbb{N}^+ \to \mathbb{N} saying that there are y(k)y(k) cycles of length kk for each k=1,2,3,k = 1, 2, 3, \dots.

In short, if we use π 0(G)\pi_0(G) to stand for the set of isomorphism classes of objects of the groupoid GG, we have established an isomorphism

π 0(Perm)Y \pi_0(\mathsf{Perm}) \cong Y

where YY is the set of Young diagrams. The groupoid Perm\mathsf{Perm} is thus equivalent to a coproduct of connected groupoids, one for each Young diagram:

Perm yYPerm y \mathsf{Perm} \simeq \sum_{y \in Y} \mathsf{Perm}_y

By taking a skeleton we can assume each groupoid Perm y\mathsf{Perm}_y has one object, namely (n,σ)(n,\sigma) where σS n\sigma \in S_n is a chosen permutation with y(k)y(k) cycles of length kk for each k=1,2,3,k = 1, 2, 3, \dots. The automorphisms of this object are then permutations fS nf \in S_n with σ=fσf 1\sigma = f \sigma f^{-1} .

In short, Perm y\mathsf{Perm}_y is the one-object groupoid corresponding to the centralizer of σS n\sigma \in S_n, where σ\sigma is any permutation with y(k)y(k) cycles of length kk for all kk.

We can choose σ\sigma to act on the boxes of the Young diagram yy, cyclically permuting the entries in each column in such a way that the first entry in each column is mapped to the second, the second is mapped to the third, and so on, with the last entry being mapped to the first. Any element of the centralizer of σ\sigma thus consists of a permutation of the columns, mapping each column to some other column of the same height, followed by an arbitrary cyclic permutation of the entries in each column. It follows that the centralizer is isomorphic to

k=1 S y(k)(/k) y(k) \prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)}

so

Perm yB( k=1 S y(k)(/k) y(k)) \mathsf{Perm}_y \simeq \mathsf{B} \left( \prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right)

Then, by equation (1) and the fact that B:GpGpd\mathsf{B} \colon \mathsf{Gp} \to \mathsf{Gpd} preserves products, we have

Perm y k=1 B(S y(k)(/k) y(k)) k=1 B(/k) y(k)y(k)! \begin{array}{ccl} \mathsf{Perm}_y &\simeq& \displaystyle{ \prod_{k=1}^\infty \mathsf{B} \left( S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right) } \\ \\ &\simeq & \displaystyle{ \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} } \end{array}

It follows that

Perm yYPerm y yY k=1 B(/k) y(k)y(k)! \begin{array}{ccl} \mathsf{Perm} &\simeq & \displaystyle{ \sum_{y \in Y} \mathsf{Perm}_y } \\ \\ &\simeq& \displaystyle{ \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} } \end{array}

as desired.   ■

Now let’s see how this result lets us compute the probability that a random permutation of an nn-element set lies in any given conjugacy class. The conjugacy classes in S nS_n correspond to Young diagrams yy with nn boxes. For each such yy we will compute the probability that a random element of S nS_n lies in the corresponding conjugacy class. Let’s call this probability p yp_y.

In general, the probability that a randomly chosen element of a finite group GG lies in some conjugacy class KK is |K|/|G||K|/|G|. But KG/C(k)K \cong G/C(k) where C(k)C(k) is the centralizer of some element kKk \in K. Thus, the probability in question equals 1/|C(k)|1/|C(k)|.

Recall that Perm y\mathsf{Perm}_y is one-object groupoid corresponding to the centralizer of some σS n\sigma \in S_n whose conjugacy class corresponds to the Young diagram yy. The cardinality of a one-object groupoid is the reciprocal of the cardinality of the corresponding group, so

|Perm y|=1|C(σ)| |\mathsf{Perm}_y| = \frac{1}{|C(\sigma)|}

It follows that

p y=|Perm y| p_y = |\mathsf{Perm}_y|

In other words, the probability we are trying to compute is the cardinality of a groupoid we have already studied! We saw in the proof of the Theorem that

Perm yB( k=1 S y(k)(/k) y(k)) \mathsf{Perm}_y \simeq \mathsf{B} \left( \prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right)

so

p y = |Perm y| = k=1 1|S y(k)(/k) y(k)| = k=1 1y(k)!k y(k) \begin{array}{ccl} p_y &=& |\mathsf{Perm}_y| \\ \\ &=& \displaystyle{ \prod_{k=1}^\infty \frac{1}{|S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)}| } } \\ \\ &=& \displaystyle{ \prod_{k=1}^\infty \frac{1}{y(k)! \, k^{y(k)} } } \end{array}

So, we get a well-known result:

Theorem. The probability p yp_y that a random permutation of an nn-element set has y(k)y(k) cycles of length kk for all k=1,2,3,k = 1, 2, 3, \dots is given by

p y= k=1 1y(k)!k y(k) p_y = \prod_{k=1}^\infty \frac{1}{y(k)! \, k^{y(k)}}

The theorem is easy to prove, so the point is just that this probability is the cardinality of a naturally defined groupoid, and a similar formula holds at the level of groupoids:

Perm y k=1 B(/k) y(k)y(k)! \mathsf{Perm}_y \simeq \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}


Here is the series so far, on my website:

  • Part 0 — What’s the average length of the longest cycle in a random permutation of an nn-element set?
  • Part 1 — What is the probability that a randomly chosen permutation of an nn-element set has exactly kk fixed points?
  • Part 2 — What is the probability that the shortest cycle in a randomly chosen permutation of an nn-element set has length greater than kk?
  • Part 3 — A large collection of questions about random permutations, with answers.
  • Part 4 — What is the probability that a randomly chosen permutation of an nn-element set has a cycle of length greater than n/2n/2?
  • Part 5 — What is the average length of a cycle in a randomly chosen permutation of an nn-element set?
  • Part 6 — What expected number of cycles of length kk in a randomly chosen permutation of an nn-element set?
  • Part 7 — How is the distribution of the number of cycles of length kk in a random permutation related to a Poisson distribution?
  • Part 8 — What’s the nnth moment of a Poisson distribution?
  • Part 9 — If we treat the number of cycles of length kk in a random permutation of an nn-element set as a random variable, what do the moments of this random variable approach as nn \to \infty?
  • Part 10 — How to compute statistics of random permutations using groupoid cardinalities.
  • Part 11 — How to prove the Cycle Length Lemma, a fundamental result on random permutations, using groupoid cardinalities.
  • Part 12 — How to write the groupoid of finite sets equipped with a permutation as a sum over Young diagrams, and how to use this to compute the probability that a random permutation has given cycle lengths.
Posted at January 11, 2020 4:44 AM UTC

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

5 Comments & 0 Trackbacks

Re: Random Permutations (Part 12)

A gorgeous piece of objective mathematics! As this whole series has been.

Posted by: David Jaz Myers on January 12, 2020 6:39 AM | Permalink | Reply to this

Re: Random Permutations (Part 12)

Thanks! Too bad Ayn Rand’s brand of objectivism missed the point.

Posted by: John Baez on January 12, 2020 6:48 AM | Permalink | Reply to this

Re: Random Permutations (Part 12)

Ha!

I’d like to try my hand at further objectifying your proof. Namely, I want to get at the term B/k y(k)y(k)\frac{B\mathbb{Z}/k^{y(k)}}{y(k)} more objectively.

I’ll work in homotopy type theory, since it’s what I know and it makes working with groupoids a breeze. So, with that in mind, we can define

Perm:(X:Fin)×(X=X){Perm} :\equiv (X : {Fin}) \times (X = X)

to be the type of finite sets equipped with an automorphism. I’ll refer to an element of Perm{Perm} by its permutation. For σ:{1,,n}={1,,n}\sigma : \{1, \ldots, n\} = \{1,\ldots, n\}, define Perm σ:BAut Perm(σ){Perm}_{\sigma} :\equiv {BAut}_{{Perm}}(\sigma) to be the type of permutations identifyable with σ\sigma. Here, I’m using the general definition BAut X(x):(y:X)×||x=y||{BAut}_{X}(x) :\equiv (y : X) \times ||x = y|| for any x:Xx : X as the type of elements of XX which are somehow identifyable with xx.

Just a few more definitions. Define B/k:BAut Perm(+1:/k=/k){B}\mathbb{Z}/k :\equiv {BAut}_{{Perm}}(+1 : \mathbb{Z}/k = \mathbb{Z}/k) to be the type of cyclic permutations of size kk. Finally, for any type GG and k:k : \mathbb{N} we define G kk!:(X:BAut(k))×G X\frac{G^k}{k!} :\equiv (X : {BAut}(k)) \times G^X to be the type of pairs consisting of a kk-element set XX and an XX-indexed tuple of elements of GG.

Almost there – we still need to know what Young diagrams are. I’m going to define a Young diagram instead to be a function Y: +FinY : \mathbb{N}^+ \to {Fin} sending a positive natural number to a finite set so that the union over all n: +n : \mathbb{N}^+ is finite. Then the Young diagram associated to the permutation σ\sigma sends each positive natural kk to the set Y σ(k)Y_{\sigma}(k) of kk-cycles in σ\sigma, considered as subactions of σ\sigma.

Now, we can state the result: Perm σ=(k: +)(Z:BAut(Y σ(k))×B/k Z.{Perm}_{\sigma} = (k : \mathbb{N}^+) \to (Z : {BAut}(Y_{\sigma}(k)) \times {B}\mathbb{Z}/k^{Z}.

We can construct such an equivalence very explicitly. Given a permutation α\alpha identifiable with σ\sigma, and a positive kk, we have that Y α(k)Y_{\alpha}(k) is identifiable with Y σ(k)Y_{\sigma}(k). Given a cycle C:Y α(k)C : Y_{\alpha}(k), CC itself is a cyclic permutation of size kk and therefore C:B/kC : {B}\mathbb{Z}/k. So the map from left to write sends α\alpha to k(Y α(k),CC)k \mapsto (Y_{\alpha}(k), C \mapsto C).

On the other hand, suppose we have a function assigning to each positive number kk a set Z kZ_k of the same cardinality as Y σ(k)Y_{\sigma}(k), together with a function assigning each element cc of Z kZ_k a cyclic permutation α c\alpha_c. Then the disjoint union of the α c\alpha_c over all cc and kk gives us a permutation α\alpha. To show that this is identifiable with σ\sigma, suppose that Z kZ_k was actually Y σ(k)Y_{\sigma}(k). Then B/k Z k{B}\mathbb{Z}/k^{Z_k} is connected, so we can assume again that the α c\alpha_c are actually CC for C:Y σ(k)C : Y_{\sigma}(k). But σ\sigma is the disjoint union of its cycles, so we’ve identified α\alpha with σ\sigma.

That these are inverse to eachother is pretty straightforward to check. If I write it in less Agda-inspired notation it now looks just like we want it: Perm σ= k=1 B/k y(k)y(k)!.{Perm}_{\sigma} = \prod_{k = 1}^{\infty} \frac{{B}\mathbb{Z}/k^{y(k)}}{y(k)!}.

Posted by: David Jaz Myers on January 13, 2020 6:03 AM | Permalink | Reply to this

Re: Random Permutations (Part 12)

Very minor notational issue: BB is in math italics in the first equation and in sans-serif nonitalic type later. I presume the latter is the desired convention.

Posted by: Blake Stacey on January 12, 2020 7:51 PM | Permalink | Reply to this

Re: Random Permutations (Part 12)

Thanks! I’m trying to go with a notation where categories (and thus groupoids) are in \mathsf font, while mere sets are in \mathrm.

Posted by: John Baez on January 12, 2020 10:15 PM | Permalink | Reply to this

Post a New Comment