## December 1, 2019

### Random Permutations (Part 6)

#### Posted by John Baez

Now I’ll tackle a really fundamental question about random permutations — one whose answer will quickly deliver the solutions to many others!

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

The answer is beautiful: it’s $1/k$. More precisely, this holds whenever the question is reasonable, meaning $1 \le k \le n$.

Note that this answer passes a simple sanity check. If on average there’s $1$ cycle of length $1$, $1/2$ cycles of length $2$, and so on, the average number of elements in our $n$-element set must be

$1 \cdot 1 + \frac{1}{2} \cdot 2 + \cdots + \frac{1}{n} \cdot n = n$

Whew!

Before we show the expected number of cycles of length $k$ in a random permutation of an $n$-element set is $1/k$, let’s see how knowing this lets us answer some other questions we’ve met.

• What’s the expected number of fixed points of a random permutation?

Since a fixed point is a cycle of length $1$, the answer is $1$. We’ve already seen this in Part 1. There we got it the hard way, by computing the probability that a permutation has $k$ fixed points. But I hinted that there’s a much easier way. Here it is: since the probability that a random permutation of an $n$-element set fixes any given point is $1/n$, the expected number of fixed points is $n \cdot \frac{1}{n} = 1$.

• What’s the probability that a random permutation of an $n$-element set has a cycle of length $k$, assuming $k \gt n/2$?

Since $k$ is more than $n/2$, there can be at most one cycle of length $k$. Thus, the probability that such a cycle exists equals the expected number of such cycles! So, the probability must be $1/k$. We already saw this in Part 4. Now we’re seeing a nice way to generalize this fact to $k \le n/2$, not by asking whether a cycle of length $k$ exists, but by asking the expected number of such cycles.

• What is the expected number of cycles in a random permutation of an $n$-element set?

This was Puzzle 5 in Part 3. Since the expected number of cycles of length $k$ is $1/k$, we can sum over $k = 1, \dots, n$ and get the answer:

$\frac{1}{1} + \cdots + \frac{1}{n}$

Asymptotically this is $\ln n$. Or, even better, it’s $\ln n + \gamma$ plus a correction that goes to zero as $n \to \infty$.

• If we choose an element of an $n$-element set and random permutation of this set, what is the probability that the element lies in a cycle of length $k$?

This was Puzzle 8 of Part 3. Now I’m telling you that the expected number of cycles of length $k$ is $1/k$. Since each contains $k$ elements, the expected number of elements of our set lying on cycles of length $k$ is $k \cdot \frac{1}{k} = 1$. So, the probability that any element lies on a cycle of length $k$ is $1/n$. It’s cool how this is independent of $k$.

Okay, I hope you’re convinced by now that computing the expected number of cycles of length $k$ in a random permutation of an $n$-element set is the key to understanding many things. Let’s do it!

Flajolet and Sedgewick do this using bivariate generating functions in Example III.9 of their book Analytic Combinatorics. I explained the basic method last time so now I’ll just use it.

We start by making up a functor

$H_k \colon S \times \mathbb{N} \to FinSet$

that assigns to the pair $(n,i)$ the set $H_k(n,i)$ of all permutations of $n$ having exactly $i$ cycles of length $k$. Note that $n$ here is being treated as a finite set, while $i$ and $k$ are just numbers.

The generating function of $H_k$ is defined by

$\displaystyle{ |H_k|(z,u) = \sum_{n \ge 0} \sum_{i \ge 0} |H_k(n,i)| \, \frac{z^n}{n!} u^i }$

Suppose we could compute this. How could we use this to answer our puzzle?

We want the expected number of cycles of length $k$ in a permutation of an $n$-element set. Since the probability that a random permutation has $i$ cycles of length $k$ is

$\frac{|H_k(n,i)|}{n!}$

this expected number is

$\sum_{i \ge 0} i \frac{|H_k(n,i)|}{n!}$

So this is the sum we need to compute.

But notice,

