{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T19:57:18Z","timestamp":1715630238649},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2014,9,1]],"date-time":"2014-09-01T00:00:00Z","timestamp":1409529600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,11]]},"abstract":"We propose an approach to analysing the asymptotic behaviour of P\u00f3lya 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\u00f3lya urns that lead to limit laws with normal limit distributions, with non-normal limit distributions and with asymptotic periodic distributional behaviour.<\/jats:p>","DOI":"10.1017\/s0963548314000364","type":"journal-article","created":{"date-parts":[[2014,9,1]],"date-time":"2014-09-01T14:07:35Z","timestamp":1409580455000},"page":"1148-1186","source":"Crossref","is-referenced-by-count":21,"title":["P\u00f3lya Urns Via the Contraction Method"],"prefix":"10.1017","volume":"23","author":[{"given":"MARGARETE","family":"KNAPE","sequence":"first","affiliation":[]},{"given":"RALPH","family":"NEININGER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,9,1]]},"reference":[{"key":"S0963548314000364_ref13","doi-asserted-by":"publisher","DOI":"10.1214\/009117905000000026"},{"key":"S0963548314000364_ref1","first-page":"31","article-title":"On a characteristic property of P\u00f3lya'surn","volume":"4","author":"Athreya","year":"1969","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548314000364_ref18","first-page":"347","article-title":"Congruence properties of depths in some random trees","volume":"1","author":"Janson","year":"2006","journal-title":"Alea"},{"key":"S0963548314000364_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(97)00018-7"},{"key":"S0963548314000364_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP696"},{"key":"S0963548314000364_ref26","volume-title":"P\u00f3lya Urn Models","author":"Mahmoud","year":"2009"},{"key":"S0963548314000364_ref29","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1214\/aoap\/1075828056","article-title":"A general limit theorem for recursive algorithms and combinatorial structures","volume":"14","author":"Neininger","year":"2004","journal-title":"Ann. Appl. Probab."},{"key":"S0963548314000364_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(98)00094-5"},{"key":"S0963548314000364_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(00)00045-6"},{"key":"S0963548314000364_ref40","first-page":"449","article-title":"Ideal metrics in the problem of approximating the distributions of sums of independent random variables (Russian)","volume":"22","author":"Zolotarev","year":"1977","journal-title":"Teor. Veroyatnost. i Primenen."},{"key":"S0963548314000364_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0110-1"},{"key":"S0963548314000364_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993441"},{"key":"S0963548314000364_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/0606041"},{"key":"S0963548314000364_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10010"},{"key":"S0963548314000364_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138390X"},{"key":"S0963548314000364_ref39","first-page":"741","article-title":"Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces (Russian)","volume":"21","author":"Zolotarev","year":"1976","journal-title":"Teor. Veroyatnost. i Primenen."},{"key":"S0963548314000364_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0442-7"},{"key":"S0963548314000364_ref31","first-page":"275","article-title":"Classification of large P\u00f3lya\u2013Eggenberger urns with regard to their asymptotics","volume":"AD","author":"Pouyanne","year":"2005","journal-title":"2005 International Conference on Analysis of Algorithms, DMTCS Proc."},{"key":"S0963548314000364_ref12","unstructured":"Fill J. A. and Kapur N. (2004) The space requirement of m-ary search trees: Distributional asymptotics for m \u22db 27. Invited paper, Proc. 7th Iranian Statistical Conference, 2004. www.ams.jhu.edu\/~fill\/papers\/periodic.pdf"},{"key":"S0963548314000364_ref22","doi-asserted-by":"crossref","unstructured":"Johnson N. L. and Kotz S. (1977) Urn Models and their Application: An Approach to Modern Discrete Probability Theory, Wiley Series in Probability and Mathematical Statistics, Wiley.","DOI":"10.2307\/2530628"},{"key":"S0963548314000364_ref34","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1991250100851"},{"key":"S0963548314000364_ref7","first-page":"191","article-title":"Support and density of the limit m-ary search tree distribution","volume":"AQ","author":"Chauvin","year":"2012","journal-title":"23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms: AofA'12, DMTCS Proc."},{"key":"S0963548314000364_ref8","first-page":"628","article-title":"Limit distributions for multitype branching processes of m-ary search trees","volume":"50","author":"Chauvin","year":"2014","journal-title":"Ann. IHP."},{"key":"S0963548314000364_ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800027142"},{"key":"S0963548314000364_ref9","unstructured":"Chauvin B. , Mailler C. and Pouyanne N. (2013) Smoothing equations for large P\u00f3lya urns. arXiv:1302.1412"},{"key":"S0963548314000364_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/07-AIHP130"},{"key":"S0963548314000364_ref25","doi-asserted-by":"crossref","unstructured":"Leckey K. , Neininger R. and Szpankowski W. (2013) Towards more realistic probabilistic models for data structures: The external path length in tries under the Markov model. In Proc. ACM\u2013SIAM Symposium on Discrete Algorithms (SODA), pp. 877\u2013886.","DOI":"10.1137\/1.9781611973105.63"},{"key":"S0963548314000364_ref5","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1214\/aoap\/1037125857","article-title":"Gaussian approximation theorems for urn models and their applications","volume":"12","author":"Bai","year":"2002","journal-title":"Ann. Appl. Probab."},{"key":"S0963548314000364_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/10-PS160"},{"key":"S0963548314000364_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2003.12.002"},{"key":"S0963548314000364_ref20","unstructured":"Janson S. and Kaijser S. (2012) Higher moments of Banach space valued random variables. Mem. Amer. Math. Soc., to appear."},{"key":"S0963548314000364_ref23","unstructured":"Knape M. (2013) P\u00f3lya urns via the contraction method. PhD dissertation. Submitted at the J. W. Goethe University, Frankfurt am Main, April 2013. urn:nbn:de:hebis:30:3-322846"},{"key":"S0963548314000364_ref11","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP457"},{"key":"S0963548314000364_ref37","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1978.10480109"},{"key":"S0963548314000364_ref30","unstructured":"Neininger R. and Sulzbach H. (2012) On a functional contraction method. Ann. Probab., to appear. arXiv:1202.1370"},{"key":"S0963548314000364_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(96)00094-4"},{"key":"S0963548314000364_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698013"},{"key":"S0963548314000364_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345637"},{"key":"S0963548314000364_ref36","doi-asserted-by":"publisher","DOI":"10.1214\/lnms\/1215451474"},{"key":"S0963548314000364_ref38","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10475319"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T14:55:34Z","timestamp":1565794534000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000364\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,1]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["S0963548314000364"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000364","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,1]]}}}