2e colloque interne de l'équipe “Probabilités & Statistiques” de l'Institut Élie Cartan — 5 décembre 2013
Anne Briquet

Hauteur & niveau de saturation de l'arbre de Lyndon généralisé

Un arbre de Lyndon est un arbre binaire construit simplement, en scindant en deux un mot de n lettres et en itérant cette opération jusqu'à emiettement complet du mot en n lettres séparées. La césure est à chaque fois déterminée à l'aide de l'ordre lexicographique (voir encadrés ci-dessous). Le problème de la hauteur de l'arbre de Lyndon, longtemps resté ouvert, a été soulevé par des membres du collectif Lothaire (collectif qui a publié trois ouvrages fondateurs sur la combinatoire des mots). Les applications en vue sont l'étude des algèbres de Lie simples, et à l'heure actuelle (de manière moins claire) la cryptographie. Nous rappellerons les éléments essentiels de la solution du problème dans le cas à 2 lettres équiprobables, faisant intervenir les arbres de Yule et les processus de Galton-Watson, et nous aborderons les problèmes plus spécifiquement lié au cas général d'un nombre quelconque de lettres non équiprobables, qui nous amèneront sur le terrain des statistiques de valeurs extrêmes.

On trouve que la hauteur de ces arbres converge en probabilité vers log(n) multiplié par une constante ne dépendant que de p0 et de max {pi : i≠0}, où pi est la probabilité d'occurrence de la lettre i. Le niveau de saturation d'une lettre non nulle (càd. la hauteur de la feuille la plus basse étiquetée par cette lettre) présente la même forme — au contraire de celui de la lettre 0 (qui est aussi le niveau de saturation de l'arbre, càd. la hauteur de la feuille la plus basse tout court), lequel est en O(1) et dont on a une expression explicite.