Random derangements and the Ewens Sampling Formula

MaRDI QIDQ6342404zbMATH OpenFDO

Authors Poly H. da Silva, Arash Jamshidpey, Simon Tavaré

Publication date 8 June 2020

Mathematics Subject Classification ID

Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: We study derangements of $1,2,ldots,n$ under the Ewens distribution with parameter $heta$. We give the moments and marginal distributions of the cycle counts, the number of cycles, and asymptotic distributions for large $n$. We develop a $0,1$-valued non-homogeneous Markov chain with the property that the counts of lengths of spacings between the 1s have the derangement distribution. This chain, an analog of the so-called Feller Coupling, provides a simple way to simulate derangements in time independent of $heta$ for a given $n$ and linear in the size of the derangement.

This page was built for publication: Random derangements and the Ewens Sampling Formula

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342404)