×
Müller, Noela; Neininger, Ralph

Refined asymptotics for the composition of cyclic urns. (English) Zbl 1406.60043

Electron. J. Probab. 23, Paper No. 117, 20 p. (2018).
Summary: A cyclic urn is an urn model for balls of types \(0,\dots ,m-1\). The urn starts at time zero with an initial configuration. Then, in each time step, first a ball is drawn from the urn uniformly and independently from the past. If its type is \(j\), it is then returned to the urn together with a new ball of type \(j+1 \mod m\). The case \(m=2\) is the well-known Friedman urn. The composition vector, i.e., the vector of the numbers of balls of each type after \(n\) steps is, after normalization, known to be asymptotically normal for \(2\leq m\leq 6\). For \(m\geq 7\) the normalized composition vector is known not to converge. However, there is an almost sure approximation by a periodic random vector.
In the present paper the asymptotic fluctuations around this periodic random vector are identified. We show that these fluctuations are asymptotically normal for all \(7\leq m\leq 12\). For \(m\geq 13\) we also find asymptotically normal fluctuations when normalizing in a more refined way. These fluctuations are of maximal dimension \(m-1\) only when \(6\) does not divide \(m\). For \(m\) being a multiple of \(6\) the fluctuations are supported by a two-dimensional subspace.

MSC:

60F05 Central limit and other weak theorems
60F15 Strong limit theorems
60C05 Combinatorial probability
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Keywords:

Pólya urn; cyclic urn; cyclic group; periodicities; weak convergence; CLT analogue; probability metric; Zolotarev metric
Cite Review PDF
Full Text: DOI arXiv Euclid

References:

[1] Bindjeme, P. and Fill, J. A. (2012) Exact \(L^2\)-Distance from the Limit for QuickSort Key Comparisons (Extended abstract). DMTCS proc.AQ, 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’12), 339-348. · Zbl 1296.68039
[2] Chauvin, B., Mailler, C. and Pouyanne, N. (2015) Smoothing equations for large Pólya urns. J. Theor. Probab.28, 923-957. · Zbl 1358.60010 · doi:10.1007/s10959-013-0530-z
[3] Chern, H.-H., Fuchs, M. and Hwang, H.-K. (2007) Phase changes in random point quadtrees. ACM Trans. Algorithms3, Art. 12, 51 pp. · Zbl 1321.68218
[4] Chern, H.-H. and Hwang, H.-K. (2001) Phase changes in random \(m\)-ary search trees and generalized quicksort. Random Structures Algorithms19, 316-358. · Zbl 0990.68052
[5] Drmota, M., Janson, S. and Neininger, R. (2008) A functional limit theorem for the profile of search trees. Ann. Appl. Probab.18, 288-333. · Zbl 1143.68019 · doi:10.1214/07-AAP457
[6] Evans, S.N., Grübel, R. and Wakolbinger, A. (2012) Trickle-down processes and their boundaries. Electron. J. Probab.17, 1-58. · Zbl 1246.60100 · doi:10.1214/EJP.v17-1698
[7] Freedman, D. A. (1965) Bernard Friedman’s Urn. Ann. Math. Statist.36, no. 3, 956-970. · Zbl 0138.12003 · doi:10.1214/aoms/1177700068
[8] Grübel, R. (2014) Search trees: Metric aspects and strong limit theorems. Ann. Appl. Probab.24, 1269-1297. · Zbl 1294.60009 · doi:10.1214/13-AAP948
[9] Janson, S. (1983) Limit theorems for certain branching random walks on compact groups and homogeneous spaces. Ann. Probab.11, 909-930. · Zbl 0544.60022 · doi:10.1214/aop/1176993441
[10] Janson, S. (2004) Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl.110, 177-245. · Zbl 1075.60109
[11] Janson, S. (2006) Congruence properties of depths in some random trees. Alea1, 347-366. · Zbl 1104.60300
[12] Knape, M. and Neininger, R. (2014) Pólya Urns Via the Contraction Method. Combin. Probab. Comput.23, 1148-1186. · Zbl 1301.60012 · doi:10.1017/S0963548314000364
[13] Mahmoud, H. M. (1992) Evolution of Random Search Trees, John Wiley & Sons, New York. · Zbl 0762.68033
[14] Mailler, C. (2018) Balanced multicolour Pólya urns via smoothing systems analysis. ALEA - Latin American Journal of Probability and Mathematical StatisticsXV, 375-408. · Zbl 1390.60115 · doi:10.30757/ALEA.v15-16
[15] Müller, N. S. and Neininger, R. (2016) The CLT Analogue for Cyclic Urns. Analytic Algorithmics and Combinatorics (ANALCO), 121-127. · Zbl 1433.05282
[16] Neininger, R. (2015) Refined Quicksort asymptotics. Random Structures Algorithms46, 346-361. · Zbl 1327.68086 · doi:10.1002/rsa.20497
[17] Neininger, R. and Rüschendorf, L. (2004) A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab.14, 378-418. · Zbl 1041.60024 · doi:10.1214/aoap/1075828056
[18] Pouyanne, N. (2005) Classification of large Pólya-Eggenberger urns with regard to their asymptotics. 2005 International Conference on Analysis of Algorithms, 275-285 (electronic), Discrete Math. Theor. Comput. Sci. Proc., AD, Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1096.60007
[19] Pouyanne, N. (2008) An algebraic approach to Pólya processes. Ann. Inst. Henri Poincaré Probab. Stat.44, 293-323. · Zbl 1185.60029
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.