The Metropolis Algorithm

Abstract

The Metropolis Algorithm has been the most successful and influential of all the members of the computational species that used to be called the "Monte Carlo method". Today, topics related to this algorithm constitute an entire field of computational science supported by a deep theory and having applications ranging from physical simulations to the foundations of computational complexity. Since the rejection method invention (J. von Neumann), it has been developed extensively and applied in a wide variety of settings. The Metropolis Algorithm can be formulated as an instance of the rejection method used for generating steps in a Markov chain.