Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 13 (2016) open journal systems 

On moment sequences and mixed Poisson distributions

Markus F. Kuba, FH Technikum Wien
Alois Panholzer, TU-Wien

In this article we survey properties of mixed Poisson distributions and probabilistic aspects of the Stirling transform: given a non-negative random variable \(X\) with moment sequence \((\mu_s)_{s\in\mathbb{N}}\) we determine a discrete random variable \(Y\), whose moment sequence is given by the Stirling transform of the sequence \((\mu_s)_{s\in\mathbb{N}}\), and identify the distribution as a mixed Poisson distribution. We discuss properties of this family of distributions and present a new simple limit theorem based on expansions of factorial moments instead of power moments. Moreover, we present several examples of mixed Poisson distributions in the analysis of random discrete structures, unifying and extending earlier results. We also add several entirely new results: we analyse triangular urn models, where the initial configuration or the dimension of the urn is not fixed, but may depend on the discrete time \(n\). We discuss the branching structure of plane recursive trees and its relation to table sizes in the Chinese restaurant process. Furthermore, we discuss root isolation procedures in Cayley trees, a parameter in parking functions, zero contacts in lattice paths consisting of bridges, and a parameter related to cyclic points and trees in graphs of random mappings, all leading to mixed Poisson-Rayleigh distributions. Finally, we indicate how mixed Poisson distributions naturally arise in the critical composition scheme of Analytic Combinatorics.

AMS 2000 subject classifications: 60C05.

Keywords: Mixed Poisson distribution, factorial moments, Stirling transform, limiting distributions, urn models, parking functions, record-subtrees.

Creative Common LOGO

Full Text: PDF

Kuba, Markus F., Panholzer, Alois, On moment sequences and mixed Poisson distributions, Probability Surveys, 13, (2016), 89-155 (electronic). DOI: 10.1214/14-PS244.


[1]    L. Addario-Berry, N. Broutin, C. Holmgren, Cutting down trees with a Markov chainsaw, Annals of Applied Probability 24, 2297–2339, 2014. MR3262504

[2]    C. Banderier, P. Flajolet, G. Schaeffer, M. Soria, Random maps, coalescing saddles, singularity analysis and Airy phenomena, Random Structures & Algorithms 19, 194–246, 2001. MR1871555

[3]    C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science 281, 37–80, 2002. MR1909568

[4]    C. Banderier and M. Wallner, Some reflections on directed lattice paths, DMTCS Proceedings Series, Proceedings of AofA 2014, to appear, 2014.

[5]    J. Bertoin, Fires on trees, Annales de l’Institut Henri Poincaré Probabilités et Statistiques 48, no. 4, 909–921, 2012. MR3052398

[6]    J. Bertoin, Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures & Algorithms 44, 29–44, 2014. MR3143589

[7]    J. Bertoin, The cut-tree of large recursive trees, Annales de l’Institut Henri Poincaré, to appear. MR3335011

[8]    E. Baur and J. Bertoin, Cutting edges at random in large recursive trees, Preprint, available at http://hal.archives-ouvertes.fr/docs/01/00/31/51/PDF/cutting-edges.pdf. MR3332709

[9]    J. Bertoin and G. Miermont, The cut-tree of large Galton-Watson trees and the Brownian CRT, Annals of Applied Probability 23, 1469–1493, 2013. MR3098439

[10]    Z.-D. Bai, F. Hu and L.-X. Zhang, Gaussian approximation theorems for urn models and their applications, Annals of Applied Probability 12, 1149–1173, 2002. MR1936587

[11]    F. Bergeron, P. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science 581, 24–48, 1992. MR1251994

[12]    M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra and its Applications 226/228, 57–72, 1995. MR1344554

[13]    F. Brenti, Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Memoirs Amer. Math. Soc. 81, no. 413, 1989. MR0963833

[14]    F. Brenti, Hilbert polynomials in combinatorics, J. Algebraic Combinatorics 7, 127–156, 1998. MR1609885

[15]    T. Carleman, Sur le problème des moments, Acad. Sci. Paris 174, 1680–1682, 1922.

[16]    P. Chassaing and G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence, Random Structures & Algorithms 21, 76–119, 2002. MR1913079

[17]    J. H. Curtiss, A note on the theory of moment generating functions, Annals of Math. Stat. 13, 430–433, 1942. MR0007577

[18]    M. Drmota and M. Soria, Images and preimages in random mappings, SIAM Journal on Discrete Mathematics 10, 246–269, 1997. MR1445035

[19]    M. Drmota and M. Soria. Marking in combinatorial constructions: Generating functions and limiting distributions, Theoretical Computer Science 144, 67–99, 1995. MR1337754

