Send to

Choose Destination
Theor Popul Biol. 2018 Jul;122:5-11. doi: 10.1016/j.tpb.2018.02.002. Epub 2018 Feb 9.

Simulating the component counts of combinatorial structures.

Author information

Department of Mathematics, University of Southern California, Los Angeles, CA 90089, USA.
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, 8057 Zürich, Switzerland.
Department of Biology, University of Pennsylvania, 433 S University Ave, Philadelphia, PA 19104, USA.
DAMTP, University of Cambridge, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WA, UK. Electronic address:


This article describes and compares methods for simulating the component counts of random logarithmic combinatorial structures such as permutations and mappings. We exploit the Feller coupling for simulating permutations to provide a very fast method for simulating logarithmic assemblies more generally. For logarithmic multisets and selections, this approach is replaced by an acceptance/rejection method based on a particular conditioning relationship that represents the distribution of the combinatorial structure as that of independent random variables conditioned on a weighted sum. We show how to improve its acceptance rate. We illustrate the method by estimating the probability that a random mapping has no repeated component sizes, and establish the asymptotic distribution of the difference between the number of components and the number of distinct component sizes for a very general class of logarithmic structures.


Chinese restaurant process; Ewens sampling formula; Feller coupling; Random mappings; Random permutations; Spaghetti loop distribution

[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Elsevier Science
Loading ...
Support Center