Analytic Combinatorics of the Mabinogion Urn

Abstract : 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.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.549-572, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194668
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:51
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:54:43

Fichier

dmAI0138.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194668, version 1

Collections

Citation

Philippe Flajolet, Thierry Huillet. Analytic Combinatorics of the Mabinogion Urn. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.549-572, 2008, DMTCS Proceedings. 〈hal-01194668〉

Partager

Métriques

Consultations de la notice

387

Téléchargements de fichiers

179