|
|
|
|
Last time I listed a bunch of facts designed to improve our mental picture of a typical randomly chosen permutation. Many of these facts are fun to prove using generating functions. But one has a more elementary proof.
Namely: a random permutation of a large finite set has an almost 70% chance of having a single cycle that contains at least half the elements!
This really solidifies my image of a typical permutation of a large finite set. It consists of one big cycle involving most of the elements... and the rest, which is a typical permutation of the remaining smaller set.
Suppose \(f \colon X \to X\) is a permutation of an \(n\)-element set. Let's say a cycle of \(f\) is a giant cycle if it has length \(\gt n/2\). A permutation can contain at most one giant cycle — and as we shall see, this makes this puzzle easy:
Puzzle 10. What is the probability that a randomly chosen permutation of an \(n\)-element set has a giant cycle?
We'll actually solve a more detailed problem. Suppose \(k \gt n/2\). What is the probability that our permutation has a cycle of length \(k\)?
To solve this, we can just count permutations with a cycle of length \(k\) and divide by \(n!\). There is no problem with double counting, since each permutation has at most one giant cycle.
Take an \(n\)-element set \(X\). Choosing a permutation of \(X\) with a cycle of length \(k\) is the same as choosing a \(k\)-element subset \(S \subseteq X\), a cyclic ordering on \(S\), and an arbitrary permutation of \(X - S\).
There are \(\binom{n}{k}\) choices of \(S\), \((k-1)!\) cyclic orderings on \(S\), and \((n-k)!\) permutations of \(X - S\). Multiplying these, we get
\[ \binom{n}{k} (k-1)! (n-k)! = \frac{n! (k-1)! (n-k)!}{k! (n-k)!} = \frac{n!}{k} \]So that's the number of permutations of an \(n\)-element set with a cycle of length \(k\), assuming \(k \gt n/2\).
Dividing by \(n!\), we get
\[ \frac{1}{k} \]So that's the probability that a random permutation of an \(n\)-element set has a cycle of length \(k\), assuming \(k \gt n/2\).
Now we can answer the puzzle! The probability that a random permutation of an \(n\)-element set has a giant cycle is just the sum of \(1/k\) over all \(k\) with \(n/2 \lt k \le n\):
\[ \frac{1}{\lfloor n/2 \rfloor + 1} + \cdots + \frac{1}{n-1} + \frac{1}{n} \]Again there's no double-counting problem, since these cases are exclusive.
As \(n \to \infty\) this sum approaches
\[ \ln n - \ln (n/2) = \ln 2 \approx 0.693 \]So, a random permutation of a huge set has about a 69.3% chance of containing a giant cycle.
We can have a bit more fun with this: in the limit as \(n \to \infty\), there's a 50% probability that a random permutation of an \(n\)-element set will have a cycle of length at least \(e^{-1/2}n\). Since
\[e^{-1/2} \approx 0.6065 \]we know the median length of the largest cycle in a random permutation of a huge set! It's about 60.6% the size of the set itself.
This is a nice counterpart to a harder result we saw before: the mean length of the longest cycle is about 62.4% times the size of the set. Sometimes the mean and median are vastly different, but not here.
In all these calculations it was crucial that we worked with giant cycles. With more work perhaps we could handle subgiant cycles: that is, those containing more than 1/3 of the elements of our set. A permutation can have at most two subgiant cycles, so the double-counting problems we dodged above might still be manageable. But in general, computing the probability that a random permutation has a certain number of cycles of lengths in certain ranges will call for better techniques.
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|