Résumé : Les marches aléatoires 2D, composés d'un ensemble fini de pas élémentaires et restreintes au quadrant positif, forment des classes combinatoires dotées de structures typiquement complexes, et admettant une grande variété de comportements asymptotiques. En collaboration avec Jérémie Lumbroso (Princeton, USA) et Marni Mishna (SFU, Canada), nous nous intéressons à la génération aléatoire uniforme de marches d'une taille n donnée, à partir de l'ensemble des pas élémentaires. Notre principal résultat consiste en un algorithme de rejet, qui remplace le quart de plan par un demi-plan bien choisi. On se ramène alors à la génération aléatoire de marches 1D composées de pas généralement irrationnels, et pour lesquels une génération uniforme est possible en temps polynomial à partir d'une famille de grammaires non-contextuelles. Un résultat de Garbit et Raschel démontre ensuite l'existence d'un demi-plan tel que l'espérance du nombre de tirages dans le demi-plan est polynomiale, mais une analyse plus fine de la complexité de cette approche soulève des questions en combinatoire (analytique) des marches 1D/2D et des spécifications algébriques. Cette présentation consiste en une version étendue d'un exposé présenté à GASCOM 2016.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr