×

zbMATH — the first resource for mathematics

On moment sequences and mixed Poisson distributions. (English) Zbl 1377.60021
This survey article covers the basic theory as well as several applications of the mixed Poisson distribution. Roughly speaking, the mixed Poisson distribution refers to a class of distributions that follow the Poisson law whose parameter is a random variable. The distribution of this is called the mixing distribution. According to the choice of the mixing distribution, one can derive the ordinary Poisson distribution, the negative binomial distribution, the Rayleigh distribution and others. The article gives the basic theorems that associate the moments of the mixed Poisson distribution with the moments of the mixing distribution. These are obtained through the Stirling transformations that relate Stirling numbers of the first kind with those of the second kind. It also covers conditions that imply that a given sequence of random variables converges in distribution to the a random variable that follows the mixed Poisson distribution. After this fundamental theory, several applications of the mixed Poisson distribution are discussed. Those start with the block sizes of Stirling permutations, several urn models, such as the class of diminishing Pólya-Eggenberger urns models. Another important class of applications discussed is that of trees. In particular, increasing trees are discussed as well as recursive trees. In that context, the distribution of node degrees is considered. Thereafter, the model of triangular urns is considered, which is a generalisation of an urn model that is encountered in the analysis of random recursive trees. There, convergence in distribution is proved for the (rescaled) number of balls of a given colour. Also, a special class of mixed distribution with mixing distribution is discussed, namely the Rayleigh distribution. This occurs naturally in the context of random trees and parking functions. Particular applications are discussed. Also, some applications on the zeros of walks are discussed, as well as on random mappings. Finally, the notion of multivariate mixed Poisson distribution is discussed.

