The number of components in a logarithmic combinatorial structure

Citation
R. Arratia et al., The number of components in a logarithmic combinatorial structure, ANN APPL PR, 10(2), 2000, pp. 331-361
Citations number
34
Categorie Soggetti
Mathematics
Journal title
ANNALS OF APPLIED PROBABILITY
ISSN journal
10505164 → ACNP
Volume
10
Issue
2
Year of publication
2000
Pages
331 - 361
Database
ISI
SICI code
1050-5164(200005)10:2<331:TNOCIA>2.0.ZU;2-2
Abstract
Under very mild conditions, we prove that the number of components in a dec omposable logarithmic combinatorial structure has a distribution which is c lose to Poisson in total variation. The conditions are satisfied for all as semblies, multisets and selections in the logarithmic class. The error in t he Poisson approximation is shown under marginally more restrictive conditi ons to be of exact order O(1/ log n), by exhibiting the penultimate asympto tic approximation; similar results have previously been obtained by Hwang [ 20], under stronger assumptions. Our method is entirely probabilistic, and the conditions can readily be verified in practice.