Approximation by the Dickman Distribution and Quasi-Logarithmic Combinatorial Structures

Andrew D Barbour (Universität Zürich)
Bruno Nietlispach (Universität Zürich)


Quasi-logarithmic combinatorial structures are a class of decomposable combinatorial structures which extend the logarithmic class considered by Arratia, Barbour and Tavaré (2003). In order to obtain asymptotic approximations to their component spectrum, it is necessary first to establish an approximation to the sum of an associated sequence of independent random variables in terms of the Dickman distribution. This in turn requires an argument that refines the Mineka coupling by incorporating a blocking construction, leading to exponentially sharper coupling rates for the sums in question. Applications include distributional limit theorems for the size of the largest component and for the vector of counts of the small components in a quasi-logarithmic combinatorial structure.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 880-902

Publication Date: May 4, 2011

DOI: 10.1214/EJP.v16-881


R. Arratia, A. D. Barbour and S. Tavaré. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics, European Mathematical Society (EMS), Zürich 2003. MR2032426 (2004m:60004).

R. Arratia, A. D. Barbour and S. Tavaré. A probabilistic approach to analytic arithmetic on algebraic function fields. Math. Proc. Cambridge Philos. Soc. 139 (2005), 1–26. MR2155502 (2006d:11090).

R. Arratia, D. Stark, and S. Tavaré. Total variation asymptotics for Poisson process approximations of logarithmic combinatorial assemblies, Ann. Probab. 23 (1995), 1347–1388. MR1349176 (96f:60008).

A. D. Barbour, L. H. Y. Chen, and W.-L. Loh. Compound Poisson approximation for nonnegative random variables via Stein's method, Ann. Probab. 20 (1992), 1843–1866. MR1188044 (93k:60044).

A. D. Barbour and B. L. Granovsky. Random combinatorial structures: the convergent case. J. Combin. Theory Ser. A 109 (2005), 203–220. MR2121024 (2005m:60225).

A. Beurling. Analyse de la loi asymptotique de la distribution des nombres premiers généralisés. Acta Math. 68 (1937), 255–291. Math. Review number not available.

F. Chung and L. Lu. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics 3 (2006), 79–127. MR2283885 (2008j:60049).

K. Dickman. On the frequency of numbers containing prime factors of a certain relative magnitude. Ark. Math. Astr. Fys. 22 no. 10 (1930), 1–14. Math. Review number not available.

G. A. Freiman and B. L. Granovsky. Asymptotic formula for a partition function of reversible coagulation-fragmentation processes. Israel J. Math. 130 (2002), 259–279. MR1919380 (2003i:60036).

J. F. C. Kingman. The population structure associated with the Ewens sampling formula. Theoret. Population Biology 11 (1977), 274–283. MR0682238 (58 #33117).

J. Knopfmacher. Analytic arithmetic of algebraic function fields. Lecture Notes in Pure and Applied Mathematics 50, Marcel Dekker Inc., New York, 1979. MR0545904 (81d:10031).

J. Kubilius. Probabilistic methods in the theory of numbers. Translations of Mathematical Monographs 11, American Mathematical Society, Providence, R.I., 1964. MR0160745 (28 #3956).

T. Lindvall. Lectures on the coupling method. Dover Publications Inc., Mineola, NY, 2002. MR1924231 and MR1180522 (94c:60002).

E. Manstavičius. Strong convergence on weakly logarithmic combinatorial assemblies. arXiv:0903.1051 (2009). Math. Review number not available.

L. Mattner and B. Roos. A shorter proof of Kanter's Bessel function concentration bound. Prob. Theory Rel. Fields 139 (2007), 191–205. MR2322695 (2008e:60044).

J. Mineka. A criterion for tail events for sums of independent random variables. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 25 (1973), 163–170. MR0350890 (50 #3382).

U. Rösler. Das 0-1-Gesetz der terminalen σ-Algebra bei Harrisirrfahrten. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 37 (1977), 227–242. MR0428451 (55 #1472).

L. C. G. Rogers. Fastest coupling of random walks. J. London Math. Soc. 60 (1999), 630–640. MR1724813 (2001k:60068).

W. Vervaat. Success epochs in Bernoulli trials with applications in number theory. Mathematical Centre Tracts 42, Mathematisch Centrum, Amsterdam, 1972. MR0328989 (48 #7331).

W.-B. Zhang. The prime element theorem in additive arithmetic semigroups, I. Illinois J. Math. 40 (1996), 245–280. MR1398093 (97m:11123).

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.