[20]    A. Ferrari, G. Letacy and J.-Y. Tourneret, Multivariate mixed Poisson distributions, EUSIPCO-04, Vienna, Austria, 2004.

[21]    P. Flajolet, P. Dumas and V. Puyhaubert, Some exactly solvable models of urn process theory, Discrete Mathematics and Theoretical Computer Science, vol. AG, 59–118, 2006, in “Proceedings of Fourth Colloquium on Mathematics and Computer Science”, P. Chassaing Editor. MR2509623

[22]    P. Flajolet, J. Gabarró and H. Pekari, Analytic urns, Annals of Probability 33, 1200–1233, 2005. MR2135318

[23]    P. Flajolet and A. Odlyzko, Random mapping statistics, in: Advances in cryptology – EUROCRYPT ’89, Lecture Notes in Computer Science 434, 329–354, Springer, Berlin, 1990. MR1083961

[24]    P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, Cambridge, UK, 2009. MR2483235

[25]    P. Flajolet and M. Soria, Gaussian limiting distributions for the number of components in combinatorial structures, J. Combinatorial Theory, Series A 53, 165–182, 1990. MR1041444

[26]    P. Flajolet and M. Soria, The cycle construction, SIAM Journal on Discrete Mathematics 4, 58–60, 1991. MR1090289

[27]    P. Flajolet and M. Soria, General combinatorial schemas: Gaussian limit distributions and exponential tails, Discrete Mathematics 114, 159–180, 1993. MR1217750

[28]    P. Flajolet and J. Vitter, Average case analysis of algorithms and data structures, in Handbook of Theoretical Computer Science, 431–524, Elsevier, Amsterdam, 1990. MR1127175

[29]    I. Gessel and R. P. Stanley, Stirling polynomials, Journal of Combinatorial Theory, Series A 24, 24–33, 1978. MR0462961

[30]    R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Second Edition. Reading, Massachusetts: Addison-Wesley, 1994. MR1397498

[31]    R. Grübel and N. Stefanoski, Mixed Poisson approximation of node depth distributions in random binary search trees, Annals of Applied Probability 15, 279–297, 2005. MR2115044

[32]    A. Gut, On the moment problem, Bernoulli 8, 407–421, 2002. MR1913113

[33]    H.-K. Hwang and R. Neininger, Phase change of limit laws in the quicksort recurrence under varying toll functions, SIAM Journal on Computing 31, 1687–1722, 2002. MR1954876

[34]    S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic processes and applications 110, 177–245, 2004. MR2040966

[35]    S. Janson, Random records and cuttings in complete binary trees, Mathematics and Computer Science III, Algorithms, Trees, Combinatorics and Probabilities, M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger (eds.), 241–253, Birkhäuser, Basel, 2004. MR2090513

[36]    S. Janson, Random cutting and records in deterministic and random trees, Random Structures & Algorithms 29, 139–179, 2006. MR2245498

[37]    S. Janson, Limit theorems for triangular urn schemes, Probability Theory and Related Fields 134, 417–452, 2005. MR2226887

[38]    S. Janson, Plane recursive trees, Stirling permutations and an urn model, Proceedings, Fifth Colloquium on Mathematics and Computer Science (Blaubeuren, 2008), DMTCS Proceedings AI, 541–548, 2008. MR2508813

[39]    S. Janson, Moments of Gamma type and the Brownian supremum process area, Probability Surveys, 7, 1–52, 2010. MR2645216

[40]    S. Janson, M. Kuba and A. Panholzer, Generalized Stirling permutations, families of increasing trees and urn models, Journal of Combinatorial Theory, Series A 118, 94–114, 2011. MR2737187

[41]    N. L. Johnson, S. Kotz and A. W. Kemp, Univariate Discrete Distributions, 2. Edition, New York, John Wiley, 1992. MR1224449

[42]    D. Karlis and E. Xekalaki, Mixed Poisson Distributions, International Statistical Review 73, 35–58, 2005.

[43]    D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, 1998. MR3077154

[44]    L.  M. Koganov, Universal bijection between Gessel-Stanley permutations and diagrams of connections of corresponding ranks, Uspekhi Mat. Nauk 51, no. 2(308), 165–166, 1996; English translation in Russian Math. Surveys 51, no. 2, 333–335, 1996. MR1401550

[45]     A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics 14, 1266–1274, 1966.

[46]    M. Kuba, A note on Critical Compositions and Mixed Poisson distributions, manuscript.

[47]    M. Kuba and A. Panholzer, Descendants in increasing trees, Electronic Journal of Combinatorics 13 (1), Paper 8, 2006. MR2200536

[48]    M. Kuba and A. Panholzer, Analysis of label-based parameters in increasing trees, Discrete Mathematics and Theoretical Computer Science, Proceedings AG, 321–330, 2006. MR2509642

