Total Variation Asymptotics for Poisson Process Approximations of Logarithmic Combinatorial Assemblies
Arratia, Richard ; Stark, Dudley ; Tavare, Simon
Ann. Probab., Tome 23 (1995) no. 3, p. 1347-1388 / Harvested from Project Euclid
Assemblies are the decomposable combinatorial constructions characterized by the exponential formula for generating functions: $\Sigma p(n)s^n/n! = \exp(\Sigma m_is^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 + 2Z_2 + \cdots + nZ_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, \ldots, Z_b)$ and $(C_1(n),\ldots,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 \rightarrow \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 \rightarrow \infty$. Our results are proved using coupling, large deviation bounds and singularity analysis of generating functions.
Publié le : 1995-07-14
Classification:  Singularity analysis,  Ewens sampling formula,  assemblies,  species,  random mappings,  forests,  permutations,  Poisson approximation,  functional limit theorems,  60C05,  60F17,  05A05,  05A16
@article{1176988188,
     author = {Arratia, Richard and Stark, Dudley and Tavare, Simon},
     title = {Total Variation Asymptotics for Poisson Process Approximations of Logarithmic Combinatorial Assemblies},
     journal = {Ann. Probab.},
     volume = {23},
     number = {3},
     year = {1995},
     pages = { 1347-1388},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176988188}
}
Arratia, Richard; Stark, Dudley; Tavare, Simon. Total Variation Asymptotics for Poisson Process Approximations of Logarithmic Combinatorial Assemblies. Ann. Probab., Tome 23 (1995) no. 3, pp.  1347-1388. http://gdmltest.u-ga.fr/item/1176988188/