PHASE TRANSITIONS OF COMPOSITION SCHEMES: MITTAG-LEFFLER AND MIXED POISSON DISTRIBUTIONS

• 成果类型: Article
• 署名作者: Banderier, Cyril; Kuba, Markus; Wallner, Michael
• 署名单位: Universite Paris 13; Technische Universitat Wien; Technische Universitat Wien
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2076
• 发表日期: 2024
• 页码: 4635-4693
• 关键词: limit-theorems; increasing trees; recursive trees; singularity analysis; asymptotic enumeration; boltzmann samplers; search-trees; number; approximation; CONVERGENCE

摘要

Multitudinous probabilistic and combinatorial objects are associated with generating functions satisfying a composition scheme F(z) = G(H(z)). The analysis becomes challenging when this scheme is critical (i.e., G and H are simultaneously singular). Motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely F(z, u) = G(uH(z))M(z). We also consider a variant of this scheme, which allows us to analyse the number of H-components of a given size in F. We prove that these two models lead to a rich world of limit laws, where we identify the key role played by a new universal law introduced in this article: the three-parameter Mittag-Leffler distribution, which is essentially the product of a beta and a Mittag-Leffler distribution. We also prove (double) phase transitions, additionally involving Boltzmann and mixed Poisson distributions, bringing a unified explanation of the associated thresholds. In all cases we obtain moment convergence and local limit theorems. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular P & oacute;lya urns, and the Chinese restaurant process.