Header

UZH-Logo

Maintenance Infos

Simulating the component counts of combinatorial structures


Arratia, Richard; Barbour, AD; Ewens, WJ; Tavaré, Simon (2018). Simulating the component counts of combinatorial structures. Theoretical population biology, 122: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.

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.

Statistics

Citations

Dimensions.ai Metrics
2 citations in Web of Science®
2 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

2 downloads since deposited on 15 Nov 2018
2 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Uncontrolled Keywords:Ecology, Evolution, Behavior and Systematics
Language:English
Date:1 July 2018
Deposited On:15 Nov 2018 13:44
Last Modified:09 Feb 2019 01:02
Publisher:Elsevier
ISSN:0040-5809
OA Status:Green
Publisher DOI:https://doi.org/10.1016/j.tpb.2018.02.002

Download

Download PDF  'Simulating the component counts of combinatorial structures'.
Preview
Content: Accepted Version
Language: English
Filetype: PDF
Size: 282kB
View at publisher
Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)