Agenda de l’IDP

Séminaire SPACE Tours

Construction de peignes et marches aléatoires persistantes
Peggy Cénac (Université de Bourgogne)
Friday 13 February 2015 11:00 -  Tours -  Salle 1180 (Bât E2)

Résumé :
Les séquences aléatoires de lettres peuvent être vues comme des chaînes au sens probabiliste ou comme des sources au sens de la théorie de l’information. La manière dont les mots sont produits a une grande influence sur le comportement probabiliste des algorithmes ou des principales structures de données associées (arbre binaire de recherche, arbre digital, arbre des suffixes, pour la compression). Les chaînes de Markov à mémoire de longueur variable constituent une classe de sources probabilistes. Il sera question dans cet exposé d'une construction explicite d'une VLMC en tant que source dynamique, puis d'existence et de convergence vers la mesure stationnaire pour l’exemple du "peigne". Nous verrons ensuite que le peigne peut plus ou moins bien mélanger et être à l'origine de la construction d'arbres de suffixes dont les paramètres ne convergent pas à vitesse logarithmique. Enfin, nous nous intéresserons au comportement asymptotique d’une marche aléatoire construite à partir du peigne, dont les longueurs de sauts ne sont pas forcément intégrables.

Liens :