Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T14:03:00.470Z Has data issue: false hasContentIssue false

Total Variation Asymptotics for Refined Poisson Process Approximations of Random Logarithmic Assemblies

Published online by Cambridge University Press:  01 November 1999

DUDLEY STARK
Affiliation:
BRIMS, Hewlett Packard Laboratories, Filton Road, Stoke Gifford, Bristol, BS34 8QZ, England (e-mail: dstark@hplb.hpl.hp.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Assemblies are decomposable combinatorial objects characterized by a sequence mi that counts the number of possible components of size i. Permutations on n elements, mappings from a set containing n elements into itself, 2-regular graphs on n vertices, and set partitions on a set of size n are all assemblies with natural decompositions. Logarithmic assemblies are characterized by constants θ > 0 and κ0 > 0 such that miκi0/(i−1)! → θ. Random mappings, permutations and 2-regular graphs are all logarithmic assemblies, but set partitions are not.

Given a logarithmic assembly, all representatives having total size n are chosen uniformly and a component counting process C(n) = (C1(n), C2(n), …, Cn(n)) is defined, where Ci(n) is the number of components of size i. Our results also apply to C(n) distributed as the Ewens sampling formula with parameter θ. Denote the component counting process up to size at most b by Cb(n) = (C1(n), C2(n), …, Cb(n)). It is natural to approximate Cb by Zb = (Z1, Z2, …, Zb), the b-dimensional process of independent Poisson variables Zi for which the ith variable has expectation []Zi = miκi0 exp((1−θ)i/n)/i!. We find asymptotics for the total variation distance between Cb(n) and Zb.

Information

Type
Research Article
Copyright
© 1999 Cambridge University Press