×

Pólya urns via the contraction method. (English) Zbl 1301.60012

Summary: We propose an approach to analysing the asymptotic behaviour of Pólya urns based on the contraction method. For this, a new combinatorial discrete-time embedding of the evolution of the urn into random rooted trees is developed. A decomposition of these trees leads to a system of recursive distributional equations which capture the distributions of the numbers of balls of each colour. Ideas from the contraction method are used to study such systems of recursive distributional equations asymptotically. We apply our approach to a couple of concrete Pólya urns that lead to limit laws with normal limit distributions, with non-normal limit distributions and with asymptotic periodic distributional behaviour.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
60J05 Discrete-time Markov processes on general state spaces
68Q25 Analysis of algorithms and problem complexity

References:

[1] Flournoy, Adaptive Designs pp 13– (1995)
[2] DOI: 10.1080/01621459.1978.10480109 · doi:10.1080/01621459.1978.10480109
[3] RAIRO Inform. Théor. Appl. 25 pp 85– (1991)
[4] DOI: 10.2307/1428133 · Zbl 0829.60094 · doi:10.2307/1428133
[5] DOI: 10.1214/07-AIHP130 · Zbl 1185.60029 · doi:10.1214/07-AIHP130
[6] 2005 International Conference on Analysis of Algorithms, DMTCS Proc. AD pp 275– (2005)
[7] DOI: 10.1214/10-PS160 · Zbl 1194.60019 · doi:10.1214/10-PS160
[8] Alea 1 pp 347– (2006)
[9] Probab. Theory Rel. Fields 134 pp 417– (2005)
[10] DOI: 10.1016/j.spa.2003.12.002 · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[11] DOI: 10.1214/aop/1176993441 · Zbl 0544.60022 · doi:10.1214/aop/1176993441
[12] DOI: 10.1137/S009753970138390X · Zbl 1008.68166 · doi:10.1137/S009753970138390X
[13] Ann. IHP. 50 pp 628– (2014)
[14] DOI: 10.1214/009117905000000026 · Zbl 1073.60007 · doi:10.1214/009117905000000026
[15] 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms: AofA’12, DMTCS Proc. AQ pp 191– (2012)
[16] DOI: 10.1214/aos/1176345637 · Zbl 0449.62034 · doi:10.1214/aos/1176345637
[17] DOI: 10.1214/07-AAP457 · Zbl 1143.68019 · doi:10.1214/07-AAP457
[18] DOI: 10.1214/aoap/1037125857 · Zbl 1014.60025 · doi:10.1214/aoap/1037125857
[19] DOI: 10.1214/10-AAP696 · Zbl 1220.60006 · doi:10.1214/10-AAP696
[20] DOI: 10.1016/S0304-4149(98)00094-5 · Zbl 0954.62014 · doi:10.1016/S0304-4149(98)00094-5
[21] Teor. Veroyatnost. i Primenen. 22 pp 449– (1977)
[22] DOI: 10.1137/0606041 · Zbl 0568.60010 · doi:10.1137/0606041
[23] DOI: 10.1214/aoms/1177698013 · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[24] Studia Sci. Math. Hungar. 4 pp 31– (1969)
[25] DOI: 10.1214/aoap/1075828056 · Zbl 1041.60024 · doi:10.1214/aoap/1075828056
[26] DOI: 10.1002/rsa.10010 · Zbl 0990.68054 · doi:10.1002/rsa.10010
[27] DOI: 10.1016/S0167-7152(97)00018-7 · Zbl 0946.62074 · doi:10.1016/S0167-7152(97)00018-7
[28] Pólya Urn Models (2009)
[29] DOI: 10.1016/S0167-7152(00)00045-6 · Zbl 0965.60027 · doi:10.1016/S0167-7152(00)00045-6
[30] DOI: 10.1007/s00440-007-0110-1 · Zbl 1158.60044 · doi:10.1007/s00440-007-0110-1
[31] Teor. Veroyatnost. i Primenen. 21 pp 741– (1976)
[32] DOI: 10.1080/01621459.1990.10475319 · doi:10.1080/01621459.1990.10475319
[33] DOI: 10.1016/S0304-4149(96)00094-4 · Zbl 0889.60013 · doi:10.1016/S0304-4149(96)00094-4
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.