$\begin{array}{ccl} \displaystyle{ \left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1} } &=& \displaystyle{ \left. \frac{\partial}{\partial u} \sum_{n \ge 0} \sum_{i \ge 0} |H_k(n,i)| \, \frac{z^n}{n!} u^i \; \right|_{u=1} } \\ \\ &=& \displaystyle{ \sum_{n \ge 0} \sum_{i \ge 0} i |H_k(n,i)| \, \frac{z^n}{n!} } \\ \\ \end{array}$

So, the expected number we want is the coefficient of $z^n$ in the power series for

$\left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1}$

Thus, to answer our puzzle, we should figure out $|H_k|(z,u)$, differentiate it with respect to $u$, set $u = 1$, and read off the coefficient of $z^n$.

For this, we’ll need a formula for $H_k$:

$H_k \cong Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k)$

Let’s see what this means! As soon as you understand what it means, you’ll know it’s true. That happens a lot in category theory.

Here $Cyc_k \colon S \to FinSet$ is the species ‘being a cyclically ordered $k$-element set’. We’ve already met the species

$Cyc \cong \sum_{i \ge 0} Cyc_i$

which is ‘being a cyclically ordered finite set’, and now we’ll define a species

$Cyc_{\ne k} \cong \sum_{i \ne k} Cyc_i$

which is ‘being a cyclically ordered finite set of cardinality $\ne k$’. All these species can be seen as functors from $S \times \mathbb{N}$ to $FinSet$ that don’t involve the second variable.

On the other hand, we have a functor

$U \colon \mathbb{N} \to FinSet$

called ‘being the number 1’. This is defined by setting $U(1) = 1$ and $U(i) = \emptyset$ for all $i \ne 1$. This can be seen as a functor from $S \times \mathbb{N}$ to $FinSet$ that doesn’t involve the first variable.

It’s a bit hard for me to describe the functor

$Cyc_{\ne k} + U \cdot Cyc_k$

in plain English, mainly because I haven’t developed a vocabulary for functors $S \times \mathbb{N} \to FinSet$ the way I have for species! A species describes a type of structure you can put on a finite set; one of these functors describes a type of structure you can put on a finite set and a natural number. This one is ‘either your finite set is cyclically ordered and not of cardinality $k$ and your number is $0$, or it’s cyclically ordered and of cardinality $k$ and your number is $1$’.

As a consequence

$Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k)$

describes the following sort of structure on a finite set and a natural number. This structure is a way to chop the finite set into cyclically ordered pieces and simultaneously write the number as sum of $0$’s and $1$’s, but using a $1$ for each piece of cardinality $k$, and a $0$ for every other piece. This is why we get

$Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k) \cong H_k$

where $H_k(n,i)$ is the set of all permutations of the set $n$ having exactly $i$ cycles of length $k$.

That’s my best attempt at a purely verbal explanation of this isomorphism. Now let’s exploit it: it gives an equation between generating functions

$|H_k| = exp \circ (|Cyc_{\ne k}| + |U| \cdot |Cyc_k|)$

which will let us compute $|H_k|$.

To proceed, notice that

$|Cyc_k| = \frac{(k-1)!}{k!} z^k = \frac{z^k}{k}$

since there are $(k-1)!$ ways to cyclically order a $k$-element set. Similarly,

$\begin{array}{ccl} |Cyc_{\ne k}| &=& \displaystyle{ \sum_{i \ne k} \frac{z^i}{i} } \\ \\ &=& \displaystyle{ \ln\left(\frac{1}{1-z}\right) - \frac{z^k}{k} } \end{array}$

The whole point of $U$ is that

$|U| = u$

So, we get

$| Cyc_{\ne k} + U \cdot Cyc_k | = \ln\left(\frac{1}{1-z}\right) + (u-1) \frac{z^k}{k}$

In other words, this generating function is like that of $Cyc$, the species of cyclic orderings:

$|Cyc| = \ln \left( \frac{1}{1-z} \right)$

