Soutenance mémoire
Quel rapport y a-t-il entre la propagation d’une épidémie, le passage d’un gaz entre deux compartiments, l’expansion d’un réseau social, la ruine d’un joueur ou d’une banque, la collection de vignettes, la génétique des populations, la croissance d’une branche dans un arbre ou encore une campagne électorale désastreuse ? A priori, ces problèmes sont de natures très différentes, cependant ils partagent tous certaines caractéristiques. Tout d’abord, il s’agit toujours de phénomènes évolutifs : croissance, décroissance ou échange au cours du temps. Ensuite, nous pouvons distinguer deux types de caractères dans chacun des exemples : individus sains contre individus infectés par une épidémie ; compartiment A ou B pour un gaz ; présence ou absence d’un individu dans un réseau social ; possession ou non d’argent pour un joueur ; possession ou non d’une vignette dans la collection ; présence ou non d’un gène chez un individu ; feuille ou nœud dans la branche d’un arbre ; partisans du candidat X ou Y dans la campagne électorale. Enfin, il se dégage une propriété d’uniformité parmi l’ensemble des individus, atomes, particules ou objets considérés. À un instant donné, chaque individu peut devenir infecté ; n’importe quelle particule de gaz peut changer de compartiment ; n’importe qui peut rejoindre ou quitter le réseau ; toute pièce de monnaie peut être gagnée ou perdue ; n’importe quelle vignette peut être découverte ; le gène de chaque individu peut muter d’une génération à une autre ; la branche de l’arbre peut pousser au niveau d’une feuille ou d’un nœud ; chaque partisan peut changer de camp à tout moment. Tous ces phénomènes se regroupent dans un même modèle : les urnes. Nous disposons d’une urne contenant des boules toutes identiques, de deux couleurs différentes. Chaque boule représente un individu, un objet, une particule. La couleur de la boule désigne une propriété : présence ou absence, catégorie A ou B, candidat X ou Y, feuille ou nœud. Ainsi, tous ces problèmes sont regroupés dans un même formalisme. Une fois ce modèle statique adopté, nous voulons modéliser l’évolution du modèle au cours du temps. Pour cela, il suffit de choisir au hasard et à chaque instant une boule dans l’urne, puis d’appliquer une règle de transformation qui permet de modéliser la dynamique que l’on souhaite étudier. Ce formalisme est celui des urnes de Pólya .
Historique des urnes de Pólya
L’étude des urnes remonte à quelques siècles. Certains problèmes d’échange de particules de gaz entre deux compartiments sont traités via des urnes par J. Bernoulli (fin XVIIe ) et P. S. Laplace (fin XVIIIe ). Les premières modélisations des urnes telles qu’elles sont traitées dans ce manuscrit datent de 1923 : l’étude de la propagation d’épidémie par G. Pólya et F. Eggenberger [EP23] débute par la modélisation suivante [Pól30] : “Une urne contient originalement N boules, dont R sont rouges et S noires, R+S = N. Nous faisons dans l’urne des tirages successifs en ajoutant à l’urne, après chaque tirage, à la place de la boule tirée 1 + ∆ boules de la même couleur. Si ∆ est positif, le nombre de boules augmente après chaque tirage, chaque succès obtenu favorise les chances de succès à obtenir, chaque insuccès gâte encore les chances des épreuves suivantes, le succès ainsi que l’insuccès sont contagieux.”
Notons (An , Bn ) la composition de l’urne après n tirages successifs, An étant le nombre de boules noires dans l’urne et Bn le nombre de boules blanches. Deux questions se posent alors : pour un entier n fixé, que contient l’urne ? Quelle est la composition de l’urne lorsque le nombre de tirages est très grand, lorsque n tend vers l’infini ? D’une part, nous cherchons la distribution de probabilité du vecteur (An, Bn ), d’autre part nous cherchons la loi limite qui gouverne le comportement de l’urne. La Figure 1 (p.8) illustre les comportements très divers des urnes de Pólya. Ce modèle est très simple dans son énoncé. La diversité des règles fait sa richesse, et ses possibilités infinies traduisent des comportements multiples. Le but est de comprendre les phénomènes limites à partir des règles imposées au départ.
Une infinité d’applications
Le modèle des urnes de Pólya est très riche par la diversité des règles. Les applications des urnes touchent de ce fait un très grand nombre de domaines : les probabilités et statistiques classiques, l’épidémiologie, la physique statistique, la génétique des populations ou encore la finance [CGH12]. Le livre de N. L. Johnson et S. Kotz [JK77] et livre de H. M. Mahmoud [Mah08] regorgent d’applications de ces modèles. Nous rappelons quelques exemples classiques.
Urnes et informatique fondamentale
Analyse d’algorithme. L’informatique est l’art de traiter l’information de façon automatique. Ainsi, les algorithmes sont l’objet au cœur de cette discipline. Un algorithme n’est rien d’autre qu’une succession d’instructions de base qu’une machine doit effectuer. Ces instructions permettent d’agir automatiquement sur une donnée fournie en entrée de l’algorithme. Les données de départ sont structurées et peuvent prendre des formes diverses (entiers, mots, arbres, graphes, etc). L’évaluation des performances d’un algorithme se fait essentiellement sur le temps de calcul du résultat. Pour avoir une évaluation précise du temps de calcul, il est indispensable de bien comprendre les structures de données fournies en entrée. La donnée du temps moyen de calcul sur une entrée quelconque est une mesure précise de la performance de l’algorithme. L’analyse d’algorithme repose donc sur la compréhension fine des structures de données, et de leur propriétés génériques (celles que l’on observe dans le cas moyen). Depuis une dizaine d’années, les urnes de Pólya ont permis de modéliser certaines structures de données et certains comportements présents en informatique. Citons par exemple les arbres de recherches au pire cas garanti, tels que les arbres 2–3, ou encore les B-trees en base de données. L’urne [−2, 3, 4,−3] modélise la croissance des arbres 2–3, structure utilisée pour le tri et la recherche de données. Un autre exemple est lié aux fonctions de hachage [Dur04], outil très présent pour les algorithmes de fouille de flots de données (streaming algorithms) ou encore en cryptographie. Des connections existent également avec la modélisation de croissance de réseaux sociaux (modèles d’attachement préférentiel, graphe du web, k-arbres).
L’apport probabiliste
Toutes ces applications se sont fortement développées au XXe siècle. La théorie a apporté de nombreuses réponses, en grande partie par des méthodes probabilistes. Les résultats mêlent combinatoire et probabilité pour de nombreuses classes d’urnes; le livre de H. M. Mahmoud [Mah08] fait une synthèse des travaux sur les urnes. Des résultats asymptotiques avec une approche très générale sont obtenus par S. Janson [Jan04, Jan06], et nous rappelons ici un résultat asymptotique fondamental. Pour une urne équilibrée [a, b,c, d] de balance σ = a + b = c + d, nous notons p la constante p = c − a = b − d. Notons λ le rapport de ces deux quantités λ = −p/σ. Si la quantité λ est inférieure ou égale à 1/2, le comportement limite de l’urne est gaussien : les variables aléatoires An et Bn comptant le nombre de boules noires et blanches convergent après renormalisation vers une gaussienne. Lorsque la quantité λ est strictement supérieure à 1/2, les lois limites ne sont pas gaussiennes.
Lorsque λ ≤ 1/2, l’usage est de parler de petites urnes; lorsque λ > 1/2, la terminologie grandes urnes est employée. Il est donc connu que les petites urnes ont un comportement gaussien. Pour les grandes urnes, des avancées sur la compréhension des lois limites sont dans les articles de N. Pouyanne et al. [Pou05, Pou08, CPS11, CMP13]. L’article de S. Janson [Jan04] donne également des résultats généraux de convergence dans un cadre plus large, sans condition d’équilibre, par des méthodes de plongement en temps continu.
La vision de Philippe Flajolet
Les travaux de P. Flajolet et coauteurs [FGP05, FDP06] sont un retour à une vision purement combinatoire des urnes. La combinatoire analytique, domaine développé dans [FS09] par P. Flajolet et R. Sedgewick , a montré ces vingt dernières années sa pertinence dans le traitement systématique des objets combinatoires classiques (mots, arbres, graphes, permutations, . . . ). En partant simplement de dénombrement et de récurrences sur les objets, la combinatoire est ensuite manipulée via des fonctions génératrices, outil essentiel de la combinatoire analytique. Les articles de P. Flajolet et al. illustrent l’intérêt de cette approche pour la compréhension des urnes de Pólya. Grâce à l’analyse systématique d’équation aux dérivées partielles [FGP05] puis de systèmes différentiels [FDP06], la combinatoire analytique apporte une certaine nouveauté sur les propriétés asymptotiques de plusieurs classes d’urnes. La vitesse de convergence ainsi que des précisions locales sur la distribution limite s’ajoutent au phénomène gaussien. C’est ainsi que cette thèse a vu le jour il y a trois ans, dans la continuité des travaux de P. Flajolet, P. Dumas, V. Puyhaubert, J. Gabarró et H. Pekari. Notre étude est le développement de la combinatoire analytique pour les classes d’urnes de Pólya non analysées par ces auteurs.
Urnes et combinatoire analytique
Combinatoire analytique : Aperçu et techniques
La combinatoire analytique se donne pour but l’étude des structures combinatoires de grande taille, par l’intermédiaire de l’analyse de fonctions génératrices, objets fondamentaux de cette théorie. Plusieurs aspects interviennent alors : les objets combinatoires et leurs séries génératrices associées sont traités tout d’abord algébriquement, d’une manière formelle. Ensuite, les séries génératrices sont vues comme des fonctions de la variable complexe, et cette étude analytique permet d’accéder, via les singularités des fonctions, au comportement asymptotique des objets combinatoires. Enfin, l’utilisation symbolique de fonctions génératrices multivariées permet l’étude de paramètres caractéristiques sur les objets combinatoires. L’analyse complexe intervient encore afin de dériver des propriétés probabilistes sur ces objets aléatoires de grande taille.
Asymptotique et analyse complexe
Les outils précédents permettent d’avoir des expressions précises des coefficients des séries génératrices, ainsi que l’expression des moments. La présente section rappelle les résultats importants de combinatoire analytique concernant l’asymptotique des séries génératrices [FS09, Chap. VI]. Le point principal, basé sur l’analyse de singularité est le lemme de transfert, dû à P. Flajolet et A. Odlyzko [FO90]. Dans cette section, nous considérons une série génératrice f (z) issue d’une description combinatoire, et nous la voyons comme une fonction de la variable complexe. Les coefficients fn ont un comportement asymptotique du type fn ∼ λ nθ(n), qui satisfait les deux principes suivants.
Premier principe de l’analyse asymptotique. L’emplacement des singularités de la fonction f (z) donne le facteur λ n de croissance exponentielle des coefficients fn .
Second principe de l’analyse asymptotique. Le nature des singularités de la fonction f (z) détermine le facteur de croissance sous-exponentiel θ(n) des coefficients fn . Le théorème suivant est le lien entre l’analyse complexe et les coefficients des séries génératrices. C’est une simple application du théorème des résidus.
|
Table des matières
Introduction
I Urnes et combinatoire analytique
1 Combinatoire analytique : aperçu et techniques
1.1 Séries génératrices
1.2 Paramètres et séries génératrices multivariées
1.3 Asymptotique et analyse complexe
1.4 Lois limites
1.5 Théorème de Cauchy-Kowalevski
2 Urnes et combinatoire analytique – Les fondamentaux
2.1 Les histoires d’une urne
2.2 Urnes de Pólya et système différentiel
2.3 Résultats par combinatoire analytique
II Urnes algébriques
Introduction
3 Recherche automatique des urnes algébriques
3.1 La démarche sur un exemple
3.2 Remarques préliminaires à l’automatisation
3.3 L’algorithme de GUESS’N’PROVE
3.4 Résultats de la recherche automatique
3.5 Repousser les limites
4 Preuves d’algébricité
4.1 Le cas trivial p = 0
4.2 Les urnes à croissance préférentielle : cas (ii)
4.3 Les urnes à croissance adverse : cas (iii)
4.4 Les urnes algébriques non strictement additives
Conclusion – Récapitulatif
III Analyse asymptotique des urnes algébriques
Introduction
5 Asymptotique des urnes C P
5.1 Moyenne, Variance, Moments
5.2 Résultats asymptotiques
5.3 Analyse asymptotique par méthode de col
6 Asymptotique des urnes CA
6.1 Moments de An
6.2 Résultats asymptotiques
6.3 Analyse asymptotique par analyse des singularités
IV Applications et extensions des modèles d’urnes
7 Urnes additives et réseaux sociaux
7.1 Urnes équilibrées additives avec p > 0
7.2 Quelques exemples d’urnes additives avec p > 0
7.3 Urnes et k-arbres
8 Urnes multicolores et fonctions booléennes
8.1 Le cas de l’urne 3 × 3
8.2 Généralisation par une urne (k + 2) × (k + 2)
8.3 Un peu de combinatoire bijective
Conclusion
Télécharger le rapport complet
