November 24, 2019

Random Permutations (Part 1)

Posted by John Baez

I’m going to solve some problems on random permutations in my combinatorics class, to illustrate some of the ideas on species and generating functions, but also to bring in some ideas from complex analysis.

In all these problems we choose permutations randomly from $S_n$, with each permutation having probability $1/n!$ of being chosen.

Puzzle 1. What is the probability that a randomly chosen permutation of an $n$-element set has exactly $k$ fixed points? What does this probability converge to as $n \to \infty$?

In homework the students already computed the probability that a randomly chosen permutation of an $n$-element set has no fixed points. A permutation with no fixed points is called a derangement, and the number of derangements of an $n$-element set is called the subfactorial $!\!n$.

Using the inclusion-exclusion principle, the number of derangements of $\{1,\dots, n\}$ is the number of permutations of this set, minus the number of permutations that fix the point $1$, minus the number that fix the point $2$,… minus the number that fix the point $n$, plus the number that fix the points $1$ and $2$, plus the number that fix the points $1$ and $3$,… minus the number that fix the points $1, 2$ and $3$,… and so on.

In short:

$!n = n! \; -\; \binom{n}{1} (n-1)! + \binom{n}{2} (n-2)! - \cdots + (-1)^n \binom{n}{n} (n-n)!$

We can simplify this to

$!\!n = n! \, \left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} \right)$

Thus, the probability that a permutation of an $n$-element set has no fixed points is

$\frac{!\!n}{n!} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}$

and this approaches $1/e$ as $n \to \infty$. So cool.

Now, what about $k$ fixed points? To choose a permutation of an $n$-element set with $k$ fixed points, we need to choose $k$ points and then choose a derangement of the remaining $(n-k)$-element set. There are

$\binom{n}{k} \, !(n-k)$

ways to do this. Thus, the probability that a permutation of an $n$-element set has $k$ fixed points is

$\binom{n}{k} \; \frac{!\!(n-k)}{n!}$

which can be written more charmingly as

$\frac{1}{k!} \; \frac{!\!(n-k)}{(n-k)!}$

We have seen that as $n \to \infty$ we have

$\frac{!\!(n-k)}{(n-k)!} \to \frac{1}{e}$

Thus, as $n \to \infty$, the probability that a permutation of an $n$-element set has $k$ fixed points approaches

$\frac{1}{e \, k!}$

Note that these probabilities sum to $1$, as they must.

Puzzle 2. In the $n \to \infty$ limit, what is the expected number of fixed points of a permutation of an $n$-element set?

You might naively think it would be infinite, but remember as we increase the size of our set we decrease the probability that any point gets mapped to itself.

We know that in the $n \to \infty$ limit the probability of there being $k$ fixed points is

$\frac{1}{e \, k!}$

so in this limit, the expected number of fixed points is

$\sum_{k \ge 0} k \frac{1}{k! e} = \frac{1}{e} \sum_{k \ge 1} \frac{1}{(k-1)!} = 1$

Exactly one!

You might also wonder what’s the expected number of fixed points for an arbitrary finite $n$, but I’ll leave that to you.

Posted at November 24, 2019 1:39 AM UTC

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

Re: Random Permutations (Part 1)

Is it clear why the limit as $n \to \infty$ of the expected number of fixed points of a permutation on $n$ elements is the same as $\sum_{k = 0}^\infty P_k k$, where $P_k$ is the limit as $n \to \infty$ of the probability of a permutation on $n$ elements having exactly $k$ fixed points? This seems like the sort of interchange-of-limits argument with which one must take some care.

Posted by: L Spice on November 25, 2019 3:46 PM | Permalink | Reply to this

Re: Random Permutations (Part 1)

Good point - it’s true one should take care with this. I’m pretty sure the dominated convergence theorem can handle it.

Posted by: John Baez on November 25, 2019 6:23 PM | Permalink | Reply to this

Re: Random Permutations (Part 1)

The distribution of the number of fixed points for a random permutation of size $n$ has the same first $n$ moments as the Poisson distribution with $\lambda = 1$. Here someone on MathOverflow pointed me to a paper on this by Diaconis, Fulman and Guralnick.

Posted by: Scott McKuen on November 25, 2019 5:51 PM | Permalink | Reply to this

Re: Random Permutations (Part 1)

Cool!

Posted by: John Baez on November 26, 2019 12:37 AM | Permalink | Reply to this

Post a New Comment