except that we’ve yanked out the $z^k/k$ term and stuck it back in multiplied by $u$. That’s why it pays special attention to cycles of length $k$.

From this we get

$\begin{array}{ccl} |H_k| &=& \exp \circ (|Cyc_{\ne k}| + |U| \cdot |Cyc_k|) \\ \\ &=& \displaystyle{ \exp \left( \ln \left( \frac{1}{1-z} \right) + (u-1) \frac{z^k}{k} \right) } \\ \\ &=& \displaystyle{ \frac{e^{(u-1)z^k/k}}{1-z} } \end{array}$

Now to answer our puzzle we differentiate this with respect to $u$, set $u = 1$, and read off the coefficient of $z^n$. That’ll be the expected number of cycles of length $k$ in a random permutation of an $n$-element set!

Here we go:

$\begin{array}{ccl} \displaystyle{ \left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1} } &=& \displaystyle{ \left. \frac{\partial}{\partial u} \frac{e^{(u-1)z^k/k}}{1-z} \right|_{u=1} } \\ \\ &=& \displaystyle{ \frac{z^k/k}{1-z} } \\ \\ &=& \displaystyle{ \frac{z^k}{k} + \frac{z^{k+1}}{k} + \frac{z^{k+1}}{k} + \cdots } \end{array}$

As long as $n \ge k$, the coefficient of $z^n$ in this power series is $1/k$. But of course, we need $k \ge 1$ for this whole calculation to make sense.

So whenever $1 \le k \le n$, the expected number of cycles of length $k$ in a random permutation of an $n$-element set is $1/k$. It’s a little jewel of mathematics.

Posted at December 1, 2019 8:36 PM UTC

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

### Re: Random Permutations (Part 6)

What is the expected number of cycles of length $k$ in a random permutation of an $n$-element set?

The answer is beautiful: it’s $1/k$ [for $1 \leq k \leq n$].

That is beautiful!

Another way to say it is this: in a random permutation of an $n$-element set, the expected number of $k$-periodic points is $1$.

Do you know of any direct way of seeing that the expected number of $k$-periodic points in a permutation of $n$ elements should be independent of $n$, for $n \geq k$?

E.g. why should the expected number of 3-periodic points in a permutation of 10 elements be the same as in a permutation of 100 elements?

For some reason this is reminding me of Barbier’s beautiful solution of the Buffon needle problem. But if I could put my finger on why, I could answer my own question!

Posted by: Tom Leinster on December 4, 2019 3:16 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Another interesting aspect of this reformulation is that the expected number of $k$-periodic points in a random permutation of $n$ elements is independent of $k$, for $k \le n$.

This perspective comes more to the fore when observing that yet another equivalent formulation is that $\mathbb{P}[x is k\text{-periodic}] = \frac{1}{n}$ for each fixed $x$ in the $n$-element set and each $1 \le k \le n$.

And this leads to the question: Is there a direct way of seeing that the probability that a fixed element is $k$-periodic should be independent of $k$?

Posted by: Mark Meckes on December 4, 2019 4:23 PM | Permalink | Reply to this

### Sridhar Ramesh

Sure, it’s simple, isn’t it?

Consider a fixed point p in an n-element set and start randomly choosing further values in the chain $p, f(p), f(f(p))$, etc, till eventually this returns to p. What’s the probability it takes k steps to do so?

Let $T_k$ mean the event that the first $k$ many values in the sequence $p, f(p), f(f(p)), \ldots$, are all distinct.

Given that $T_k$ holds, what’s the probability of $T_{k + 1}$?

Well, $f^k(p)$ cannot match $f^j(p)$ for any prior positive $j$, since $f$ is a permutation. Either $f^k(p) = p$ and $T_{k + 1}$ fails to hold, or $f^k(p)$ is one of the other equally likely $n - k$ values left available to choose and $T_{k + 1}$ holds.

