Génération aléatoire ``laxiste'' d'arbres

Le fait que les arbres de familles simples (au sens de Meir et Moon) correspondent à des processus de branchement conditionnés par une taille fixée, est relativement bien connu\,; l'extension à des structures combinatoires dont les séries génératrices satisfont des équations algébriques ne pose pas de problèmes. Dans cet exposé, je présenterai un moyen extrêmement simple de tirer parti de cette relation pour obtenir des générateurs aléatoires efficaces d'arbres (et d'autres structures).

Ces générateurs aléatoires sont qualifiés de ``laxistes'' car, bien que la condition d'uniformité à taille fixée soit conservée (``pour tout $n$, tous les arbres de taille $n$ ont la même probabilité d'être tirés''), on est typiquement amené à relacher les conditions sur la taille (l'objectif ``obtenir un arbre de taille $n$'' est remplacé par ``obtenir un arbre de taille comprise entre $n$ et $n+f(n)$'').