Arbre aléatoire

page d'homonymie

En théorie des probabilités un arbre aléatoire est un arbre défini en utilisant une loi de probabilité sur un ensemble d'arbres (au sens de graphe). Par exemple, un arbre aléatoire à n nœuds peut être choisi aléatoirement parmi tous les arbres à n nœuds suivant une loi de probabilité, par exemple avec une loi uniforme. Il existe d'autres manières de générer certains arbres particuliers (binaires par exemple). Les arbres de Galton-Watson sont des cas particuliers d'arbres aléatoires.

Arbre uniforme modifier

Un arbre uniforme à n nœuds est un arbre choisi aléatoirement dans une classe d'arbres avec une loi de probabilité uniforme sur cette classe. Il est parfois possible d'associer leur loi avec la loi d'un arbre de Galton-Watson.

Arbre planaire enraciné uniforme modifier

Considérons la classe des arbres planaires enracinés (non-étiquetés) avec n nœuds.

Un arbre planaire enraciné uniforme a la même loi de probabilité qu'un arbre de Galton-Watson conditionné à avoir n nœuds et dont la loi de reproduction est une loi géométrique de paramètre 1/2.

Arbre étiqueté et enraciné uniforme modifier

Considérons la classe des arbres étiquetés et enracinés (non-planaires) avec n nœuds.

Un arbre étiqueté et enraciné uniforme a la même loi de probabilité qu'un arbre de Galton-Watson conditionné à avoir n nœuds et dont la loi de reproduction est une loi de Poisson de paramètre 1.

Arbre binaire uniforme modifier

