|
|
|
|
I'm trying to understand what a random permutation of a large set is typically like. While I've been solving some puzzles that shed a bit of light on this question, I now realize there are some other puzzles that would help more.
When I started, I had a wrong mental image of a random permutation of a large finite set. I foolishly imagined it would be made of many small orbits. But that's far from true!
It's easy to see why if you think about it. Given a random permutation \(f\colon X \to X\) of a large \(n\)-element set, it's very unlikely for \(x \in X\) to be mapped to itself by \(f\), or even by \(f^k\) for some small \(k\). So we should instead imagine our random permutation as consisting mainly of quite large orbits!
Here are the facts I've proved or at least stated so far:
So there's about a 37% chance of having no fixed points, a 37% chance of having one, an 18% chance of having two, a 6% chance of having three, and it drops off rapidly from there. I showed this in Part 1.
In the \(n \to \infty\) limit this follows from the previous remark. But in fact there's an easy way to show it's true for any \(n \gt 0\). Do you see how?
So, there's a 37% chance that the shortest cycle has length \(\gt 1\), a 22% chance that it has length \(\gt 2\), a 16% chance that it has length \(\gt 3\), a 12% chance that it has length \(\gt 4\), and it drops off slowly from there. I proved this in Part 2.
This is potentially misleading to the unwary. It says a random permutation of a huge set is quite likely to have at least one short cycle. But you shouldn't assume it has lots of short cycles. Indeed, my second remark above says that it has just one cycle of length 1, on average.
I discussed in this Part 0, which is the name for this number \(\lambda\). Dickman proved more: he computed the probability that the longest cycle in a random permutation of an \(n\)-element set has length \(\le c n\), in the \(n \to \infty\) limit. He showed it drops off very rapidly as \(c\) decreases. For example, the probability that the longest permutation has length \(\le n/10\) is less than \(10^{-10}\), for large \(n\).
This is makes it very interesting to probe the nature of large cycles. But the details of these, and many other aspects of random permutations, remain mysterious to me!
So, let me resume my puzzle series. These are puzzles for myself, or anyone who wants to help:
Puzzle 5. What is the expected number of cycles in a random permutation of an \(n\)-element set? What about the mode, or median?
Apparently the expected number of cycles is
\[ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \]As \(n \to \infty\) this is asymptotically \(\ln n\). That's very small compared to the size of our set! This goes along with the fact that typically there are some rather large cycles. I'll prove this in Part 5.
I don't know the mode or median.
Puzzle 6. What is the expected length of a cycle in a random permutation of an \(n\)-element set, asymptotically as \(n \to \infty\)? What about the mode, or median?
I haven't worked this out, but I want the expected value to be asymptotically \(n/\ln n\).
Puzzle 7. What is the expected number of cycles of length \(k\) in a random permutation of an \(n\)-element set?
The answer is apparently \(1/k\) when \(1 \le k \le n\). A proof is here, but I should explain it. Note that when \(k = 1\) we're back to my claim that the expected number of fixed points is \(1\).
Here are some more puzzles designed to shed light on the large cycles in a random permutation:
Puzzle 8. If we choose an element of an \(n\)-element set, what is the probability that it lies in a cycle of length \(k\)?
The answer is very simple: \(1/n\), for \(1 \le k \le n\). In other words, it's equally likely to be on a cycle of any allowed size! A proof is here, and again I want to explain it.
Puzzle 9. If we choose one element of an \(n\)-element set, what is the expected length of the cycle it lies on?
Thanks to Puzzle 8, the answer is \((n+1)/2\): the average of the natural numbers from \(1\) to \(n\).
Note that there can be at most one cycle of length \(\gt n/2\). I'll call such a cycle a giant cycle, because it reminds me of the giant connected component of a random graph.
Puzzle 10. How probable is the existence of a giant cycle?
When \(n\) is even, the probability is
\[ \frac{1}{n+1} + \cdots + \frac{1}{2n} \]This is connected to the hundred prisoners problem. Something similar is true when \(n\) is odd. As \(n \to \infty\) the probability approaches \(\ln 2\), or about 69.3%.
Okay, now I need to process all this information, write up proofs for some of these things, but most importantly synthesize all this information to get a better mental picture of a random permutation.
The way I see it now, when you have a random permutation of a large set, there's a very good chance a substantial fraction of the elements lie on the largest cycle. If this happens, what about the rest? Is the permutation restricted to the rest of the set random in the same way — all elements of the permutation group equally likely? I think so.
If so, we can recursively 'chip away' at a random permutation, repeatedly removing the largest cycle, getting a kind of fractal structure where each time we do this, the random permutation of the remaining elements is governed by all the same rules I've listed here!
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|