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. Some exactly solvabl ...
Conference paper

Some exactly solvable models of urn process theory

Philippe Flajolet ORCID (1), Philippe Dumas ORCID (1), Vincent Puyhaubert (1)
(1) Algorithms
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3506
License
https://about.hal.science/hal-authorisation-v1
Indicators
994
Views
1168
Downloads

Some exactly solvable models of urn process theory

Philippe Flajolet ORCID (1), Philippe Dumas ORCID (1), Vincent Puyhaubert (1)
(1) Algorithms
Abstract
We establish a fundamental isomorphism between discrete-time balanced urn processes and certain ordinary differential systems, which are nonlinear, autonomous, and of a simple monomial form. As a consequence, all balanced urn processes with balls of two colours are proved to be analytically solvable in finite terms. The corresponding generating functions are expressed in terms of certain Abelian integrals over curves of the Fermat type (which are also hypergeometric functions), together with their inverses. A consequence is the unification of the analyses of many classical models, including those related to the coupon collector's problem, particle transfer (the Ehrenfest model), Friedman's "adverse campaign'' and Pólya's contagion model, as well as the OK Corral model (a basic case of Lanchester's theory of conflicts). In each case, it is possible to quantify very precisely the probable composition of the urn at any discrete instant. We study here in detail "semi-sacrificial'' urns, for which the following are obtained: a Gaussian limiting distribution with speed of convergence estimates as well as a characterization of the large and extreme large deviation regimes. We also work out explicitly the case of $2$-dimensional triangular models, where local limit laws of the stable type are obtained. A few models of dimension three or greater, e.g., "autistic'' (generalized Pólya), cyclic chambers (generalized Ehrenfest), generalized coupon-collector, and triangular urns, are also shown to be exactly solvable.
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]
  • urn process
Cited by

