Analytic urns
By Philippe Flajolet, Joaquim Gabarró, Helmut Pekari. 2004
98 citations recorded by the source corpus.
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.
Subfields: Condensed Matter Physics, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/7795f191422fa80da8bbf57d74043b8e77e650a5
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Condensed Matter Physics
In Discrete Mathematics and Combinatorics
In Mathematical Physics
Citations in the corpus
- Functional limit theorems for multitype branching processes and generalized Pólya urns (2004, unknown): “1”
- A survey of random processes with reinforcement (2006, methodology): “ random recursive trees, and [Mah98] for a tree application of a three-color balanced urn. Exact solutions to two-color balanced urns exhibit involve number theoretic phenomena which are described in [FGP05]. Without the assumption of balance, results on triangular urns date back at least to [DV97].”