Considérons la classe des arbres binaires avec n nœuds. Si on considère uniquement les nœuds internes de l'arbre binaire, c'est-à-dire on enlève les feuilles de l'arbre, il reste trois types de nœuds :

  • les nœuds sans fils, qui possédaient 2 fils feuilles précédemment,
  • les nœuds avec 1 fils, dont le deuxième fils était précédemment une feuille (notons qu'il y a deux possibilités pour la position de la feuille : droite ou gauche),
  • les nœuds avec 2 fils, dont aucun des deux fils n'était une feuille précédemment.

En ajoutant des feuilles à tous les endroits libres, on retrouve l'arbre binaire initial.

Ainsi, un arbre binaire uniforme a la même loi de probabilité qu'un arbre de Galton-Watson conditionné à avoir n nœuds et dont la loi de reproduction est une loi binomiale B(2,1/2). C'est-à-dire chaque nœud a probabilité 1/4 d'avoir 0, 1/4 d'avoir 2 fils et 1/2 d'avoir 1 fils.

Arbre couvrant uniforme modifier

Soit G un graphe. Un arbre couvrant (spanning tree en anglais) de G est un sous-graphe de G contenant tous les nœuds et une partie des arêtes et qui est un arbre, c'est-à-dire un graphe non orienté, acyclique et connexe. Un arbre couvrant uniforme est un arbre couvrant choisi aléatoirement parmi tous les arbres couvrant de G avec la même probabilité.

Soit v et w deux nœuds de G. Tous arbre couvrant contient précisément un chemin entre v et w. Prendre ce chemin dans un arbre couvrant uniforme donne un chemin aléatoire. La loi de ce chemin est la même que la loi de la marche aléatoire à boucles effacées (loop-erased random walk en anglais) partant de v et stoppée en w.

Comme corollaire immédiat, la marche aléatoire à boucle effacées est symétrique en ses points de départ et de fin. Plus précisément, la marche aléatoire à boucles effacées partant de v et stoppée en w a même loi que la marche aléatoire à boucle effacées inversée partant de w et stoppée en v. Ce qui n'est pas trivial.

Il existe plusieurs algorithmes pour générer des arbres couvrants uniformes. Donnons ici l'algorithme de Wilson. Prenons deux nœuds et réalisons une marche aléatoire à boucles effacées d'un point à l'autre. Prenons ensuite un troisième nœud qui n'est pas dans le chemin ainsi construit et réalisons une marche aléatoire à boucle effacées jusqu'à ce qu'elle rencontre le chemin précédemment construit. on recommence jusqu'à ce que l'arbre couvre tous les nœuds. Finalement, qu'importe la méthode que vous utilisez pour choisir les nœuds de départ, vous obtiendrez la même loi d'arbre couvrant, la loi uniforme.

Un graphe peut avoir différents arbres couvrants. On peut ainsi donner un poids à chaque arête qui est une valeur représentant la probabilité d'être choisi (poids faible pour une grande probabilité). Un arbre couvrant possède ainsi un poids qui est la somme des poids de ses arêtes. Un arbre couvrant minimum ou arbre couvrant à poids minimum est alors un arbre couvrant avec un poids inférieur ou égal au poids de tous les autres arbres couvrants.

On peut également assigner un poids aléatoire à chaque arête en utilisant des variables aléatoires uniformes sur [0,1] indépendantes. L'arbre couvrant aléatoire minimum est alors l'arbre couvrant 0 poids minimum.

Arbre binaire aléatoire modifier

En théorie des probabilités et en informatique, un arbre binaire aléatoire est un arbre binaire choisi aléatoirement par une loi de probabilité sur l'ensemble des arbres binaires. Plusieurs procédés sont utilisés : les arbres binaires construits par insertion successive des nœuds selon une permutation aléatoire, et les arbres binaires choisis par une loi uniforme discrète, par séparation binaire des arbres.

Par une permutation aléatoire modifier

Pour tout ensemble de nombres, on construit un arbre binaire de recherche en insérant chaque nouveau nombre en tant que feuille de l'arbre. La position d'insertion est déterminée par recherche dichotomique sur les nombres précédents. Par exemple, pour la suite (1,3,2), 1 est la racine, 3 est le fils droit de 1 et 2 est le fils gauche de 3. Il y a 6 permutations différentes de (1,2,3) cependant il n'y a que 5 arbres différents, (2,1,3) et (2,3,1) donnent le même arbre.

Loi uniforme modifier

Le nombre d'arbres binaires à n nœuds est le n-ième nombre de Catalan  . Chaque arbre a donc une probabilité   d'apparaître. L'algorithme de Rémy[1],[2] engendre en temps linéaire un arbre binaire uniforme.

Séparation binaire modifier

On peut générer des arbres aléatoires binaires avec n nœuds en considérant une variable aléatoire X à valeurs dans ]0,1[. Les premiers Xn (en considérant la partie entière) entiers sont assignés au sous-arbre gauche, le prochain entier sera la racine et les autres au sous-arbre droit. On itère pour chaque sous-arbre. Si X est choisie uniformément sur l'intervalle, l'arbre obtenu est le même que l'arbre binaire aléatoire construit avec une permutation aléatoire quand la racine est choisie uniformément. Devroye et Kruszewski[3] montrent que si X suit une loi bêta et en représentant de manière appropriée les arêtes, les arbres ainsi générés peuvent être utilisés pour simuler des arbres phylogénétiques.

Arbres de Galton-Watson modifier

Un arbre de Galton-Watson représente la généalogie d'un processus de Galton-Watson dont chaque nœud a un nombre aléatoire de fils : on attribue des variables aléatoires indépendantes et de même loi de reproduction à chaque nœud.

Annexes modifier

Articles connexes modifier

Notes et références modifier

  1. J.L. Rémy, Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire, R.A.I.R.O., Informatique Théorique, 19.2 (1985), p. 179-195
  2. Donald E. Knuth, The Art of Computer Programming, vol. 4.4 (Generating all Trees), Addison Wesley, p. 18
  3. L. Devroye, P. Kruszewski, The botanical beauty of random binary trees, Lecture Notes in Computer Science, Springer-Verlag, vol. 1027 (1996), p. 166–177, doi 10.1007/BFb0021801.
  • (en) M. Drmota, Random trees - An Interplay between Combinatorics and Probability, Springer Verlag, Wien/New York (2009), (ISBN 978-3-211-75355-2)