Random Permutations (Part 0)

November 23, 2019

Random Permutations (Part 0)

John Baez

I'm falling in love with random permutations. There's something both simple and fairly deep about them. I like to visualize a random permutation as a "gas of cycles", governed by the laws of statistical mechanics. I haven't gotten very with this analogy yet. But I'm learning a lot of fun stuff.

Here's one of the many cute facts about random permutations — not every easy to prove, but cute.

Let \(a_n\) be the average length of the longest cycle in a permutation, averaged over all permutations of an \(n\)-element set. Then \(a_n\) is asymptotically equal to \(\lambda n\) where

\[ \lambda \approx 0.6243299885 \dots \]

is called the Golomb–Dickman constant. There's a cool formula for this constant: \[ \lambda = \int_0^1 e^{\mathrm{Li}(x)} dx \; \; \textrm{where} \; \; \mathrm{Li}(x) = \int_0^x \frac{dt}{\ln t} \] But nobody has been able to prove that it's irrational!

The Golomb–Dickman constant also shows up in number theory... in a very similar way! If you randomly choose a huge \(n\)-digit integer, the average number of digits of its largest prime factor is asymptotic to \(\lambda n\).

So, there's a connection between prime factorizations and random permutations! And this fact is both simpler and more interesting to me than the Golomb–Dickman constant. You can read more about this here:

The Golomb–Dickman constant is a kind of relative of Euler's constant, though there's no known formula expressing one in terms of the other.

Here's another appearance of this constant. Say you randomly choose a function from a huge \(n\)-element set to itself. Then the average length of its longest periodic orbit is asymptotic to

\[ \lambda \; \sqrt{\frac{\pi n}{2}} \]

Next time I'll start explaining proofs of some other facts about random permutations — facts that are easier to prove!

You can also read comments on the n-Category Café, and make your own comments or ask questions there!

© 2019 John Baez