Les marches aléatoires avec branchement

 

Dana Addario-Berry

Université McGill

 

Domaine : structures abstraites

Programme établissement de nouveaux chercheurs universitaires

Concours 2012-2013

Le premier but de ce projet de recherche est une meilleure compréhension du comportement des marches aléatoires avec branchement (MAB), en particulier des points extrémaux de chemins individuels de tels processus. Le deuxième but est de développer et d'analyser des algorithmes de recherche qui fonctionnent à l'aide des MAB.

Dû à la croissance exponentielle de la taille de la population d'une marche aléatoire avec branchement, les algorithmes efficaces ont forcément besoin de considérer les sous-populations ciblées. À l'aide d'outils mathématiques, il est souvent possible d'établir l'efficacité de ces algorithmes d'une façon rigoureuse. Le comportement de premier ordre des points extrémaux est bien compris depuis les années 1970. Cependant, ce n'est que récemment qu'on a réussi à caractériser précisément l'espérance du point extrémal pour une famille de marches aléatoires de branchement dont la fonction de distribution satisfait des conditions de décroissance suffisamment restrictives. L'analyse est à la fois combinatoire et probabiliste. En développant les outils qui proviennent de la combinatoire analytique, on espère pouvoir étendre ces théorèmes à des familles plus générales, et ainsi trouver le comportement d'une famille très générale de marches aléatoires de branchement.