Total variation asymptotics for Poisson process approximations for logarithmic combinatorial assemblies. (English) Zbl 0833.60010

Arratia, Richard; Stark, Dudley; Tavaré, Simon

Ann. Probab. 23, No. 3, 1347-1388 (1995).

Summary: Assemblies are the decomposable combinatorial constructions characterized by the exponential formula for generating functions: \(\sum p (n)s^n/n! = \text{exp} (\sum m_i s^i/i!)\). Here \(p(n)\) is the total number of constructions that can be formed from a set of size \(n\), and \(m_n\) is the number of these structures consisting of a single component. Examples of assemblies include permutations, graphs, 2-regular graphs, forests of rooted or unrooted trees, set partitions, and mappings of a set into itself. If an assembly is chosen uniformly from all possibilities on a set of size \(n\), the counts \(C_i(n)\) of components of size \(i\) are jointly distributed like independent nonidentically distributed Poisson variables \(Z_i\) conditioned on the event \(Z_1 + 2 Z_2 + \cdots + n Z_n = n\). We consider assemblies for which the process of component-size counts has a nontrivial limit distribution, without renormalizing. These include permutations, mappings, forests of labelled trees and 2-regular graphs, but not graphs and not set partitions. For some of these assemblies, the distribution of the component sizes may be viewed as a perturbation of the Ewens sampling formula with parameter \(\theta\).
We consider \(d_b (n)\), the total variation distance between \((Z_1, \dots, Z_b)\) and \((C_1(n), \dots, C_b(n))\), counting components of size at most \(b\). If the generating function of an assembly satisfies a mild analytic condition, we can determine the decay rate of \(d_b(n)\). In particular, for \(b = b(n) = o(n/\log n)\) and \(n \to \infty\), \(d_b(n)=o(b/n)\) if \(\theta=1\) and \(d_b(n) \sim c(b)b/n\) if \(\theta \neq 1\). The constant \(c(b)\) is given explicitly in terms of the \(m_i :c(b) = |1 - \theta |\mathbb{E} |T_{0b}-\mathbb{E} T_{0b}|/(2b)\), where \(T_{0b} = Z_1 + 2Z_2 + \cdots + bZ_b\). Finally, we show that for \(\theta \neq 1\) there is a constant \(c_\theta\) such that \(c(b) \sim c_\theta b\) as \(b \to \infty\). Our results are proved using coupling, large deviation bounds and singularity analysis of generating functions.

MSC:

60C05	Combinatorial probability
60F17	Functional limit theorems; invariance principles
05A05	Permutations, words, matrices
05A16	Asymptotic enumeration

Keywords:

singularity analysis; Ewens sampling formula; assemblies; species; random mappings; forests; permutations; Poisson approximation; functional limit theorems