So $P(T_{k + 1} | T_k) = \frac{n - k}{n - k + 1}$. That is, $P(T_2 | T_1) = \frac{n - 1}{n}$, $P(T_3 | T_2) = \frac{n - 2}{n - 1}$, $P(T_4 | T_3) = \frac{n - 3}{n - 2}$, etc.

Taking the telescoping product of these, and using $T_1 = 1$, we find the sequence $P(T_1), P(T_2), P(T_3), \ldots$ is $\frac{n}{n}, \frac{n - 1}{n}, \frac{n - 2}{n}, \ldots$ respectively. And thus, the probability that $T_k$ holds but $T_{k + 1}$ does not hold is $1/n$, for each $k \in [1, n]$.

But for $T_k$ to hold while $T_{k + 1}$ does not hold is precisely what it means for our original point to be in a cycle of length $k$. And so we are done.

Posted by: Sridhar Ramesh on December 6, 2019 6:36 PM | Permalink | Reply to this

### Sridhar

Er, when I start off saying “fixed point p”, I obviously don’t mean a fixed point of the function f; just a particular given point p. But in an abundance of caution, I’ll note now that was not the most apt language for this context. Oh well, no post editing.

Posted by: Sridhar Ramesh on December 6, 2019 6:38 PM | Permalink | Reply to this

### Random Permutations (Part 6)

Oh, great, and I’ve been making my name the subject too, haha. What a mess I’ve made.

Posted by: Sridhar Ramesh on December 6, 2019 6:40 PM | Permalink | Reply to this

### Random Permutations (Part 6)

Even simpler:

Pick a particular point $p$ in an $n$-element set.

How many permutations of this $n$-element set have $p$ in a cycle of length precisely $k$?

Well, we have to choose the other $k - 1$ elements in the cycle, and put an ordering on them. Then we have to permute the remaining $n - k$ elements. So there are $\binom{n - 1}{k - 1} \times (k - 1)! \times (n - k)!$ ways of doing so. This is equal to $(n - 1)!$.

And dividing by the $n!$ many permutations of an $n$-element set overall, we get the probability $1/n$, as desired.

Posted by: Sridhar Ramesh on December 6, 2019 6:51 PM | Permalink | Reply to this

### Random Permutations (Part 6)

With analogous directness:

The mean number of points in cycles of length $k$ over all permutations of an $n$-element set is $1$. Why is this?

Well, a point in a cycle of length $k$ is specified by first choosing $k$ many elements to be in the cycle (in one of $\binom{n}{k}$ many ways), then putting an ordering on these elements (in one of $k!$ many ways), with the first point in the ordering taken as our point of interest. Fleshing out the full permutation now comprises simply permuting the remaining points among themselves (in one of $(n - k)!$ many ways).

So there are $\binom{n}{k} k! (n - k)!$ many points in cycles of length $k$ overall, among all permutations of $n$ elements. Finally, we divide by the number of permutations of $n$ elements (which is $n!$) to compute the mean value, rather than the total value.

This gives us $\binom{n}{k} k! (n - k)! / n!$. And this is clearly $1$.

Posted by: Sridhar Ramesh on December 6, 2019 7:00 PM | Permalink | Reply to this

### Random Permutations (Part 6)

I wish I could now delete the early posts in the clutter of my thinking and leave only the perfectly polished last one, but so it goes. Anyway, I’ll stop blathering now. :)

Posted by: Sridhar Ramesh on December 6, 2019 7:05 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Tom wrote:

Do you know of any direct way of seeing that the expected number of $k$-periodic points in a permutation of $n$ elements should be independent of $n$, for $n \geq k$?

No, I don’t! The only way I know to prove this is the argument I just gave—or a slight variation I want to describe.

Mark wrote:

And this leads to the question: Is there a direct way of seeing that the probability that a fixed element is $k$-periodic should be independent of $k$?

The only way I know how to prove this is the argument I just gave. I’d really like a more direct proof!

