Pólya urns via the contraction method

DOI10.1017/S0963548314000364arXiv1301.3404MaRDI QIDQ2929861FDOQ2929861

Authors: Margarete Knape, Ralph Neininger 

Publication date: 14 November 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We propose an approach to analyze the asymptotic behavior of P'olya 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'olya urns that lead to limit laws with normal limit distributions, with non-normal limit distributions and with asymptotic periodic distributional behavior.

Full work available at URL: https://arxiv.org/abs/1301.3404

Recommendations

• Fully analyzing an algebraic Pólya urn model
• Limit distributions for large Pólya urns
• Pólya urn models and connections to random trees: a review
• Rates of convergence for balanced irreducible two-color Pólya urns
• A.s. convergence for infinite colour Pólya urns associated with random walks

Mathematics Subject Classification ID

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

Cites Work

• Some asymptotic theory for the bootstrap
• A general limit theorem for recursive algorithms and combinatorial structures
• On a multivariate contraction method for random recursive structures with applications to quicksort
• Probability metrics and recursive algorithms
• Limit distributions for large Pólya urns
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
• Central limit theorems for urn models
• Analytic urns
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Gaussian approximation theorems for urn models and their applications
• An algebraic approach to Pólya processes
• Moments of gamma type and the Brownian supremum process area
• Asymptotic theorems for urn models with nonhomogeneous generating matrices
• A functional limit theorem for the profile of search trees
• The size of random fragmentation trees
• On generalized Pólya urn models
• Limit theorems for certain branching random walks on compact groups and homogeneous spaces
• Variance in randomized play-the-winner clinical trials

Cited In (24)

• Refined asymptotics for the composition of cyclic urns
• Nonlinear randomized urn models: a stochastic approximation viewpoint
• Absolute continuity of complex martingales and of solutions to complex smoothing equations
• Two-color balanced affine urn models with multiple drawings
• Solutions to complex smoothing equations
• Exactly solvable balanced tenable urns with random entries via the analytic methodology
• An asymptotic distribution theory for Eulerian recurrences with applications
• Random additions in urns of integers
• Title not available (Why is that?)
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Models induced from critical birth-death process with random initial conditions
• On martingale tail sums in affine two-color urn models with multiple drawings
• On densities for solutions to stochastic fixed point equations
• Pólya urn models and connections to random trees: a review
• The fixed points of the multivariate smoothing transform
• Dependence and phase changes in random \(m\)-ary search trees
• Generalized gamma approximation with rates for urns, walks and trees
• Broadcasting on random recursive trees
• Balanced multicolour Pólya urns via smoothing systems analysis
• Fully analyzing an algebraic Pólya urn model
• The size of random bucket trees via urn models
• Periodic Pólya urns, the density method and asymptotics of Young tableaux
• Smoothing equations for large Pólya urns
• Pólya urns with immigration at random times

This page was built for publication: Pólya urns via the contraction method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929861)