DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Classification of large Pólya-Eggenberger urns with regard to their asymptotics

Nicolas Pouyanne


This article deals with Pólya generalized urn models with constant balance in any dimension. It is based on the algebraic approach of [AlgApproach] and classifies urns having ``large'' eigenvalues in five classes, depending on their almost sure asymptotics. These classes are described in terms of the spectrum of the urn's replacement matrix and examples of each case are treated. We study the cases of so-called cyclic urns in any dimension and m-ary search trees for m ≥ 27.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional