Simulating the component counts of combinatorial structures

Richard Arratia, A.D. Barbour, W.J. Ewens and Tavaré, Simon

Theoretical Population Biology, 2018, vol. 122, issue C, 5-11

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

Keywords: Chinese restaurant process; Ewens sampling formula; Feller coupling; Random mappings; Random permutations; Spaghetti loop distribution (search for similar items in EconPapers)
Date: 2018
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/S0040580918300224
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:thpobi:v:122:y:2018:i:c:p:5-11

DOI: 10.1016/j.tpb.2018.02.002

Access Statistics for this article

Theoretical Population Biology is currently edited by Jeremy Van Cleve

More articles in Theoretical Population Biology from Elsevier
Bibliographic data for series maintained by Catherine Liu ().