Profiles of Permutations

  • Michael Lugo

Abstract

This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $\sigma$ and, on the other hand, permutations selected according to the Ewens distribution with parameter $\sigma$. In particular we show that the asymptotic expected number of cycles of random permutations of $[n]$ with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter $1/2$ are all ${1 \over 2} \log n + O(1)$, and the variance is of the same order. Furthermore, we show that in permutations of $[n]$ chosen from the Ewens distribution with parameter $\sigma$, the probability of a random element being in a cycle longer than $\gamma n$ approaches $(1-\gamma)^\sigma$ for large $n$. The same limit law holds for permutations with cycles carrying multiplicative weights with average $\sigma$. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.

Published
2009-08-07
Article Number
R99