Metropolis Monte Carlo sampling: convergence, localization transition and optimality

Although Buffon's needle problem [1] may be considered as the earliest documented use of Monte Carlo sampling (18th century), the method was developed at the end of the second world war and dates from the early days of computer use [2, 3]. With the increase in computational power, it has become a pervasive and versatile technique in basic sciences and engineering. It uses random sampling for solving both deterministic and stochastic problems, as found in physics, biology, chemistry, or artificial intelligence [4-10]. Monte Carlo techniques also allow to assess risk in quantitative analysis and decision making [11, 12], and their methodological developments provide tools for economy, epidemiology or archaeology [13]. It is then crucial to understand the type of errors which can be introduced as a consequence of the incomplete convergence of such algorithms. Our interest goes to Markov Chain Monte Carlo techniques [14, 15], that create correlated random samples from a target distribution; a special emphasis is put on the relaxation rate of these methods. From the target probability distribution, a sequence of samples is obtained by a random walk, with appropriate transition probabilities. The walker's density evolves at long times towards the target distribution, and quantities of interest follow from the law of large numbers and other methods of statistical inference [11-19]. The Monte-Carlo method and its modern developments [20-30] have now been adopted in many topics in and outside physics.