TOTAL VARIATION ASYMPTOTICS FOR POISSON-PROCESS APPROXIMATIONS OF LOGARITHMIC COMBINATORIAL ASSEMBLIES

• 成果类型: Article
• 署名作者: ARRATIA, R; STARK, D; TAVARE, S
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1176988188
• 发表日期: 1995
• 页码: 1347-1388
• 关键词: CENTRAL-LIMIT-THEOREM; random permutations; Random mappings; allocation; particles; cells

摘要

Assemblies are the decomposable combinatorial constructions characterized by the exponential formula for generating functions: Sigma p(n)s(n)/n! = exp(Sigma 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) + 2Z(2) + ... +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),...,Z(b)) and (C-1(n),...,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 --> infinity, d(b)(n) = o(b/n) if theta = 1 and d(b)(n) similar to c(b)b/n, if theta not equal 1. The constant c(b) is given explicitly in terms of the m(i): c(b) = \1 - theta\E\T-ob - ET(ob)\/(2b), where T-ob = Z(1) + 2Z(2) + ... +bZ(b). Finally, we show that for theta not equal 1 there is a constant c(theta) such that c(b)similar to c(theta)b as b --> infinity. Our results are proved using coupling, large deviation bounds and singularity analysis of generating functions.