The Feller Coupling for random derangements

We study derangements of {1,2,…,n} under the Ewens distribution with parameter θ. We give basic properties of derangements, such as the moments and marginal distributions of the cycle counts, the number of cycles, and asymptotic distributions for large n, and we construct, for any given n, a {0,1}-valued non-homogeneous Markov chain ▪ with the property that the counts of lengths of spacings between the 1s have the same distribution as the cycle counts of the random derangement of size n. Unlike the Feller Coupling, this chain does not couple realizations for different values of n – the chain must be rerun to get derangements of other sizes. To resolve this issue we construct another {0,1}-valued Markov chain η whose law coincides with that of the Feller Coupling conditional on no consecutive 1s. The distribution of η, the so-called “Feller Coupling for random derangements”, arises as the weak limit as n→∞ of the distributions of ▪ . Consequently, the asymptotic behavior of finite random derangements may be studied via this coupling. The rate of convergence of ▪ to η is studied via an estimate of their total variation distance. We provide extensive comparisons of these methods, and show that the Markov chain methods generate derangements in time independent of θ for a given n and linear in the size of the derangement.