Cycle type of random permutations: a toolkit

Cycle type of random permutations: a toolkit, Discrete Analysis 2022:9, 36 pp.

What does a random permutation look like? This general question has led to a great deal of research, and this article provides a convenient single reference for many results, some new, others well known but with more unified proofs. Throughout the paper, the author is motivated by an analogy between how the cycle type of a random permutation is distributed, and how the sizes of prime factors of a random integer (between \(n\) and \(2n\) for large \(n\), say) is distributed. Although the methods do not carry over from one domain to the other, the number-theoretic results turn out to be a surprisingly good guide to what will be true in the case of permutations.

Some of the questions tackled are the following. Given a positive integer \(j\), how is the number of cycles of length \(j\) distributed? Given a set \(I\), how is the number of cycles with length in \(I\) distributed? If \(I_1,\dots,I_k\) are disjoint sets, then what does the joint distribution of the numbers of cycles with lengths in \(I_j\) look like? And what is the effect of conditioning on the total number of cycles.

Let \(C_j(\sigma)\) be the number of cycles of \(\sigma\) of length \(j\). For small \(j\) heuristic arguments lead quickly to the conclusion that \(C_j(\sigma)\) should be approximately Poisson with mean \(1/j\). (To see that this should be the mean, note that the probability that 1 belongs to a \(j\)-cycle of \(\sigma\) is roughly the probability that \(\sigma^j(1)=1\), which is roughly \(1/n\). So the expected number of members of \(j\)-cycles is roughly 1, and therefore the expected number of \(j\)-cycles is roughly \(1/j\).) It also leads to the conclusion that if \(j_1,\dots,j_k\) are small distinct integers, then \(C_{j_1}(\sigma),\dots,C_{j_k}(\sigma)\) should be approximately independent. From this it follows that for small sets \(I\) of small numbers, \(C_I(\sigma)\), the number of cycles with lengths in \(I\), ought to be approximately Poisson with mean \(\sum_{j\in I}1/j\). These heuristics are referred to as the Poisson model, and much of the paper is devoted to an analysis of when the Poisson model gives good results and when it needs refining, as it does when long cycles are involved.

Many of the results that are scattered through the literature are proved using generating functions. By contrast, the methods here are mainly direct probabilistic and combinatorial ones, which give uniform and explicit results. The outcome represents the state of the art for elementary methods and provides an excellent benchmark that any more sophisticated method should be expected to beat. The paper will be useful both for bringing the results together under one roof and also for introducing a general and flexible approach to solving them.