Philippe Flajolet ; Thierry Huillet - Analytic Combinatorics of the Mabinogion Urn

dmtcs:3591 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science -
Analytic Combinatorics of the Mabinogion Urn

Authors: Philippe Flajolet 1; Thierry Huillet 2

  • 1 Algorithms
  • 2 Laboratoire de Physique Théorique et Modélisation

The Mabinogion urn is a simple model of the spread of influences amongst versatile populations. It corresponds to a non-standard urn with balls of two colours: each time a ball is drawn, it causes a ball of the other kind to switch its colour. The process stops once unanimity has been reached. This note provides analytic expressions describing the evolution of the Mabinogion urn, based on a time-reversal transformation applied to the classical Ehrenfest urn. Consequences include a precise asymptotic analysis of the stopping-time distribution―it is asymptotically normal in the "unfair'' case and akin to an extreme-value (double exponential) distribution in the "fair'' case―as well as a characterization of the exponentially small probability of reversing a majority.

Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: Analytic combinatorics,asymptotic analysis,urn models,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1088/1751-8113/42/34/345005
  • 10.1088/1751-8113/42/34/345005
  • 10.1088/1751-8113/42/34/345005
Reversing the drift of the Ehrenfest urn model and three conditionings

Consultation statistics

This page has been seen 163 times.
This article's PDF has been downloaded 133 times.