Metropolis–Hastings algorithm

The Metropolis algorithm is a Monte Carlo method for the generation of states of a system according to the Boltzmann distribution. The derived more general Metropolis -Hastings algorithm makes it possible to simulate sequences of random variables, more precisely Markov chains, which have a desired distribution as stationary distribution, in particular, in many cases where can not be simulated directly for distribution random variables.

Metropolis algorithm

The Metropolis algorithm was founded in 1953 by Nicholas Metropolis et al. published. It is used to produce a Markov chain, so that the states of a system according to the Boltzmann distribution. Here, the new state of the system depends only on the previous state.

In the following the algorithm is described for the case that the system depends on a multi-dimensional location. is continuous and the current location after iterations is denoted by. The Metropolis algorithm is then obtained by repeating the following steps:

• Is the new position so energetically equivalent or more favorable, is accepted as the new current location in each case.
• Is the new position so energetically less favorable, on the other hand is only accepted with probability as the new current location, to which you practically a random number q determined between 0 and 1, and then compares it with: If q is less than, is accepted as the new current location, otherwise not know.

Small values ​​of | r | result is in a large acceptance rates, however, have the disadvantage of high autocorrelation times

Large values ​​of | r | While on the other hand reduce the autocorrelation time, but now have the disadvantage of a lower acceptance rate, so that in practice a balance must be sought always.

The method described above can be easily to other cases such as transmit discrete states. For systems of many interacting particles of the Metropolis algorithm is first applied locally for a single particle and then - either sequentially or randomly - on all particles.

Metropolis -Hastings algorithm

W. Keith Hastings generalized the method in 1970. The Metropolis -Hastings algorithm can produce states for an arbitrary probability distribution. The only requirement is that the density can be calculated at any location. The algorithm uses a proposal density that depends on the current location and possible next place. In the Metropolis -Hastings algorithm, a proposal is randomly generated based on the proposal density and accepted with probability.

For a proposal density that is constant and zero otherwise in a fixed interval around the current location, as well as a Boltzmann distribution as a probability distribution results from this, the original Metropolis algorithm.

Applications

Monte Carlo simulation

In Monte Carlo simulations configurations are generated by means of the Metropolis algorithm and mean values ​​/ expectation values ​​of physically relevant quantities calculated, such as the expectation value of the pressure or density:

With and

These are first executed so many of the iterations of the Metropolis algorithm until the system has sufficiently approximated close to thermal equilibrium, ie to the likelihood of each configuration of the Boltzmann distribution corresponds. If the system is in thermal equilibrium, so the probability distribution corresponds to the Boltzmann distribution, ie the configurations are generated with probability ( importance sampling ) and it only has about every measurement, or measurement values ​​are at a constant distance, averaged.

The Metropolis algorithm generates systems in the canonical state, ie at a constant temperature. To produce microcanonical conditions molecular dynamics algorithms can be used.

In the original work by Nicholas Metropolis et. al. the algorithm for Monte Carlo simulation of a two-dimensional hard - disk model was used. The algorithm was later nominated for a multitude of different Monte Carlo simulations in areas such as used in thermodynamics and statistical physics, solid state physics, quantum electrodynamics or quantum chromodynamics. In this case, the algorithm needs to be adjusted, where appropriate; For example, you have to replace the energy described by the Hamiltonian or the action.

The Metropolis algorithm is easy to implement, but not always the most efficient algorithm. Alternatively can be used other local or non-local process.

Optimization methods

The Metropolis algorithm can also be used as a stochastic optimization method for finding a global minimum values ​​of a landscape. To this end, starting with a high temperature, so that as a large area of ​​landscape values ​​is visited. The temperature is then lowered slowly, so you faced with increasingly higher probability approaches a minimum. Such a Metropolis algorithm with inverse of the ( simulation ) time temperature is called simulated annealing ( simulated annealing ). For certain forms of simulated annealing could be proved that they find the global minimum of a value system.

The procedure is similar to the climber algorithm (hill climbing ) but accepts as opposed to this also steps away from the nearest minimum, so that is " getting stuck " in avoiding local minima that are not yet yield the absolute minimum. The Metropolis algorithm overcomes so small hill before proceeding towards the valley, as the increase is small in the direction of hill and thus the acceptance probability is relatively large.