If anyone knows other proofs of these facts — there must be some — please let me know about them!

Posted by: John Baez on December 6, 2019 7:52 AM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Terry Tao says in this blog post that he has found bijective proofs of this and related identities about cycles of random permutations. Bijective doesn’t necessarily mean more direct, but probably that’s exactly what you’d like here.

Terry says he “thought some readers might be interested in trying to find these proofs themselves as an exercise”, so he just listed the identities for reference. It sounds like a fun exercise, certainly more fun than all the grading I need to be doing now…

Posted by: Mark Meckes on December 6, 2019 3:04 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Thanks! By the way, almost all the proofs in this series of blog posts are bijective proofs. That’s what species are for.

Posted by: John Baez on December 6, 2019 6:30 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

By the way, almost all the proofs in this series of blog posts are bijective proofs. That’s what species are for.

Right, it’s really cool how all this shows that generating function arguments can be viewed as decategorified bijective arguments. I assumed, though, that Terry meant that he had found independent bijective proofs that were not directly inspired by the generating functions proofs.

Anyway, there are lots of nice solutions to the exercise around here now.

Posted by: Mark Meckes on December 6, 2019 6:50 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Mark wrote:

And this leads to the question: Is there a direct way of seeing that the probability that a fixed element is $k$-periodic should be independent of $k$?

I posed this on Twitter and quickly got this reply from a mathematician named Tom at Cambridge University:

Use induction on $k$. The prob that it’s on a cycle of length $k+1$ given that it’s not on a cycle of length at most $k$ is $1/(n-k)$, since next element in the walk has equal chance going anywhere not already visited, which removes $k$ elements. Then use formula for conditional probability, and induction to show that prob not on a cycle of length at most $k$ is $1-k/n$.

I believe this strategy is the one explained in more detail by Sridhar here on the $n$-Café.

On the other hand, Zeno Rogue proposed an even quicker proof:

Encode permutations as follows: list all cycles, sorted by the smallest number on them, each cycle ending with the smallest number. E.g. [3541][762] is encoded as 3541762. This is a bijection $S_n \to S_n$. 1 is in cycle of length $k$ iff $code[k]=1$, thus clearly $prob=1/n$.

(If the notation is not clear — the example permutation maps $3 \mapsto 5, 4 \mapsto 1, 1 \mapsto 3, 7 \mapsto 6, 6 \mapsto 2, 2 \mapsto 7$.)

Akiva Weinberger wrote:

So for example, 291384756 corresponds to [291][3][84][75][6].

You find the lowest number, bracket off everything to the left (including itself), find the lowest number of what’s left, etc.

Posted by: John Baez on December 6, 2019 6:43 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Still more beautiful: Suppose $C_k$ denotes the number of cycles of length $k$ in a random permutation of an $n$-element set (suppressing the dependence on $n$). Then as $n \to \infty$, the distribution of the random variable $C_k$ approaches a Poisson distribution with mean $1/k$.

And even better: For a fixed $b$, in the $n \to \infty$ limit $C_1, \ldots, C_b$ become independent Poisson random variables. In a reasonable quantitative version, this even extends to $b = o(n)$. (Reference.)

None of this address Tom’s question, though.

Posted by: Mark Meckes on December 4, 2019 4:03 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

That $1/k$ is a lovely result — it’s the sort of discovery that underscores the value of the tools used to find it.

Posted by: Blake Stacey on December 4, 2019 5:51 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Here’s the proof “from the Book”, offered by Zeno Rogue on Twitter:

Posted by: John Baez on December 6, 2019 10:58 PM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

Am I the only one who found it difficult at first to see how inverting that bijection works?

Posted by: Blake Stacey on December 7, 2019 4:16 AM | Permalink | Reply to this

### Re: Random Permutations (Part 6)

No, people are talking about it on Twitter. (I’m raising the tone of the place.)

Posted by: John Baez on December 7, 2019 5:46 AM | Permalink | Reply to this

Post a New Comment