Marches aléatoires et systèmes à événements discrets – MASED

Le cadre général du projet est l'analyse et l'optimisation de systèmes discrets, éventuellement aléatoires. Cette problématique est par essence pluridisciplinaire, au carrefour entre informatique théorique et mathématique. Les motivations sont à la fois internes aux mathématiques (par exemple, prouver des théorèmes ergodiques pour certains processus aléatoires) et rattachées à des questions pratiques propres à l'informatique (par exemple, optimiser le débit dans un réseau de communication). Dans ce cadre, mon projet de recherche est pour l'essentiel original. Il consiste à associer deux domaines qui semblent de prime abord étrangers l'un à l'autre: les systèmes à événements discrets et les marches aléatoires sur des structures algébriques discrètes. Ces domaines sont extrèmement actifs, leurs motivations différentes, et leurs communautés scientifiques disjointes. Ayant contribué aux deux domaines, j'ai commencé à développer une synthèse que je souhaite poursuivre et enrichir. L'interaction se fait au moyen d'un double aller-retour avec enrichissement mutuel. D'une part, on étudie les marches aléatoires à l'aide d'outils de l'infomatique théorique (combinatoire, automates, transducteurs); d'autre part, on propose et on étudie de nouveaux modèles mathématiques de systèmes à événements discrets fondés sur des mécanismes de marches aléatoires. Une attention particulière est portée aux questions quantitatives et effectives: est-il possible de calculer explicitement les paramètres essentiels d'une marche aléatoire? Ce problème est notoirement difficile et a été très peu regardé par la communauté probabiliste. Dans notre projet, au contraire, ce problème occupe une place centrale en raison de la motivation systèmes à événements discrets. Si la vitesse de fuite d'une marche aléatoire s'interprète comme le débit dans un système à événements discrets, alors on comprend qu'il est important de la calculer voire de l'optimiser.
Les résultats escomptés sont de plusieurs types. Le premier objectif est de réaliser une étude complète des marches aléatoires pour lesquelles il existe une description combinatoire explicite du comportement asymptotique. L'idée de départ est de travailler sur des groupes ou mono des sur lesquels la manipulation des éléments peut se faire à l'aide d'automates finis. L'intuition est que cette structure combinatoire doit se refléter au niveau de la mesure limite de la marche, et donc que cette dernière doit aussi, en un sens, se décrire à l'aide d'automates finis. La retombée principale est alors la capacité à calculer explicitement les paramètres de la marche. Le second objectif est de réinvestir cette connaissance en synthétisant de nouveaux modèles mathématiques pour l'analyse des systèmes à événements discrets, fondés sur les mécanismes de marche aléatoire. Ici, le critère essentiel de pertinence est l'obtention de modèles originaux réalisant un vrai compromis entre puissance de modélisation et capacité d'analyse mathématique exacte.
Les outils à mettre en œuvre dans cette étude sont variés: systèmes dynamiques, théorie des groupes, théorie ergodique et probabilités, mais aussi combinatoire, automates et langages formels. Les membres du projet sont le reflet de cette diversité, chacun d'entre d'eux possédant des spécialités scientifiques distinctes et bien marquées, de l'algorithmique à la théorie des groupes, en passant par la théorie des automates. Cette diversité est évidemment une richesse et une garantie de la vi