ALCOMFT-TR-03-16

Philippe Flajolet, Joaquim Gabarr\'o and Helmut Pekari
Analytic Urns
Barcelona and INRIA. Work package 4. July 2003.

Abstract: This article describes a purely analytic approach to urn models of the generalized or extended P\'olya-Eggenberger type, in the case of two types of balls and constant ``balance'', i.e., constant row sum. (Under such models, an urn may contain balls of either of two colours and a fixed 2x2-matrix determines the replacement policy when a ball is drawn and its colour is observed.) 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 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 limits, 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, are shown to admit of explicit representations in terms of Weierstra\ss elliptic functions. Other consequences include a unification of earlier studies of these models and the detection of stable laws in certain classes of urns with an off-diagonal entry equal to zero.

Postscript file: ALCOMFT-TR-03-16.ps.gz (438 kb).