The number of components in a logarithmic combinatorial structure.
type: Item
instance of: scholarly article
title: The number of components in a logarithmic combinatorial structure.
zbMATH Open document ID: 1056.60012
author: Richard Arratia
author: Simon Tavaré
author: A. D. Barbour
published in: The Annals of Applied Probability
publication date: 2004-10-27T00:00:00Z
review text: Let \(Z_1,Z_2,\dots\) be a sequence of independent nonnegative integer-valued random variables and \(C(n)= C(n,1),\dots, C(n,n)\), \(n= 1,2,\dots\), be an array of random variables satisfying the conditioning relation \({\mathcal L}(C(n))= {\mathcal L}(Z_1,\dots, Z_n\mid \sum^n_{i=1} i Z_i= n)\) and also the logarithmic condition \(iP(Z_i= 1)\to \theta\), \(iEZ_i\to \theta\), \(i\to\infty\), with \(\theta> 0\). The \(C(n,i)\) describe so-called logarithmic combinatorial structures, e.g. \(C(n,i)\) is the number of cycles of size \(i\) in a random permutation of \((1,\dots, n)\) or, more general, in a permutation \(\pi\) chosen with weight \(\theta^K\), where \(K\) is the total number of cycles in \(\pi\). Then \(Z_i\) is Poisson \((\theta/i)\) and the distribution of \(C(n)\) has the Ewens sampling formula distribution \(\text{ESF}_n(\theta)\), cf. \textit{G. A. Watterson} [Adv. Appl. Probab. 6, 463--488 (1974; Zbl 0289.62020)]. Other examples are multisets and selections. In general \(C(n,i)\) denotes the number of components of size \(i\) in the combinatorial structure. The paper shows that under mild conditions the distribution of \(K_n= \sum_i C(n,i)\), the total number of components, is close to a Poisson or perturbed Poisson distribution, with closeness always in terms of total variation. The order of convergence depends on the conditions, three of which, ULC(0), \((1)\), \((r)\), \(r> 1\), have increasing strength. Under \((0)\) there is an estimate for \({\mathcal L}(K_n)-{\mathcal L} (\sum_{i\leq\alpha n}Z_i)\), becoming \(O(1/\log n)\) for \((1)\). Under \((3)\) there is an estimate for \({\mathcal L}(K_n)- \nu_n\), with \(\nu_n\) perturbed Poisson, and also a first-order asymptotic term with \(O(\log n)^{-3/2}\) error. The proof separates the treatment for small and large \(i\). Theorem 4.3 estimates \({\mathcal L}(C(n,i), i\leq b)-{\mathcal L}\left(\sum_{i\leq b} Z_i\right),\) uniformly in \(4b< n\). In Section 3 the joint distribution of \(C(n,i)\), \(b…
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 2110907
zbMATH Keywords: logarithmic combinatorial structures
zbMATH Keywords: random permutations
zbMATH Keywords: limit theorem
zbMATH Keywords: conditional distribution
zbMATH Keywords: Poisson distribution
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2110907