Modèles d'urnes et phénomènes de seuils en combinatoire analytique.

Vincent Puyhaubert 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This thesis is about urn models and threshold phenomena, from the point of view of analytic combinatorics. It adresses three main questions: the phase transition in the k-sat problem, Polya-Eggenberger urn models, and the Ok Corral gunfight model. The k-sat phase transition corresponds to the fact that, considering random formulae, satisfiability is almost surely characterised by the density of the formula only. Our work intends to prove some parts of the satisfiability threshold conjecture, using mainly urn models and random allocations. The Polya-Eggenberger urn model subjects an urn containing balls of different colours to replacement rules. We determine the limit distribution of the composition of the triangular models, using Flajolet-Gabarro-Pekari's method. The Ok Corral gunfight is a special case of a general theory of conflict due to Lanchester. Using a link between this model and an urn of the Polya-Eggenberger type, we derive new expressions for the distribution of probabilities and reffine earlier results of Kingman.
Document type :
Liste complète des métadonnées

Cited literature [75 references]  Display  Hide  Download
Contributor : Ecole Polytechnique <>
Submitted on : Tuesday, July 27, 2010 - 2:24:28 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Document(s) archivé(s) le : Thursday, October 28, 2010 - 11:31:41 AM


  • HAL Id : pastel-00001348, version 1



Vincent Puyhaubert. Modèles d'urnes et phénomènes de seuils en combinatoire analytique.. Combinatoire [math.CO]. Ecole Polytechnique X, 2005. Français. 〈pastel-00001348〉



Record views


Files downloads