In statistics and physics, multicanonical ensemble (also called multicanonical sampling or flat histogram) is a Markov chain Monte Carlo sampling technique that uses the Metropolis–Hastings algorithm to compute integrals where the integrand has a rough landscape with multiple local minima.
on the energy spectrum is exponentially difficult to overcome.
[1] Systems with multiple local energy minima like the Potts model become hard to sample as the algorithm gets stuck in the system's local minima.
Multicanonical ensemble uses the Metropolis–Hastings algorithm with a sampling distribution given by the inverse of the density of states of the system, contrary to the sampling distribution
This leads to an algorithm for which the energy barriers are no longer difficult to overcome.
This is a great improvement in the study of first order phase transitions.
[1] The biggest problem in performing a multicanonical ensemble is that the density of states has to be known a priori.
[2][3] One important contribution to multicanonical sampling was the Wang and Landau algorithm, which asymptotically converges to a multicanonical ensemble while calculating the density of states during the convergence.
[2] The multicanonical ensemble is not restricted to physical systems.
It can be employed on abstract systems which have a cost function F. By using the density of states with respect to F, the method becomes general for computing higher-dimensional integrals or finding local minima.
and a "cost" function F from the system's phase-space to a one-dimensional space
is then given by When the system has a large number of degrees of freedom, an analytical expression for
is often hard to obtain, and Monte Carlo integration is typically employed in the computation of
On the simplest formulation, the method chooses N uniformly distributed states
by the strong law of large numbers: One typical problem of this convergence is that the variance of Q can be very high, which leads to a high computational effort to achieve reasonable results.
Generally, Monte Carlo methods' idea is to use importance sampling to improve the convergence of the estimator
In Monte Carlo, the canonical ensemble is defined by choosing
In this situation, the estimator corresponds to a simple arithmetic average: Historically, this occurred because the original idea[6] was to use Metropolis–Hastings algorithm to compute averages on a system in contact with a heat bath where the weight is given by the Boltzmann factor,
One situation where the canonical ensemble is not an efficient choice is when it takes an arbitrarily long time to converge.
[1] One situation where this happens is when the function F has multiple local minima.
The computational cost for the algorithm to leave a specific region with a local minimum exponentially increases with the cost function's value of the minimum.
One way to avoid becoming stuck in local minima of the cost function is to make the sampling technique "invisible" to local minima.
The multicanonical ensemble is defined by choosing the sampling distribution to be where
Like in any other Monte Carlo method, there are correlations of the samples being drawn from
A typical measurement of the correlation is the tunneling time.
The tunneling time is defined by the number of Markov steps (of the Markov chain) the simulation needs to perform a round-trip between the minimum and maximum of the spectrum of F. One motivation to use the tunneling time is that when it crosses the spectra, it passes through the region of the maximum of the density of states, thus de-correlating the process.
On the other hand using round-trips ensures that the system visits all the spectrum.
Because the histogram is flat on the variable F, a multicanonic ensemble can be seen as a diffusion process (i.e. a random walk) on the one-dimensional line of F values.
[7] This implies that the tunneling time, in local dynamics, should scale as a diffusion process, and thus the tunneling time should scale quadratically with the size of the spectrum, N: However, in some systems (the Ising model being the most paradigmatic), the scaling suffers from critical slowing down: it is
However, it is still an open question whether there is a local dynamics that does not suffer from critical slowing down in spin systems like the Ising model.