Urn models and threshold phenomenoms in analytic combinatorics.

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

Vincent Puyhaubert (1)

1 ALGO - Algorithms

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.

Cette thèse traite de phénomènes de seuils et de modèles d'urnes, en adoptant le point de vue de la combinatoire analytique. On traite ici trois problèmes qui illustrent cette approche: la transition de phase du problème k-sat, les modèles d'urnes triangulaires de Polya-Eggenberger et le modèle de duel de Ok Corral. La transition de phase du problème k-sat se manifeste par le fait la densité d'une formule caractérise de manière presque sûre sa satisfaisabilité. Nos travaux visent à mettre en évidence une partie de ce phénomène et se relient à un modèle d'urne à jets. Le modèle d'urne de Polya-Eggenberger utilise une urne contenant des boules de diverses couleurs, soumises à des règles de pioches et de substitutions. En utilisant une technique de Flajolet-Gabarro-Pekari, nous déterminons la distribution limite de la composition des modèles dits triangulaires. Le modèle de duel de Ok Corral intervient dans une problématique plus générale de Lanchester de gestion des conflits, selon laquelle on cherche à prédire l'issue de duels entre plusieurs forces armées, en environnement aléatoire. Nous utilisons un lien pré-établi entre ce modèle et une urne de type Polya-Eggenberger pour donner de nouvelles expressions des probabilités du modèle et raffiner les résultats récents de Kingman.

Mots clés: Urn models; Threshold phenomenoms

Mots clés: Modèles d'urnes; Phénomènes de seuils

Domaines: Combinatoire [math.CO]

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