Repository logo
 

Simulating the component counts of combinatorial structures.

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Arratia, Richard 
Barbour, AD 
Ewens, WJ 
Tavaré, Simon 

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.

Description

Keywords

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

Journal Title

Theoretical Population Biology

Conference Name

Journal ISSN

0040-5809
1096-0325

Volume Title

Publisher

Elsevier
Sponsorship
ADB acknowledges support from ARC grants DP150101459 and DP150103588.