Random Cyclations

Nicholas Pippenger

Abstract


Consider $n$ unit intervals, say $[1,2], [3,4], \ldots, [2n-1,2n]$. Identify their endpoints in pairs at random, with all $(2n-1)!! = (2n-1)(2n-3)\cdots 3\cdot 1$ pairings being equally likely. The result is a collection of cycles of various lengths, and we investigate the distribution of these lengths. The distribution is similar to that of the distribution of the lengths of cycles in a random permutation, but it also exhibits some striking differences.


Keywords


Permutations; Cycle lengths; Asymptotics

Full Text: PDF