2012 | OriginalPaper | Buchkapitel
Fully Analyzing an Algebraic Pólya Urn Model
verfasst von : Basile Morcrette
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper introduces and analyzes a particular class of Pólya 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 et al. [4]. 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.