Random Mappings with Ewens Cycle Structure

Abstract

In this paper, we consider a random mapping ${\hat{T}}_{n,\theta }$ of the finite set $\{1,2,\dots ,n\}$ into itself, for which the digraph representation ${\hat{G}}_{n,\theta }$ is constructed by: (1) selecting a random number ${\hat{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 $\theta$. We investigate ${\hat{k}}_{n,\theta }$, the size of a `typical’ component of ${\hat{G}}_{n,\theta }$, and we obtain the asymptotic distribution of ${\hat{k}}_{n,\theta }$ conditioned on ${\hat{L}}_n=m(n)$. As an application of our results, we show in Section 3 that provided ${\hat{L}}_n$ is of order much larger than $\sqrt{n}$, then the joint distribution of the normalized order statistics of the component sizes of $G_{n,\theta }$ converges to the Poisson-Dirichlet $(\theta )$ distribution as $n\to \mathrm{\infty }$.