Séminaire Probabilités et Statistiques
Autour des algorithmes de rejet anticipé
06
April 2023
logo_team
Intervenant : Axel Bacher
Institution : LIPN, Institut Galilée, Université Sorbonne Paris Nord
Heure : 14h00 - 15h00
Lieu : 3L15

Les algorithmes de rejet anticipé sont une classe d'algorithmes de
génération aléatoire dont les plus célèbres sont les algorithmes dits
florentins pour les mots de Motzkin (Barcucci et al., 1992). Je
présenterai plusieurs de ces algorithmes et montrerai des résultats
permettant de les analyser de manière systématique en loi limite. Je
montrerai aussi comment, dans certains cas (mots de Dyck ou arbres
binaires, notamment), on peut obtenir des algorithmes plus efficaces en
s'affranchissant de tout rejet. Enfin, je détaillerai les propriétés des
lois limites de ces algorithmes, dont les densités vérifient une
équation différentielle avec retard, ce qui entraîne une structure un
peu inhabituelle (par exemple, elles ont une singularité en tous les
points entiers).

Certains de ces travaux sont en commun avec Olivier Bodini, Alice
Jacquot, Andrea Sportiello.

All (past and future) events