Random mappings with Ewens cycle structure

Authors:

• Jennie C. Hansen,
• Jerzy Jaworski

Abstract

In this paper we consider a random mapping, T̂ _n,θ , of the finite set {1,2,...,n} into itself for which the digraph representation Ĝ _n,θ is constructed by: (1) selecting a random number, L̂ _n , of cyclic vertices, (2) constructing a uniform random forest of size n with the selected cyclic vertices as roots, and (3) forming 'cycles' of trees by applying to the selected cyclic vertices a random permutation with cycle structure given by the Ewens sampling formula with parameter θ. We investigate k̂ _n,θ , the size of a 'typical' component of Ĝ _n,θ , and we obtain the asymptotic distribution of k̂ _n,θ conditioned on L̂ _n = m(n). As an application of our results, we show in Section 3 that provided L̂ _n is of order much larger than √n, then the joint distribution of the normalized order statistics of the component sizes of Ĝ _n,θ converges to the Poisson-Dirichlet(θ) distribution as n→∞.