Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Classification of la ...
Conference paper

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

Nicolas Pouyanne (1)
(1) Laboratoire de Mathématiques de Versailles
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Proceedings
DOI
10.46298/dmtcs.3384
License
https://about.hal.science/hal-authorisation-v1
Indicators
558
Views
414
Downloads

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

Nicolas Pouyanne (1)
(1) Laboratoire de Mathématiques de Versailles
Abstract
This article deals with Pólya generalized urn models with constant balance in any dimension. It is based on the algebraic approach of Pouyanne (2005) 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 \geq 27$.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • urn experiments
  • $m$-ary search trees
Cited by

Source: OpenCitations

  • On densities for solutions to stochastic fixed point equations

    arXiv (Cornell University)

    Authors : Kevin Leckey ORCID

    Journal reference : Volume 54, 2018, pp. 528-558

    DOI : 10.1002/rsa.20799

  • Limit distributions for multitype branching processes of $m$-ary search trees

    Authors : Brigitte Chauvin, Quansheng Liu ORCID, Nicolas Pouyanne

    Journal reference : Volume 50, 2014, pp.

    DOI : 10.1214/12-aihp518

  • Refined asymptotics for the composition of cyclic urns

    Electronic Journal of Probability

    Authors : Noela Müller ORCID, Ralph Neininger ORCID

    Journal reference : Volume 23, 2018, pp.

    DOI : 10.1214/18-ejp243

  • Analysis of a class of Cannibal urns

    Electronic Communications in Probability

    Authors : Markus Kuba ORCID

    Journal reference : Volume 16, 2011, pp.

    DOI : 10.1214/ecp.v16-1669

  • Solutions to complex smoothing equations

    Probability Theory and Related Fields

    Authors : Matthias Meiners ORCID, Sebastian Mentemeier ORCID

    Journal reference : Volume 168, 2016, pp. 199-268

    DOI : 10.1007/s00440-016-0709-1

  • Arbres pour l’Algorithmique

    Authors : Brigitte Chauvin, Julien Clément ORCID, Danièle Gardy ORCID

    Journal reference : Volume , 2018, pp.

    DOI : 10.1007/978-3-319-93725-0
Preview
Loading PDF preview...