|
|
|
I want to go back over something from Part 11, but in a more systematic and self-contained way.
Namely, I want to prove the Cycle Length Lemma using a bit of category theory. The idea here is that the number of \(k\)-cycles in a random permutation of \(n\) things is a random variable. Then comes a surprise: in the limit as \(n \to \infty\), this random variable approaches a Poisson distribution with mean \(1/k\). And even better, for different choices of \(k\) these random variables become independent in the \(n \to \infty\) limit.
I'm stating these facts roughly now, to not get bogged down. But I'll state them precisely, prove them, and categorify them. That is, I'll state equations involving random variables — but then I'll prove that these equations come from equivalences of groupoids!
So, here's the plan. First I'll state the Cycle Length Lemma, which summarizes a lot of interesting facts about random permutations. Then I'll state and prove a categorified version of the Cycle Length Lemma, which asserts an equivalence of groupoids. Then I'll derive the original version of the lemma from this categorified version by taking the cardinalities of these groupoids. The categorified version contains more information, so it's not just a trick for proving the original lemma.
What do groupoids have to do with random permutations? You'll see, but it's an example of 'principle of indifference', especially in its modern guise, called the 'principle of transformation groups': the idea that outcomes related by a symmetry should have the same probability. This sets up a connection between groupoids and probability theory — and as we'll see, we can "go down" from groupoids to probabilities using the theory of groupoid cardinalities.
In the theory of random permutations, we treat the symmetric group \(S_n\) as a probability measure space where each element has the same measure, namely \(1/n!\). Functions \(f \colon S_n \to \mathbb{R}\) then become random variables, and we can study their expected values:
$$ E(f) = \frac{1}{n!} \sum_{\sigma \in S_n} f(\sigma). $$An important example is the function
$$ C_k \colon S_n \to \mathbb{N} $$that counts, for any permutation \(\sigma \in S_n\), its number of cycles of length \(k\), also called \(k\)-cycles. A well-known but striking fact about random permutations is that whenever \(k \le n\), the expected number of \(k\)-cycles is \(1/k\):
$$ E(C_k) = \frac{1}{k} $$For example, a random permutation of any finite set has, on average, one fixed point!
Another striking fact is that whenever \(j \ne k\) and \(j + k \le n\), so that it's possible for a permutation \(\sigma \in S_n\) to have both a \(j\)-cycle and a \(k\)-cycle, the random variables \(C_j\) and \(C_k\) are uncorrelated in the following sense:
$$ E(C_j C_k) = E(C_j) E(C_k) . $$You might at first think that having lots of \(j\)-cycles for some large \(j\) would tend to inhibit the presence of \(k\)-cycles for some other large value of \(k\), but that's not true unless \(j + k \gt n\), when it suddenly becomes impossible to have both a \(j\)-cycle and a \(k\)-cycle!
These two facts are special cases of the Cycle Length Lemma. To state this lemma in full generality, recall that the number of ordered \(p\)-tuples of distinct elements of an \(n\)-element set is the falling power
$$ x^{\underline{p}} = x(x-1)(x-2) \, \cdots \, (x-p+1). $$It follows that the function
$$ C_k^{\underline{p}} \colon S_n \to \mathbb{N} $$counts, for any permutation in \(S_n\), its ordered \(p\)-tuples of distinct \(k\)-cycles. We can also replace the word 'distinct' here by 'disjoint', without changing the meaning, since distinct cycles must be disjoint.
The two striking facts mentioned above generalize as follows:
1) First, whenever \(p k \le n\), so that it is possible for a permutation in \(S_n\) to have \(p\) distinct \(k\)-cycles, then
$$ E(C_k^{\underline{p}}) = \frac{1}{k^p}. $$If you know about the moments of a Poisson distribution here's a nice equivalent way to state this equation: when \(p k \le n\), the \(p\)th moment of the random variable \(C_k\) equals that of a Poisson distribution with mean \(1/k\).
2) Second, the random variables \(C_k\) are better and better approximated by independent Poisson distributions. To state this precisely we need a bit of notation. Let \(\vec{p}\) denote an \(n\)-tuple \((p_1 , \dots, p_n)\) of natural numbers, and let
$$ |\vec{p}| = p_1 + 2p_2 + \cdots + n p_n. $$If \(|\vec{p}| \le n\), it is possible for a permutation \(\sigma \in S_n\) to have a collection of distinct cycles, with \(p_1\) cycles of length 1, \(p_2\) cycles of length 2, and so on up to \(p_n\) cycles of length \(n\). If \(|\vec{p}| \gt n\), this is impossible. In the former case, where \(|\vec{p}| \le n\), we always have
$$ E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) = \prod_{k=1}^n E( C_k^{\underline{p}_k}) .$$Taken together, 1) and 2) are equivalent to the Cycle Length Lemma, which may be stated in a unified way as follows:
Cycle Length Lemma. Suppose \(p_1 , \dots, p_n \in \mathbb{N}\). Then
$$ E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) = \left\{ \begin{array}{ccc} \displaystyle{ \prod_{k=1}^n \frac{1}{k^{p_k}} } & & \mathrm{if} \; |\vec{p}| \le n \\ \\ 0 & & \mathrm{if} \; |\vec{p}| \gt n \end{array} \right. $$This appears, for example, in Ford's course notes on random permutations and the statistical properties of prime numbers [Lemma 1.1, F]. The most famous special case is when \(|\vec{p}| = n\). Apparently this goes back to Cauchy, but I don't know where he proved it. I believe he would have phrased it in terms of counting permutations, not probabilities.
I won't get into details of precisely the sense in which random variables \(C_k\) approach independent Poisson distributions. For that, see Arratia and Tavaré [AT].
To categorify the Cycle Length Lemma, the key is to treat a permutation as an extra structure that we can put on a set, and then consider the groupoid of \(n\)-element sets equipped with this extra structure:
Definition. Let \(\mathsf{Perm}(n)\) be the groupoid in which
and
We'll need this strange fact below: if \(n \lt 0\) then \(\mathsf{Perm}(n)\) is the empty groupoid (that is, the groupoid with no objects and no morphisms).
More importantly, we'll need a fancier groupoid where a set is equipped with a permutation together with a list of distinct cycles of specified lengths. For any \(n \in \mathbb{N}\) and any \(n\)-tuple of natural numbers \(\vec{p} = (p_1 , \dots, p_n)\), recall that we have defined
$$ |\vec{p}| = p_1 + 2p_2 + \cdots + n p_n. $$Definition. Let \(\mathsf{A}_\vec{p}\) be the groupoid of \(n\)-element sets \(X\) equipped with a permutation \(\sigma \colon X \to X\) that is in turn equipped with a choice of an ordered \(p_1\)-tuple of distinct \(1\)-cycles, an ordered \(p_2\)-tuple of distinct \(2\)-cycles, and so on up to an ordered \(p_n\)-tuple of distinct \(n\)-cycles. A morphism in this groupoid is a bijection that is permutation-preserving and also preserves the ordered tuples of distinct cycles.
Note that if \(|p| \gt n\), no choice of disjoint cycles with the specified property exists, so \(A_\vec{p}\) is the empty groupoid.
Finally, we need a bit of standard notation. For any group \(G\) we write \(\mathsf{B}(G)\) for its delooping: that is, the groupoid that has one object \(\star\) and \(\mathrm{Aut}(\star) = G\).
The Categorified Cycle Length Lemma. For any \(\vec{p} = (p_1 , \dots, p_n) \in \mathbb{N}^n\) we have
$$ \mathsf{A}_{\vec{p}} \simeq \mathsf{Perm}(n - |\vec{p}|) \; \times \; \prod_{k = 1}^n \mathsf{B}(\mathbb{Z}/k)^{p_k} $$Proof. Both sides are empty groupoids when \(n - |\vec{p}| \lt 0\), so assume \(n - |\vec{p}| \ge 0\). A groupoid is equivalent to any full subcategory of that groupoid containing at least one object from each isomorphism class. So, fix an \(n\)-element set \(X\) and a subset \(Y \subseteq X\) with \(n - |\vec{p}|\) elements. Partition \(X - Y\) into subsets \(S_{k\ell}\) where \(S_{k \ell}\) has cardinality \(k\), \(1 \le k \le n\), and \(1 \le \ell \le p_k\). Every object of \(\mathsf{A}_{\vec{p}}\) is isomorphic to the chosen set \(X\) equipped with some permutation \(\sigma \colon X \to X\) that has each subset \(S_{k \ell}\) as a \(k\)-cycle. Thus \(\mathsf{A}_{\vec{p}}\) is equivalent to its full subcategory containing only objects of this form.
An object of this form consists of an arbitrary permutation \(\sigma_Y \colon Y \to Y\) and a cyclic permutation \(\sigma_{k \ell} \colon S_{k \ell} \to S_{k \ell}\) for each \(k,\ell\) as above. Consider a second object of this form, say \(\sigma'_Y \colon Y \to Y\) equipped with cyclic permutations \(\sigma'_{k \ell}\). Then a morphism from the first object to the second consists of two pieces of data. First, a bijection
$$ f \colon Y \to Y $$such that
$$ \sigma'_Y = f \circ \sigma_Y \circ f^{-1}. $$Second, for each \(k,\ell\) as above, bijections
$$ f_{k \ell} \colon S_{k \ell} \to S_{k \ell} $$such that
$$ \sigma'_{k \ell} = f_{k \ell} \circ \sigma_{k \ell} \circ f_{k \ell}^{-1}. $$Since \(Y\) has \(n - |\vec{p}|\) elements, while \(\sigma_{k \ell}\) and \(\sigma'_{k \ell}\) are cyclic permutations of \(k\)-element sets, it follows that \(\mathsf{A}_{\vec{p}}\) is equivalent to
$$ \mathsf{Perm}(n - |\vec{p}|) \; \times \; \prod_{k = 1}^n \mathsf{B}(\mathbb{Z}/k)^{p_k}. \qquad \qquad ▮ $$The case where \(|\vec{p}| = n \) is especially pretty, since then our chosen cycles completely fill up our \(n\)-element set and we have
$$ \mathsf{A}_{\vec{p}} \simeq \prod_{k = 1}^n \mathsf{B}(\mathbb{Z}/k)^{p_k}. $$The cardinality of finite sets has a natural extension to finite groupoids, and this turns out to be the key to extracting results on random permutations from category theory. Let's briefly recall the idea of 'groupoid cardinality' [BD,BHW]. Any finite groupoid \(\mathsf{G}\) is equivalent to a coproduct of finitely many one-object groupoids, which are deloopings of finite groups \(G_1, \dots, G_m\):
$$ \mathsf{G} \simeq \sum_{i = 1}^m \mathsf{B}(G_i), $$and then the cardinality of \(\mathsf{G}\) is defined to be
$$ |\mathsf{G}| = \sum_{i = 1}^m \frac{1}{|G_i|}. $$This concept of groupoid cardinality has various nice properties. For example it's additive:
$$ |\mathsf{G} + \mathsf{H}| = |\mathsf{G}| + |\mathsf{H}| $$and multiplicative:
$$ |\mathsf{G} \times \mathsf{H}| = |\mathsf{G}| \times |\mathsf{H}| $$and invariant under equivalence of groupoids:
$$ \mathsf{G} \simeq \mathsf{H} \implies |\mathsf{G}| = |\mathsf{H}|. $$But none of these three properties require that we define \(|\mathsf{G}|\) as the sum of the reciprocals of the cardinalities \(|G_i|\): any other power of these cardinalities would work just as well. What makes the reciprocal cardinalities special is that if \(G\) is a finite group acting on a set \(S\), we have
$$ |S/\!/G| = |S|/|G| $$where the groupoid \(S /\!/ G\) is the weak quotient or homotopy quotient of \(S\) by \(G\), also called the action groupoid. This is the groupoid with elements of \(S\) as objects and one morphism from \(s\) to \(s'\) for each \(g \in G\) with \(g s = s'\), with composition of morphisms coming from multiplication in \(G\).
The groupoid of \(n\)-element sets equipped with permutation, \(\mathsf{Perm}(n)\), has a nice description in terms of weak quotients:
Lemma. For all \(n \in \mathbb{N}\) we have an equivalence of groupoids
$$ \mathsf{Perm}(n) \simeq S_n /\!/ S_n $$where the group \(S_n\) acts on the underlying set of \(S_n\) by conjugation.
Proof. We use the fact that \(\mathsf{Perm}(n)\) is equivalent to any full subcategory of \(\mathrm{Perm}(n)\) containing at least one object from each isomorphism class. For \(\mathsf{Perm}(n)\) we can get such a subcategory by fixing an \(n\)-element set, say \(X = \{1,\dots, n\}\), and taking only objects of the form \(\sigma \colon X \to X\), i.e. \(\sigma \in S_n\). A morphism from \(\sigma \in S_n\) to \(\sigma' \in S_n\) is then a permutation \(\tau \in S_n\) such that
$$ \sigma' = \tau \sigma \tau^{-1} .$$But this subcategory is precisely \(S_n /\!/ S_n\). ▮
Corollary. For all \(n \in \mathbb{N}\) we have
$$ |\mathrm{Perm}(n)| = 1 $$Proof. We have \(|\mathrm{Perm}(n)| = |S_n /\!/ S_n| = |S_n|/|S_n| = 1\). ▮
It should now be clear why we can prove results on random permutations using the groupoid \(\mathsf{Perm}(n)\): this groupoid is equivalent to \(S_n /\!/ S_n\), a groupoid with one object for each permutation \(\sigma \in S_n\), and with each object contributing \(1/n!\) to the groupoid cardinality.
Now let us use this idea to derive the original Cycle Length Lemma from the categorified version.
Cycle Length Lemma. Suppose \(p_1 , \dots, p_n \in \mathbb{N}\). Then
$$ E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) = \left\{ \begin{array}{ccc} \displaystyle{ \prod_{k=1}^n \frac{1}{k^{p_k}} } & & \mathrm{if} \; |\vec{p}| \le n \\ \\ 0 & & \mathrm{if} \; |\vec{p}| \gt n \end{array} \right. $$Proof. We know that
$$ \mathsf{A}_{\vec{p}} \simeq \mathsf{Perm}(n - |\vec{p}|) \; \times \; \prod_{k = 1}^n \mathsf{B}(\mathbb{Z}/k)^{p_k} $$So, to prove the Cycle Length Lemma it suffices to show three things:
$$ |\mathsf{A}_{\vec{p}}| = E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) $$ $$ \mathsf{Perm}(n - |\vec{p}|) = \left\{ \begin{array}{ccc} 1 & & \mathrm{if} \; |\vec{p}| \le n \\ \\ 0 & & \mathrm{if} \; |\vec{p}| \gt n \end{array} \right. $$and
$$ |\mathsf{B}(\mathbb{Z}/k)| = 1/k $$The last of these is immediate from the definition of groupoid cardinality. The second follows from the Corollary above, together with the fact that \(\mathsf{Perm}(n - |\vec{p}|)\) is the empty groupoid when \(|\vec{p}| \gt n\). Thus we are left needing to show that
$$ |\mathsf{A}_{\vec{p}}| = E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right). $$We prove this by computing the cardinality of a groupoid equivalent to \(\mathsf{A}_{\vec p}\). This groupoid is of the form
$$ Q(\vec{p}) /\!/ S_n $$where \(Q(\vec{p})\) is a set on which \(S_n\) acts. As a result we have
$$ |\mathsf{A}_{\vec{p}}| = |Q(\vec{p}) /\!/ S_n| = |Q(\vec{p})| / n! $$and to finish the proof we will need to show
$$ E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) = |Q(\vec{p})| / n!. $$What is the set \(Q(\vec{p})\), and how does \(S_n\) act on this set? An element of \(Q(\vec{p})\) is a permutation \(\sigma \in S_n\) equipped with an ordered \(p_1\)-tuple of distinct \(1\)-cycles, an ordered \(p_2\)-tuple of distinct \(2\)-cycles, and so on up to an ordered \(p_n\)-tuple of distinct \(n\)-cycles. Any element \(\tau \in S_n\) acts on \(Q(\vec{p})\) in a natural way, by conjugating the permutation \(\sigma \in S_n\) to obtain a new permutation, and mapping the chosen cycles of \(\sigma\) to the corresponding cycles of this new permutation \(\tau \sigma \tau^{-1}\).
Recalling the definition of the groupoid \(\mathsf{A}_{\vec{p}}\), it is clear that any element of \(Q(\vec{p})\) gives an object of \(\mathsf{A}_{\vec{p}}\), and any object is isomorphic to one of this form. Furthermore any permutation \(\tau \in S_n\) gives a morphism between such objects, all morphisms between such objects are of this form, and composition of these morphisms is just multiplication in \(S_n\). It follows that
$$ \mathsf{A}_{\vec{p}} \simeq Q(\vec{p}) /\!/ S_n. $$To finish the proof, note that
$$ E\left( \prod_{k=1}^n C_k^{\underline{p}_k} \right) $$is \(1/n!\) times the number of ways of choosing a permutation \(\sigma \in S_n\) and equipping it with an ordered \(p_1\)-tuple of distinct \(1\)-cycles, an ordered \(p_2\)-tuple of distinct \(2\)-cycles, and so on. This is the same as \( |Q(\vec{p})| / n!\). ▮
[AT] Richard Arratia and Simon Tavaré, The cycle structure of random permutations, The Annals of Probability (1992), 1567–1591.
[BD] John C. Baez and James Dolan, From finite sets to Feynman diagrams, in Mathematics Unlimited—2001 and Beyond, vol. 1, eds. Björn Engquist and Wilfried Schmid, Springer, Berlin, 2001, pp. 29–50.
[BHW] John C. Baez, Alexander E. Hoffnung and Christopher D. Walker, Higher-dimensional algebra VII: groupoidification, Theory and Applications of Categories 24 (2010), 489–553.
[F] Kevin Ford, Anatomy of Integers and Random Permutations—Course Lecture Notes.
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|