Polya urns via the contraction method

Abstract

We propose an approach to analyze the asymptotic behavior 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 color. 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 behavior.

minor revision; accepted for publication in Combinatorics, Probability & Computing (Special issue dedicated to the memory of Philippe Flajolet)

References in corpus (7)

• Analytic urns
• A functional limit theorem for the profile of search trees
• Polya urns via the contraction method
• On a functional contraction method
• Congruence properties of depths in some random trees
• Smoothing equations for large Pólya urns
• The space requirement of m-ary search trees: distributional asymptotics for m >= 27

Cited by in corpus (13)

• Polya urns via the contraction method
• The Fixed Points of the Multivariate Smoothing Transform
• Classification of urn models with multiple drawings
• An asymptotic distribution theory for Eulerian recurrences with applications
• Periodic Pólya urns and an application to Young tableaux
• Analysis of radix selection on Markov sources
• Central limit theorem analogues for multicolour urn models
• Solutions to complex smoothing equations
• Smoothing equations for large Pólya urns
• Dependence and phase changes in random $m$-ary search trees
• Pólya urns with immigration at random times
• Random Fixed Points, Limits and Systemic risk
• Random Additions in Urns of Integers