Composition de fonctions aléatoires et reconstruction de mots

par Guillaume Chapuy (IRIF)

jeudi 5 févr. 2026, 11:00 → 12:00 Europe/Paris

Salle Pierre Grisvard (IHP - Bâtiment Borel)

Je choisis, sans vous les montrer, deux fonctions a et b de [n] dans [n], uniformément au hasard (autrement dit, je choisis un automate déterministe complet à n états sur l'alphabet {a,b}, uniformément au hasard). Pour tout mot w dans {a,b}* je dispose donc d'une fonction, obtenue en composant a et b dans l'ordre des lettres de w.

Question: si je vous montre la fonction, avec n très grand, pouvez-vous deviner le mot w? (à la symétrie a/b près). Par exemple, pouvez vous faire la différence entre w=a et w=aaaab? ou alors entre w=aba et w=abb?

Je ne sais pas répondre en toute généralité à cette question (pour deux mots différents, la distance en variation totale entre les fonctions aléatoires associées tend-elle vers zéro, vers un, ou ni l'un ni l'autre?) mais je présenterai un certain nombre de résultats partiels.

L'exposé sera élémentaire et pédagogique, et sera déjà l'occasion de "réviser" ce que l'on sait dire d'une fonction aléatoire [n]->[n] uniforme (structure locale, cycles, etc).

Travail avec Guillem Perarnau (Barcelone).