zbMATH — the first resource for mathematics

On martingale tail sums in affine two-color urn models with multiple drawings. (English) Zbl 1397.60066
Summary: In [“Two-colour balanced affine urn models with multiple drawings. I: Central limit theorems”, Preprint, arXiv:1503.09069; “Two-color balanced affine urn models with multiple drawings. II: Large-index and triangular urns”’, Preprint, arXiv:1509.09053], M. Kuba and H. M. Mahmoud introduced the family of two-color affine balanced Pólya urn schemes with multiple drawings. We show that, in large-index urns (urn index between \(\frac 12\) and 1) and triangular urns, the martingale tail sum for the number of balls of a given color admits both a Gaussian central limit theorem as well as a law of the iterated logarithm. The laws of the iterated logarithm are new, even in the standard model when only one ball is drawn from the urn in each step (except for the classical Pólya urn model). Finally, we prove that the martingale limits exhibit densities (bounded under suitable assumptions) and exponentially decaying tails. Applications are given in the context of node degrees in random linear recursive trees and random circuits.

60F15 Strong limit theorems
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
60G42 Martingales with discrete parameter
Full Text: DOI arXiv
[1] Athreya, K. B.; Karlin, S., Embedding of urn schemes into continuous time Markov branching processes and related limit theorems, Ann. Math. Statist., 39, 1801-1817, (1968) · Zbl 0185.46103
[2] Bagchi, A.; Pal, A. K., Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures, SIAM J. Algebraic Discrete Math., 6, 394-405, (1985) · Zbl 0568.60010
[3] Bai, Z. D.; Hu, F.; Zhang, L.-X., Gaussian approximation theorems for urn models and their applications, Ann. Appl. Prob., 12, 1149-1173, (2002) · Zbl 1014.60025
[4] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[5] Chauvin, B.; Pouyanne, N.; Sahnoun, R., Limit distributions for large Pólya urns, Ann. Appl. Prob., 21, 1-32, (2011) · Zbl 1220.60006
[6] Chauvin, B.; Pouyanne, N.; Mailler, C., Smoothing equations for large Pólya urns, J. Theoret. Prob., 28, 923-957, (2015) · Zbl 1358.60010
[7] Chen, M.-R.; Wei, C.-Z., A new urn model, J. Appl. Prob., 42, 964-976, (2015) · Zbl 1093.60007
[8] Chen, M.-R.; Kuba, M., On generalized Pólya urn models, J. Appl. Prob., 50, 1169-1186, (2013) · Zbl 1290.60009
[9] Chung, F.; Lu, L., Concentration inequalities and martingale inequalities: a survey, Internet Math., 3, 79-127, (2006) · Zbl 1111.60010
[10] Devroye, L.; Janson, S., Long and short paths in uniform random recursive dags, Ark. Mat., 49, 61-77, (2011) · Zbl 1230.60092
[11] Diaz, J.; Serna, M. J.; Spirakis, P.; Toran, J.; Tsukiji, T., On the expected depth of Boolean circuits, (1994)
[12] Flajolet, P.; Dumas, P.; Puyhaubert, V., Proceedings of Fourth Colloquium on Mathematics and Computer Science, AG, Some exactly solvable models of urn process theory, 59-118, (2006), DMTCS: DMTCS, Nancy · Zbl 1193.60011
[13] Flajolet, P.; Gabarró, J.; Pekari, H., Analytic urns, Ann. Prob., 33, 1200-1233, (2005) · Zbl 1073.60007
[14] Freedman, D. A., Bernard Friedman’s urn, Ann. Math. Statist., 36, 965-970, (1965) · Zbl 0138.12003
[15] Fuchs, M., A note on the quicksort asymptotics, Random Structures Algorithms, 46, 677-687, (2015) · Zbl 1332.68039
[16] Gouet, R., Martingale functional central limit theorems for a generalized Pólya urn, Ann. Prob., 21, 1624-1639, (1993) · Zbl 0788.60044
[17] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics, (1994), Addison-Wesley: Addison-Wesley, Reading · Zbl 0836.00001
[18] Grübel, R.; Kabluchko, Z., A functional central limit theorem for branching random walks, almost sure weak convergence, and applications to random trees, Ann. Appl. Prob., 26, 3659-3698, (2016) · Zbl 1367.60028
[19] Hall, P., The convergence of moments in the martingale central limit theorem, Z. Wahrsch. Verw. Gebiete, 44, 253-260, (1978) · Zbl 0369.60026
[20] Hall, P.; Heyde, C. C., Martingale Limit Theory and Its Application, (1980), Academic Press: Academic Press, New York · Zbl 0462.60045
[21] Heyde, C. C., On central limit and iterated logarithm supplements to the martingale convergence theorem, J. Appl. Prob., 14, 758-775, (1977) · Zbl 0385.60033
[22] Janson, S., Functional limit theorems for multitype branching processes and generalized Pólya urns, Stoch. Process. Appl., 110, 177-245, (2004) · Zbl 1075.60109
[23] Janson, S., Limit theorems for triangular urn schemes, Prob. Theory Relat. Fields, 134, 417-452, (2006) · Zbl 1112.60012
[24] Janson, S., Moments of Gamma type and the Brownian supremum process area, Prob. Surveys, 7, 1-52, (2010) · Zbl 1194.60019
[25] Johnson, N. L.; Kotz, S., Urn Models and Their Application, (1977), John Wiley: John Wiley, New York
[26] Johnson, N. L.; Kotz, S.; Mahmoud, H., Pólya-type urn models with multiple drawings, J. Iran. Statist. Soc., 3, 165-173, (2004) · Zbl 06657086
[27] Knape, M.; Neininger, R., Pólya urns via the contraction method, Combin. Prob. Comput., 23, 1148-1186, (2014) · Zbl 1301.60012
[28] Konzem, S.; Mahmoud, H., Characterization and enumeration of certain classes of tenable Pólya urns grown by drawing multisets of balls, Methodol. Comput. Appl. Prob., 18, 359-375, (2016) · Zbl 1339.05007
[29] Kuba, M.; Mahmoud, H.; Panholzer, A., Analysis of a generalized Friedman’s urn with multiple drawings, Discrete Appl. Math., 161, 2968-2984, (2013) · Zbl 1292.60012
[30] Kuba, M.; Mahmoud, H., On urn models with multiple drawings I: urns with a small index, (2015)
[31] Kuba, M.; Mahmoud, H., On urn models with multiple drawings II: large-index and triangular urns, (2015)
[32] Mahmoud, H., Pólya Urn Models, (2008), Chapman and Hall: Chapman and Hall, Orlando · Zbl 1149.60005
[33] Mahmoud, H., Drawing multisets of balls from tenable balanced linear urns, Prob. Eng. Inf. Sci., 27, 147-162, (2013) · Zbl 1275.60015
[34] Mahmoud, H., The degree profile in some classes of random graphs that generalize recursive trees, Methodol. Comput. Appl. Prob., 16, 527-538, (2014) · Zbl 1315.60012
[35] Moler, J.; Plo, F.; Urmeneta, H., A generalized Pólya urn and limit laws for the number of outputs in a family of random circuits, TEST, 22, 46-61, (2013) · Zbl 1262.60025
[36] Móri, T., The maximum degree of the Barabási-Albert random tree, Combin. Prob. Comput., 14, 339-348, (2005) · Zbl 1078.05077
[37] Neininger, R., Refined quicksort asymptotics, Random Structures Algorithms, 46, 346-361, (2015) · Zbl 1327.68086
[38] Peköz, E. A.; Röllin, A.; Ross, N., Degree asymptotics with rates for preferential attachment random graphs, Ann. Appl. Prob., 23, 1188-1218, (2013) · Zbl 1271.60019
[39] Pouyanne, N., An algebraic approach to Pólya processes, Ann. Inst. H. Poincaré Prob. Statist., 44, 293-323, (2008) · Zbl 1185.60029
[40] Renlund, H., Generalized Pólya urns via stochastic approximation, (2010)
[41] Rónyi, A.; Róvósz, P., On mixing sequences of random variables, Acta Math. Acad. Sci. H., 9, 389-393, (1958) · Zbl 0104.36301
[42] Sulzbach, H., On martingale tail sums for the path length in random trees, Random Structures Algorithms, (2016)
[43] Tsukiji, T.; Xhafa, F., Algorithms—ESA ’96, 1136, On the depth of randomly generated circuits, 208-220, (1996), Springer: Springer, Berlin · Zbl 1379.68182
[44] Tsukiji, T.; Mahmoud, H., A limit law for outputs in random circuits, Algorithmica, 31, 403-412, (2001) · Zbl 0989.68107
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.