Projet ANR-06-JCJC-0069 – MASED : Marches aléatoires et systèmes à événements discrets
Programme : Programme "Jeunes chercheuses et jeunes chercheurs" (JCJC) 2006
Année de financement : 2006
Coordinateur du projet : CNRS DELEGATION REGIONALE PARIS B (CNRS DELEGATION REGIONALE PARIS B)
Partenaires : Centre national de la recherche scientifique
Montant : 120000.0 euros
Date de début : 2006
Durée : 36 mois
Résumé : Le cadre g\'en\'eral du projet est -  l'analyse et l'optimisation de syst\`emes discrets, -  \'eventuellement al\'eatoires. Cette probl\'ematique est par essence -  pluridisciplinaire, au carrefour -  entre informatique th\'eorique  -  et math\'ematique. Les motivations sont \`a la fois internes aux math\'ematiques (par exemple, -  prouver des th\'eor\`emes ergodiques pour certains processus al\'eatoires) -  et rattach\'ees \`a des questions pratiques propres \`a l'informatique -  (par exemple, optimiser le d\'ebit dans un r\'eseau de communication). -  -  Dans ce cadre, mon projet de recherche est pour l'essentiel original. -  Il consiste \`a associer deux domaines qui semblent de prime abord -  \'etrangers l'un \`a l'autre~: les syst\`emes \`a \'ev\'enements -  discrets et les marches al\'eatoires sur des structures alg\'ebriques discr\`etes. -  Ces domaines sont extr\`emement actifs, leurs motivations -  diff\'erentes, et leurs communaut\'es scientifiques disjointes. -  Ayant contribu\'e aux deux domaines, j'ai commenc\'e \`a -  d\'evelopper une synth\`ese que je souhaite poursuivre et -  enrichir. -  L'interaction -  se fait au moyen d'un double aller-retour avec enrichissement -  mutuel. D'une part, on \'etudie les marches -  al\'eatoires \`a l'aide d'outils de l'infomatique th\'eorique -  (combinatoire, automates, transducteurs); d'autre -  part, on propose et on \'etudie de nouveaux mod\`eles math\'ematiques -  de syst\`emes \`a \'ev\'enements -  discrets fond\'es sur des m\'ecanismes de marches al\'eatoires. -  Une -  attention particuli\`ere est port\'ee aux questions quantitatives et -  effectives~: est-il possible de calculer explicitement les -  param\`etres essentiels d'une marche al\'eatoire~? -  Ce probl\`eme est notoirement -  difficile et a \'et\'e tr\`es peu regard\'e par la communaut\'e -  probabiliste. -  Dans notre projet, au contraire, ce probl\`eme occupe une place -  centrale en raison de la motivation syst\`emes \`a \'ev\'enements -  discrets. Si la vitesse de fuite d'une marche -  al\'eatoire s'interpr\`ete comme le d\'ebit dans un syst\`eme \`a -  \'ev\'enements discrets, alors on comprend qu'il est important de -  la calculer voire de l'optimiser. -  -  \medskip -  -  Les r\'esultats escompt\'es sont de plusieurs types. -  Le premier objectif est de r\'ealiser une \'etude compl\`ete -  des marches al\'eatoires pour lesquelles il existe une description -  combinatoire explicite du comportement asymptotique. L'id\'ee de -  d\'epart est de travailler sur des groupes ou -  mono\"{\i}des sur lesquels la manipulation des \'el\'ements peut se -  faire \`a l'aide d'automates finis. L'intuition est que cette -  structure combinatoire doit se refl\'eter au niveau de la mesure -  limite de la marche, et donc que cette derni\`ere doit -  aussi, en un sens, se d\'ecrire \`a l'aide d'automates finis. La -  retomb\'ee principale est alors la capacit\'e \`a calculer -  explicitement les param\`etres de la marche. -  Le second objectif est  -  de r\'einvestir cette connaissance en synth\'etisant de nouveaux mod\`eles  -  math\'ematiques pour l'analyse des syst\`emes \`a -  \'ev\'enements discrets, fond\'es sur les m\'ecanismes de marche -  al\'eatoire. Ici, le crit\`ere essentiel de pertinence est l'obtention de mod\`eles -  originaux r\'ealisant un vrai compromis entre -  puissance de mod\'elisation et capacit\'e -  d'analyse math\'ematique exacte. -  -  \medskip -  -  Les outils \`a mettre en {\oe}uvre dans cette \'etude sont vari\'es~: -  syst\`emes dynamiques, th\'eorie des groupes, th\'eorie -  ergodique et probabilit\'es, mais aussi combinatoire, -  automates et langages formels. Les membres du projet sont le reflet de -  cette diversit\'e, chacun d'entre d'eux poss\'edant des -  sp\'ecialit\'es scientifiques distinctes et bien marqu\'ees, de -  l'algorithmique \`a la th\'eorie des groupes, en passant par la -  th\'eorie des automates. Cette diversit\'e est \'evidemment une -  richesse et une garantie de la vi