Random mappings with Ewens cycle structure
Jennie C. Hansen, Jerzy Jaworski · Ars Combinatoria · 2013
In this paper we consider a random mapping, Tn,θ, of the finite set {1, 2, ..., n} into itself for which the digraph representation Ĝn,θ is constructed by: (1) selecting a random number, Ln, 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 kn,θ, the size of a ‘typical’ component of Ĝn,θ, and we obtain the asymptotic distribution of kn,θ conditioned on Ln = m(n). As an application of our results, we show in Section 3 that provided Ln 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→∞. ∗Actuarial Mathematics and Statistics Department and The Maxwell Institute for Mathematical Sciences, Heriot–Watt University, Edinburgh EH14 4AS, UK; email: [email protected] †Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznan, Poland; email: [email protected] ‡J. Jaworski acknowledges the support by the Marie Curie Intra-European Fellowship No. 236845 (RANDOMAPP) within the 7th European Community Framework Programme and by National Science Centre DEC-2011/01/B/ST1/03943.