[49]    M. Kuba and A. Panholzer, On the degree distribution of the nodes in increasing trees, Journal of Combinatorial Theory, Series A 114, 597–618, 2007. MR2319165

[50]    M. Kuba and A. Panholzer, Isolating nodes in recursive trees, Aequationes Mathematicae 76, 258–280, 2008. MR2461893

[51]    M. Kuba and A. Panholzer, Analysis of statistics for generalized Stirling permutations, Combinatorics, Probability and Computing 20, 875–910, 2011. MR2847273

[52]    M. Kuba and A. Panholzer, On death processes and urn models, Discrete Mathematics and Theoretical Computer Science, in: “Proceedings of the 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2012)”, Proceedings AQ, 29–42, 2012. MR2957318

[53]    M. Kuba and A. Panholzer, Limiting distributions for a class of diminishing urn models, Advances in Applied Probability 44, 1–31, 2012. MR2951548

[54]    M. Kuba and A. Panholzer, Isolating nodes in recursive trees, Online Journal of Analytic Combinatorics 9, 2014, 26 pages. MR3259471

[55]    M. Loève, Probability Theory I, 4th Edition, Springer-Verlag, New York, 1977. MR0651017

[56]    H. Mahmoud and R. Smythe, On the distribution of leaves in rooted subtrees of recursive trees, Annals of Applied Probability 1, 406–418, 1991. MR1111525

[57]    A. Meir and J. W. Moon, Cutting down random trees, Journal of the Australian Mathematical Society 11, 313–324, 1970. MR0284370

[58]    A. Meir and J. W. Moon, Cutting down recursive trees, Mathematical Biosciences 21, 173–181, 1974.

[59]    J. C. Massé, and R.  Theodorescu, Neyman type A distribution revisited, Statistica Neerlandica, Volume 59, Issue 2, 206–213, 2005. MR2153615

[60]    J. Neyman, On a new class of “contagious” distributions applicable in entomology and bacteriology, Annals of Mathematical Statistics 10, 35–57, 1939.

[61]    A. Panholzer, Non-crossing trees revisited: cutting down and spanning subtrees, Discrete Random Walks, C. Banderier and C. Krattenthaler (eds.), Discrete Mathematics and Theoretical Computer Science, Proceedings AC, 265–276, 2003. MR2042393

[62]     A. Panholzer, Cutting down very simple trees, Quaestiones Mathematicae 29, 211–228, 2006. MR2233368

[63]    A. Panholzer and H. Prodinger, The level of nodes in increasing trees revisited, Random Structures & Algorithms 31, 203–226, 2007. MR2343719

[64]    A. Panholzer and G. Seitz, Limiting distributions for the number of inversions in labelled tree families, Annals of Combinatorics 16, 847–870, 2012. MR3000449

[65]    A. Panholzer and G. Seitz, Ancestors and descendants in evolving k-tree models, Random Structures & Algorithms 44, 465–489, 2014. MR3214201

[66]    S. K. Park, The r-multipermutations, Journal of Combinatorial Theory, Series A 67, 44–71, 1994. MR1280598

[67]    S. K. Park, Inverse descents of r-multipermutations, Discrete Mathematics 132, 215–229, 1994. MR1297383

[68]    S. K. Park, P-partitions and q-Stirling numbers, Journal of Combinatorial Theory, Series A 68, 33–52, 1994. MR1295782

[69]    J. Pitman, Exchangeable and partially exchangeable random partitions, Probab. Theory Relat. Fields 102, 145–158, 1995. MR1337249

[70]    N. Pouyanne, An algebraic approach to Pólya processes, Annales de l’Institut Henri Poincaré 44, 293–323, 2008. MR2446325

[71]    N.  Privault, Generalized Bell polynomials and the combinatorics of Poisson central moments, Electronic Journal of Combinatorics 18, Paper 54, 2011. MR2776830

[72]    V. Puyhaubert, Modéles d’urnes et phénoménes de seuils en combinatoire analytique, Ph.D. thesis, École Polytechnique, Palaiseau, 2005.

[73]    R. Stanley, Enumerative Combinatorics, Volume I & II, Cambridge University Press, 1997 & 1999.

[74]    C. Su, Q. Feng and Z. Hu, Uniform recursive trees: Branching structure and simple random downward walk, Journal of Mathematical Analysis and Applications 315, 225–243, 2006. MR2196543

[75]    Eric W. Weisstein, “Stirling Transform”, From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/StirlingTransform.html

[76]    H. S. Wilf, Generatingfunctionology, Second Edition, Academic Press, 1992. MR1277813

[77]    G. Willmot, Mixed compound Poisson distributions, ASTIN Bulletin 16, 59–80, 1986.

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787