The Feller Coupling for random derangements

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

Stochastic Processes and their Applications, 2022, vol. 150, issue C, 1139-1164

Abstract: 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.

Keywords: Feller Coupling; Simulation; Poisson approximation; Poisson–Dirichlet and GEM distributions; Probabilistic combinatorics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414921001459
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:150:y:2022:i:c:p:1139-1164

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2021.09.003

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().