Fully analyzing an algebraic Pólya urn model

DOI10.1007/978-3-642-29344-3_48zbMATH Open1354.05008arXiv1203.4917OpenAlexW2134347029MaRDI QIDQ2894499FDOQ2894499

Authors: Basile Morcrette 

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Abstract: This paper introduces and analyzes a particular class of Polya urns: balls are of two colors, can only be added (the urns are said to be additive) and at every step the same constant number of balls is added, thus only the color compositions varies (the urns are said to be balanced). These properties make this class of urns ideally suited for analysis from an "analytic combinatorics" point-of-view, following in the footsteps of Flajolet-Dumas-Puyhaubert, 2006. Through an algebraic generating function to which we apply a multiple coalescing saddle-point method, we are able to give precise asymptotic results for the probability distribution of the composition of the urn, as well as local limit law and large deviation bounds.

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

Recommendations

• Limit distributions for large Pólya urns
• POLYA URN MODELS UNDER GENERAL REPLACEMENT SCHEMES
• Pólya urns via the contraction method
• Analytic urns
• Exactly solvable balanced tenable urns with random entries via the analytic methodology

zbMATH Keywords

large deviationsanalytic combinatoricsGaussian local limit lawmultiple coalescing saddle-point methodPólya urn models

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05)

Cited In (19)

• Occupancy urn models in the analysis of algorithms
• The necklace process: a generating function approach
• Exactly solvable balanced tenable urns with random entries via the analytic methodology
• Analysis of a class of cannibal urns
• On the algebraic numbers computable by some generalized Ehrenfest urns
• Some exactly solvable models of urn process theory
• Azuma-Hoeffding bounds for a class of urn models
• Multiple drawing multi-colour urns by stochastic approximation
• Pólya urns via the contraction method
• An algebraic approach to Pólya processes
• Analytic urns
• Balanced multicolour Pólya urns via smoothing systems analysis
• Preferential attachment when stable
• Classification of large Pólya-Eggenberger urns with regard to their asymptotics
• Periodic Pólya urns, the density method and asymptotics of Young tableaux
• Mean and variance of balanced Pólya urns
• Urn models and differential algebraic equations
• Pólya urns with immigration at random times
• Formulae and asymptotics for coefficients of algebraic functions

This page was built for publication: Fully analyzing an algebraic Pólya urn model

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