METROPOLIS ALGORITHME DE

Inventé en 1953 par Nicholas Metropolis et ses collaborateurs (dont Edward Teller, le « père » de la bombe H) du laboratoire de Los Alamos au Nouveau-Mexique, l'algorithme de Metropolis était d'abord destiné à faire calculer par des ordinateurs les équations d'états de mélanges de molécules en interactions. Il s'est depuis lors révélé bien adapté pour résoudre de nombreux problèmes de mécanique statistique et de chimie. L'outil principal de l'algorithme est une chaîne de Markov : on tire au hasard une boule et on déplace son centre d'une distance d ; le mouvement est accepté si la nouvelle configuration des boules reste sans recouvrement.

L'algorithme de Metropolis est un outil fréquemment utilisé dans les simulations numériques, mais sa vitesse de convergence n'est pas précisément connue. Un pas décisif dans la compréhension de cette efficacité vient d'être accompli par trois mathématiciens de l'université de Nice et de l'université Stanford (Californie). Titré « Analyse géométrique pour l'algorithme de Metropolis dans des domaines de Lipschitz », l'article de Persi Diaconis, Gilles Lebeau et Laurent Michel, publié dans la livraison d'août 2011 de la revue Inventiones Mathematicae, analyse un cas particulier important : la distribution de N boules de rayon r sans recouvrement.

Persi Diaconis et ses collaborateurs ont mené une analyse spectrale de cette chaîne de Markov dans le cas où la densité (le produit Nr²) est petite. Ils ont montré que, près de la valeur 1, le spectre est discret, et ils ont pu estimer la distance à la mesure d'équilibre en fonction du produit Nd². Cette distance est une estimation de la vitesse de convergence de l'algorithme. Leur travail introduit de nouveaux concepts géométriques – le nombre de composantes connexes de l'espace de configuration et la structure des singularités au bord de cet espace –, lesquels devraient permettre de généraliser leur étude au cas, plus intéressant, où la densité n'est pas faible.

— Bernard PIRE