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

Source abstract

Assemblies are decomposable combinatorial objects characterized by a sequence m i 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 m i κ i 0 / ( 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 ) = ( C 1 ( n ), C 2 ( n ), …, C n ( n )) is defined, where C i ( 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 C b ( n ) = ( C 1 ( n ), C 2 ( n ), …, C b ( n )). It is natural to approximate C b by Z b = ( Z 1 , Z 2 , …, Z b ), the b -dimensional process of independent Poisson variables Z i for which the i th variable has expectation [ ] Z i = m i κ i 0 exp((1−θ) i / n )/ i !. We find asymptotics for the total variation distance between C b ( n ) and Z b .