|
|
|
|
In all these problems we choose permutations randomly from \(S_n\), with each permutation having probability \(1/n!\) of being chosen.
I'll start with one that's easy, given the stuff I've already explained in class.
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.
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|