MSC:
60C05 Combinatorial probability
60-02 Research exposition (monographs, survey articles) pertaining to probability theory
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] L. Addario-Berry, N. Broutin, C. Holmgren, Cutting down trees with a Markov chainsaw, Annals of Applied Probability 24, 2297-2339, 2014. · Zbl 1352.60009 · doi:10.1214/13-AAP978 · euclid:aoap/1409058033 · arxiv:1110.6455
[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. · Zbl 1016.68179 · doi:10.1002/rsa.10021
[3] C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science 281, 37-80, 2002. · Zbl 0996.68126 · doi:10.1016/S0304-3975(02)00007-5
[4] C. Banderier and M. Wallner, Some reflections on directed lattice paths , DMTCS Proceedings Series , Proceedings of AofA 2014, to appear, 2014. · Zbl 1332.68162 · hal.inria.fr
[5] J. Bertoin, Fires on trees, Annales de l’Institut Henri Poincaré Probabilités et Statistiques 48, no. 4, 909-921, 2012. · Zbl 1263.60083 · doi:10.1214/11-AIHP435 · euclid:aihp/1353098433
[6] J. Bertoin, Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures & Algorithms 44, 29-44, 2014. · Zbl 1280.05117 · doi:10.1002/rsa.20448
[7] J. Bertoin, The cut-tree of large recursive trees, Annales de l’Institut Henri Poincaré , · Zbl 1351.60010 · doi:10.1214/13-AIHP597
[8] E. Baur and J. Bertoin, Cutting edges at random in large recursive trees, Preprint, available at . · Zbl 1358.05253 · hal.archives-ouvertes.fr
[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. · Zbl 1279.60035 · doi:10.1214/12-AAP877 · euclid:aoap/1371834035 · arxiv:1201.4081
[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. · Zbl 1014.60025 · doi:10.1214/aoap/1037125857
[11] F. Bergeron, P. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science 581, 24-48, 1992. · doi:10.1007/3-540-55251-0_2
[12] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra and its Applications 226/228, 57-72, 1995. · Zbl 0832.05002 · doi:10.1016/0024-3795(94)00245-9
[13] F. Brenti, Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Memoirs Amer. Math. Soc. 81, no. 413, 1989. · Zbl 0697.05011 · doi:10.1090/memo/0413
[14] F. Brenti, Hilbert polynomials in combinatorics, J. Algebraic Combinatorics 7, 127-156, 1998. · Zbl 0901.05093 · doi:10.1023/A:1008656320759
[15] T. Carleman, Sur le problème des moments, Acad. Sci. Paris 174, 1680-1682, 1922. · JFM 48.1263.03
[16] P. Chassaing and G. Louchard, Phase transition for parking blocks, Brownian excursion and coalescence, Random Structures & Algorithms 21, 76-119, 2002. · Zbl 1032.60003 · doi:10.1002/rsa.10039
[17] J. H. Curtiss, A note on the theory of moment generating functions, Annals of Math. Stat. 13, 430-433, 1942. · Zbl 0063.01024 · doi:10.1214/aoms/1177731541
[18] M. Drmota and M. Soria, Images and preimages in random mappings, SIAM Journal on Discrete Mathematics 10, 246-269, 1997. · Zbl 0867.05001 · doi:10.1137/S0895480194268421
[19] M. Drmota and M. Soria. Marking in combinatorial constructions: Generating functions and limiting distributions, Theoretical Computer Science 144, 67-99, 1995. · Zbl 0874.68143 · doi:10.1016/0304-3975(94)00294-S
[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. · Zbl 1193.60011 · www.dmtcs.org
[22] P. Flajolet, J. Gabarró and H. Pekari, Analytic urns, Annals of Probability 33, 1200-1233, 2005. · Zbl 1073.60007 · doi:10.1214/009117905000000026 · arxiv:math/0407098
[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. · Zbl 0747.05006 · doi:10.1007/3-540-46885-4_34
[24] P. Flajolet and R. Sedgewick, Analytic Combinatorics , Cambridge Univ. Press, Cambridge, UK, 2009. · Zbl 1165.05001
[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. · Zbl 0691.60035 · doi:10.1016/0097-3165(90)90056-3
[26] P. Flajolet and M. Soria, The cycle construction, SIAM Journal on Discrete Mathematics 4, 58-60, 1991. · Zbl 0714.05003 · doi:10.1137/0404006
[27] P. Flajolet and M. Soria, General combinatorial schemas: Gaussian limit distributions and exponential tails, Discrete Mathematics 114, 159-180, 1993. · Zbl 0776.60013 · doi:10.1016/0012-365X(93)90364-Y
[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. · Zbl 0900.68251
[29] I. Gessel and R. P. Stanley, Stirling polynomials, Journal of Combinatorial Theory, Series A 24, 24-33, 1978. · Zbl 0378.05006 · doi:10.1016/0097-3165(78)90042-0
[30] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics , Second Edition. Reading, Massachusetts: Addison-Wesley, 1994.
[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. · Zbl 1066.68031 · doi:10.1214/105051604000000611 · arxiv:math/0503738
[32] A. Gut, On the moment problem, Bernoulli 8, 407-421, 2002. · Zbl 1006.60016
[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. · Zbl 1008.68166 · doi:10.1137/S009753970138390X
[34] S. Janson, Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic processes and applications 110, 177-245, 2004. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[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. · Zbl 1063.60018 · doi:10.1007/978-3-0348-7915-6_24
[36] S. Janson, Random cutting and records in deterministic and random trees, Random Structures & Algorithms 29, 139-179, 2006. · Zbl 1120.05083 · doi:10.1002/rsa.20086
[37] S. Janson, Limit theorems for triangular urn schemes, Probability Theory and Related Fields 134 , 417-452, 2005. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7
[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. · Zbl 1358.60015 · www.dmtcs.org
[39] S. Janson, Moments of Gamma type and the Brownian supremum process area, Probability Surveys , 7, 1-52, 2010. · Zbl 1194.60019 · doi:10.1214/10-PS160 · eudml:227681 · arxiv:1002.4135
[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. · Zbl 1230.05100 · doi:10.1016/j.jcta.2009.11.006 · arxiv:0805.4084
[41] N. L. Johnson, S. Kotz and A. W. Kemp, Univariate Discrete Distributions , 2. Edition, New York, John Wiley, 1992.
[42] D. Karlis and E. Xekalaki, Mixed Poisson Distributions, International Statistical Review 73, 35-58, 2005. · Zbl 1104.62010 · doi:10.1111/j.1751-5823.2005.tb00250.x
[43] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching , second edition, Addison-Wesley, Reading, 1998.
[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. · Zbl 0879.05004 · doi:10.4213/rm958
[45] A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics 14, 1266-1274, 1966. · Zbl 0201.50204 · doi:10.1137/0114101
[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. · Zbl 1080.05019 · emis:journals/EJC/Volume_13/Abstracts/v13i1r8.html · eudml:125517
[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. · Zbl 1190.05046 · www.dmtcs.org
[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. · Zbl 1116.05020 · doi:10.1016/j.jcta.2006.08.003
[50] M. Kuba and A. Panholzer, Isolating nodes in recursive trees, Aequationes Mathematicae 76, 258-280, 2008. · Zbl 1180.05031 · doi:10.1007/s00010-008-2929-7
[51] M. Kuba and A. Panholzer, Analysis of statistics for generalized Stirling permutations, Combinatorics, Probability and Computing 20, 875-910, 2011. · Zbl 1233.05014 · doi:10.1017/S0963548311000381
[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. · Zbl 1296.60013 · www.dmtcs.org · arxiv:1110.2425
[53] M. Kuba and A. Panholzer, Limiting distributions for a class of diminishing urn models, Advances in Applied Probability 44, 1-31, 2012. · Zbl 1300.60023 · doi:10.1239/aap/1331216646 · arxiv:1403.2712
[54] M. Kuba and A. Panholzer, Isolating nodes in recursive trees, Online Journal of Analytic Combinatorics 9, 2014, 26 pages. · Zbl 1180.05031 · doi:10.1007/s00010-008-2929-7
[55] M. Loève, Probability Theory I , 4th Edition, Springer-Verlag, New York, 1977.
[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. · Zbl 0738.05034 · doi:10.1214/aoap/1177005874
[57] A. Meir and J. W. Moon, Cutting down random trees, Journal of the Australian Mathematical Society 11, 313-324, 1970. · Zbl 0196.27602 · doi:10.1017/S1446788700006698
[58] A. Meir and J. W. Moon, Cutting down recursive trees, Mathematical Biosciences 21, 173-181, 1974. · Zbl 0288.05102 · doi:10.1016/0025-5564(74)90013-3
[59] J. C. Massé, and R. Theodorescu, Neyman type A distribution revisited, Statistica Neerlandica , Volume 59, Issue 2, 206-213, 2005. · Zbl 1085.62010 · doi:10.1111/j.1467-9574.2005.00287.x
[60] J. Neyman, On a new class of “contagious” distributions applicable in entomology and bacteriology, Annals of Mathematical Statistics 10, 35-57, 1939. · Zbl 0020.38203 · doi:10.1214/aoms/1177732245
[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. · Zbl 1073.60503 · emis:journals/DMTCS/proceedings/html/dmAC0125.abs.html
[62] A. Panholzer, Cutting down very simple trees, Quaestiones Mathematicae 29, 211-228, 2006. · Zbl 1120.05020 · doi:10.2989/16073600609486160
[63] A. Panholzer and H. Prodinger, The level of nodes in increasing trees revisited, Random Structures & Algorithms 31, 203-226, 2007. · Zbl 1131.05029 · doi:10.1002/rsa.20161
[64] A. Panholzer and G. Seitz, Limiting distributions for the number of inversions in labelled tree families, Annals of Combinatorics 16, 847-870, 2012. · Zbl 1256.05050 · doi:10.1007/s00026-012-0164-3 · arxiv:1101.4790
[65] A. Panholzer and G. Seitz, Ancestors and descendants in evolving \(k\)-tree models, Random Structures & Algorithms 44, 465-489, 2014. · Zbl 1296.05177 · doi:10.1002/rsa.20474
[66] S. K. Park, The \(r\)-multipermutations, Journal of Combinatorial Theory, Series A 67, 44-71, 1994. · Zbl 0804.05001 · doi:10.1016/0097-3165(94)90003-5
[67] S. K. Park, Inverse descents of \(r\)-multipermutations, Discrete Mathematics 132, 215-229, 1994. · Zbl 0809.05001 · doi:10.1016/0012-365X(94)90239-9
[68] S. K. Park, \(P\)-partitions and \(q\)-Stirling numbers, Journal of Combinatorial Theory, Series A 68, 33-52, 1994. · Zbl 0809.05006 · doi:10.1016/0097-3165(94)90090-6
[69] J. Pitman, Exchangeable and partially exchangeable random partitions, Probab. Theory Relat. Fields 102, 145-158, 1995. · Zbl 0821.60047 · doi:10.1007/BF01213386
[70] N. Pouyanne, An algebraic approach to Pólya processes, Annales de l’Institut Henri Poincaré 44, 293-323, 2008. · Zbl 1185.60029 · doi:10.1214/07-AIHP130 · eudml:77971 · arxiv:math/0605472
[71] N. Privault, Generalized Bell polynomials and the combinatorics of Poisson central moments, Electronic Journal of Combinatorics 18, Paper 54, 2011. · Zbl 1215.11017 · emis:journals/EJC/Volume_18/Abstracts/v18i1p54.html · eudml:224135
[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. · Zbl 1088.05024 · doi:10.1016/j.jmaa.2005.05.004
[75] Eric W. Weisstein, “Stirling Transform”, From MathWorld-A Wolfram Web Resource. · mathworld.wolfram.com
[76] H. S. Wilf, Generatingfunctionology , Second Edition, Academic Press, 1992.
[77] G. Willmot, Mixed compound Poisson distributions, ASTIN Bulletin 16, 59-80, 1986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.