The number of components in a logarithmic combinatorial structure. (Q1884820): Difference between revisions

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< i\leq n\), given \(\sum_{i> b} iC(n,i)\) is shown to be close to the one obtained for \(C(n)\sim \text{ESF}(\theta)\). These parts of the proof then are connected by Lemma 2.1, proved in Section 6. The paper sharpens results by \textit{H.-K. Hwang} [Adv. Appl. Probab. 31, No. 2, 448--491 (1999; Zbl 0945.60001)].