Analytic urns

Abstract

This article describes a purely analytic approach to urn models of the generalized or extended Pólya-Eggenberger type, in the case of two types of balls and constant ``balance,'' that is, constant row sum. The treatment starts from a quasilinear first-order partial differential equation associated with a combinatorial renormalization of the model and bases itself on elementary conformal mapping arguments coupled with singularity analysis techniques. Probabilistic consequences in the case of ``subtractive'' urns are new representations for the probability distribution of the urn's composition at any time n, structural information on the shape of moments of all orders, estimates of the speed of convergence to the Gaussian limit and an explicit determination of the associated large deviation function. In the general case, analytic solutions involve Abelian integrals over the Fermat curve x^h+y^h=1. Several urn models, including a classical one associated with balanced trees (2-3 trees and fringe-balanced search trees) and related to a previous study of Panholzer and Prodinger, as well as all urns of balance 1 or 2 and a sporadic urn of balance 3, are shown to admit of explicit representations in terms of Weierstraßelliptic functions: these elliptic models appear precisely to correspond to regular tessellations of the Euclidean plane.

Published at http://dx.doi.org/10.1214/009117905000000026 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (30)

• A survey of random processes with reinforcement
• Limit distributions for large Pólya urns
• Polya urns via the contraction method
• An algebraic approach to Polya processes
• Generalized gamma approximation with rates for urns, walks and trees
• Analysis of some exactly solvable diminishing urn models
• Large deviations for Generalized Polya Urns with arbitrary urn function
• First Passage Properties of the Polya Urn Process
• Two-color balanced affine urn models with multiple drawings II: large-index and triangular urns
• Mean and variance of balanced Pólya urns
• The simple harmonic urn
• Random Polymers and Generalized Urn Processes
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux
• Sharp large deviations and concentration inequalities for the number of descents in a random permutation
• The projective translation equation and rational plane flows. I
• The projective translation equation and unramified 2-dimensional flows with rational vector fields
• Periodic Pólya urns and an application to Young tableaux
• On Sampling without replacement and OK-Corral urn models
• On death processes and urn models
• Urn models with two types of strategies
• On moment sequences and mixed Poisson distributions
• Exchangeable Gibbs partitions and Stirling triangles
• Combinatorial families of multilabelled increasing trees and hook-length formulas
• Algebraic and abelian solutions to the projective translation equation
• Smoothing equations for large Pólya urns
• Pólya urns with immigration at random times
• A Semiring Structure for Generalised Pólya Urns
• Friedman vs Pólya
• Generalized extreme shock models with a possibly increasing threshold