Source: OpenCitations

  • Moments of Gamma type and the Brownian supremum process area

    Probability Surveys

    Authors : Svante Janson ORCID

    Journal reference : Volume 7, 2010, pp.

    DOI : 10.1214/10-ps160

  • Fully Analyzing an Algebraic Pólya Urn Model

    arXiv (Cornell University)

    Authors : Basile Morcrette

    Journal reference : Volume , 2012, pp. 568-581

    DOI : 10.1007/978-3-642-29344-3_48

  • Weighted Random Staircase Tableaux

    arXiv (Cornell University)

    Authors : PAWEŁ HITCZENKO, SVANTE JANSON

    Journal reference : Volume 23, 2014, pp. 1114-1147

    DOI : 10.1017/s0963548314000327

  • On moment sequences and mixed Poisson distributions

    Probability Surveys

    Authors : Markus Kuba ORCID, Alois Panholzer ORCID

    Journal reference : Volume 13, 2016, pp.

    DOI : 10.1214/14-ps244

  • Simulating Deterministic Dynamics by Drawing Coloured Balls at Random in Urns

    Fundamental theories of physics

    Authors : Léon Brenig ORCID

    Journal reference : Volume , 2022, pp. 117-134

    DOI : 10.1007/978-3-031-04458-8_6

  • Modeling Drug Tolerance via Fluctuation Tests with Reversible Phenotypic Switching

    2025 IEEE 64th Conference on Decision and Control (CDC)

    Authors : Anna Hlubinová, Pavol Bokes ORCID, Abhyudai Singh

    Journal reference : Volume , 2025, pp. 4769-4774

    DOI : 10.1109/cdc57313.2025.11312424

  • Some families of increasing planar maps

    Electronic Journal of Probability

    Authors : Marie Albenque ORCID, Jean-Francois Marckert

    Journal reference : Volume 13, 2008, pp.

    DOI : 10.1214/ejp.v13-563

  • Reducing nonlinear dynamical systems to canonical forms

    Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences

    Authors : Léon Brenig ORCID

    Journal reference : Volume 376, 2018, pp. 20170384

    DOI : 10.1098/rsta.2017.0384

  • Large deviation principles for the Ewens-Pitman sampling model

    Electronic Journal of Probability

    Authors : Stefano Favaro, Shui Feng ORCID

    Journal reference : Volume 20, 2015, pp.

    DOI : 10.1214/ejp.v20-3668

  • Occupancy Problems Related to the Generalized Stirling Numbers

    Authors : Thierry E. Huillet ORCID

    Journal reference : Volume 191, 2023, pp.

    DOI : 10.1007/s10955-023-03216-1

  • Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions

    The Annals of Applied Probability

    Authors : Cyril Banderier ORCID, Markus Kuba ORCID, Michael Wallner ORCID

    Journal reference : Volume 34, 2024, pp.

    DOI : 10.1214/24-aap2076

  • Strong convergence of infinite color balanced urns under uniform ergodicity

    arXiv (Cornell University)

    Authors : Antar Bandyopadhyay, Svante Janson ORCID, Debleena Thacker ORCID

    Journal reference : Volume 57, 2020, pp. 853-865

    DOI : 10.1017/jpr.2020.37

  • Randomized rumor spreading in poorly connected small-world networks

    Random Structures and Algorithms

    Authors : Abbas Mehrabian ORCID, Ali Pourmiri ORCID

    Journal reference : Volume 49, 2015, pp. 185-208

    DOI : 10.1002/rsa.20624

  • An urn approach to generalized extreme shock models

    Statistics & Probability Letters

    Authors : Pasquale Cirillo ORCID, Jürg Hüsler

    Journal reference : Volume 79, 2008, pp. 969-976

    DOI : 10.1016/j.spl.2008.11.025

  • Smoothing Equations for Large Pólya Urns

    Journal of Theoretical Probability

    Authors : Brigitte Chauvin, Cécile Mailler ORCID, Nicolas Pouyanne

    Journal reference : Volume 28, 2013, pp. 923-957

    DOI : 10.1007/s10959-013-0530-z

  • Periodic Pólya urns, the density method and asymptotics of Young tableaux

    The Annals of Probability

    Authors : Cyril Banderier ORCID, Philippe Marchal, Michael Wallner ORCID

    Journal reference : Volume 48, 2020, pp.

    DOI : 10.1214/19-aop1411

  • Boundaries from Inhomogeneous Bernoulli Trials

    Progress in probability

    Authors : Alexander Gnedin

    Journal reference : Volume , 2011, pp. 91-110

    DOI : 10.1007/978-3-0346-0244-0_6

  • Limit distributions for large Pólya urns

    arXiv (Cornell University)

    Authors : Brigitte Chauvin, Nicolas Pouyanne, Reda Sahnoun

    Journal reference : Volume 21, 2010, pp.

    DOI : 10.1214/10-aap696

  • Taylor’s Law in Innovation Processes

    Entropy

    Authors : Francesca Tria ORCID, Irene Crimaldi ORCID, Giacomo Aletti ORCID, Vito D. P. Servedio ORCID

    Journal reference : Volume 22, 2020, pp. 573

    DOI : 10.3390/e22050573

  • Clade size distribution under neutral evolutionary models

    Theoretical Population Biology

    Authors : Antonio Di Nunzio ORCID, Filippo Disanto ORCID

    Journal reference : Volume 156, 2024, pp. 93-102

    DOI : 10.1016/j.tpb.2024.02.004

  • Random walks on decorated Galton–Watson trees

    Warwick Research Archive Portal (University of Warwick)

    Authors : Eleanor Archer ORCID

    Journal reference : Volume 60, 2024, pp.

    DOI : 10.1214/23-aihp1386

  • Synchronization and fluctuations for interacting stochastic systems with individual and collective reinforcement

    Stochastic Models

    Authors : Meghdad Mirebrahimi

    Journal reference : Volume 40, 2023, pp. 464-501

    DOI : 10.1080/15326349.2023.2267663

  • Large deviations for generalized Polya urns with arbitrary urn function

    arXiv (Cornell University)

    Authors : Simone Franchini ORCID

    Journal reference : Volume 127, 2017, pp. 3372-3411

    DOI : 10.1016/j.spa.2017.02.010

  • On Generalized Pólya Urn Models

    Journal of Applied Probability

    Authors : May-Ru Chen, Markus Kuba ORCID

    Journal reference : Volume 50, 2013, pp. 1169-1186

    DOI : 10.1239/jap/1389370106

  • Generalized Stirling permutations, families of increasing trees and urn models

    Journal of Combinatorial Theory Series A

    Authors : Svante Janson ORCID, Markus Kuba ORCID, Alois Panholzer ORCID

    Journal reference : Volume 118, 2009, pp. 94-114

    DOI : 10.1016/j.jcta.2009.11.006

  • The Wallis Products for Fermat Curves

    Vietnam Journal of Mathematics

    Authors : Alessandro Gambini ORCID, Giorgio Nicoletti ORCID, Daniele Ritelli ORCID

    Journal reference : Volume 53, 2023, pp. 1-16

    DOI : 10.1007/s10013-023-00617-3

  • Reinforced Galton–Watson processes I: Malthusian exponents

    Random Structures and Algorithms

    Authors : Jean Bertoin ORCID, Bastien Mallein ORCID

    Journal reference : Volume 65, 2024, pp. 387-410

    DOI : 10.1002/rsa.21219

  • A martingale approach for Pólya urn processes

    Electronic Communications in Probability

    Authors : Lucile Laulin ORCID

    Journal reference : Volume 25, 2020, pp.

    DOI : 10.1214/20-ecp321

  • Fluctuation Test with Phenotypic Switching: A Unified Stochastic Approximation Framework

    bioRxiv (Cold Spring Harbor Laboratory)

    Authors : Anna Hlubinová, Pavol Bokes ORCID, Abhyudai Singh ORCID

    Journal reference : Volume , 2025, pp.

    DOI : 10.1101/2025.05.20.655090

  • The projective translation equation and unramified 2-dimensional flows with rational vector fields

    arXiv (Cornell University)

    Authors : Giedrius Alkauskas ORCID

    Journal reference : Volume 89, 2014, pp. 873-913

    DOI : 10.1007/s00010-014-0284-4

  • AN URN MODEL FOR CASCADING FAILURES ON A LATTICE

    Probability in the Engineering and Informational Sciences

    Authors : Pasquale Cirillo ORCID, Jürg Hüsler

    Journal reference : Volume 26, 2012, pp. 509-534

    DOI : 10.1017/s0269964812000162

  • Limit Behavior of Polya Urn Schemes

    Studies in systems, decision and control

    Authors : Ricardo Vélez ORCID, Tomás Prieto-Rumeau ORCID

    Journal reference : Volume , 2018, pp. 421-429

    DOI : 10.1007/978-3-319-73848-2_40

  • A new approach to Pólya urn schemes and its infinite color generalization

    Durham Research Online (Durham University)

    Authors : Antar Bandyopadhyay, Debleena Thacker ORCID

    Journal reference : Volume 32, 2022, pp.

    DOI : 10.1214/21-aap1671

  • Box model of migration channels

    Mathematical Social Sciences

    Authors : Nikolay K. Vitanov ORCID, Kaloyan N. Vitanov

    Journal reference : Volume 80, 2016, pp. 108-114

    DOI : 10.1016/j.mathsocsci.2016.02.001

  • Multicolor urn models with reducible replacement matrices

    Bernoulli

    Authors : Arup Bose ORCID, Amites Dasgupta, Krishanu Maulik ORCID

    Journal reference : Volume 15, 2009, pp.

    DOI : 10.3150/08-bej150

  • DRAWING MULTISETS OF BALLS FROM TENABLE BALANCED LINEAR URNS

    Probability in the Engineering and Informational Sciences

    Authors : Hosam M. Mahmoud ORCID

    Journal reference : Volume 27, 2013, pp. 147-162

    DOI : 10.1017/s0269964812000381

  • GENERALIZED EXTREME SHOCK MODELS WITH A POSSIBLY INCREASING THRESHOLD

    Probability in the Engineering and Informational Sciences

    Authors : Pasquale Cirillo ORCID, Jürg Hüsler

    Journal reference : Volume 25, 2011, pp. 419-434

    DOI : 10.1017/s0269964811000088

  • Discussion of “On simulation and properties of the stable law” by L. Devroye and L. James

    Institutional Research Information System University of Turin (University of Turin)

    Authors : Stefano Favaro, Bernardo Nipoti ORCID

    Journal reference : Volume 23, 2014, pp. 365-369

    DOI : 10.1007/s10260-014-0270-y

  • Asymptotics for the number of blocks in a conditional Ewens-Pitman sampling model

    Electronic Journal of Probability

    Authors : Stefano Favaro, Shui Feng ORCID

    Journal reference : Volume 19, 2014, pp.

    DOI : 10.1214/ejp.v19-2881
Preview
Loading PDF preview...