Arbre aléatoire

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.

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.

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.

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.

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.

Le nombre d'arbres binaires à n nœuds est le n-ième nombre de Catalan ${\displaystyle \scriptstyle C_{n}={\frac {(2n)!}{n!(n+1)!}}}$. Chaque arbre a donc une probabilité ${\displaystyle \scriptstyle 1/C_{n}}$ d'apparaître. L'algorithme de Rémy[1] - [2] engendre en temps linéaire un arbre binaire uniforme.

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.

• Arbre (mathématiques)
• Arbre (graphe)
• Arbre de Galton-Watson

• (en) M. Drmota, Random trees - An Interplay between Combinatorics and Probability, Springer Verlag, Wien/New York (2009), (ISBN 978-3-211-75355-2)