Wang and Landau Algorithm - Algorithm

Algorithm

Consider a system defined on a phase space, and a cost function, E, (e.g. the energy), bounded on a spectrum, which has an associated density of states, which is to be computed. Because Wang and Landau algorithm works in discrete spectra, the spectrum is divided in N discrete values with a difference between then of, such that

.

Given this discrete spectrum, the algorithm is initialized by:

• setting all entries of the entropy to zero,
• initializing and
• initializing the system randomly, by putting in a random configuration .

The algorithm then performs a multicanonical ensemble like simulation: a Metropolis-Hastings random walk in the phase space of the system with a probability distribution given by and a probability of proposing a new state given by a probability distribution . A histogram of visited energies is stored. Like in the Metropolis-Hastings algorithm, a proposal-acceptance step is performed, and consists in (see Metropolis–Hastings algorithm overview):

1. proposing a state according to
2. accept/refusing the proposed state according to

where and .

After each proposal-acceptance step, the system transits to some value, is incremented by one and the following update is performed:

.

This is the crucial step of the algorithm, and it is what make this Wang and Landau algorithm non-markovian: the stochastic process now depends on the history of the process. Nevertheless, the next time there is a proposal to a state with that particular energy, that proposal is now more likely refused; in this sense, the algorithm forces the system to visit all the spectrum equally. The consequence is that the histogram is more and more flat. However, this flatness depends on how well approximated the calculated entropy is to the exact entropy, which naturally depends on the value of f. To better and better approximate the exact entropy (and thus histogram's flatness), f is decreased after M proposal-acceptance steps:

.

It was latter shown that updating the f by constantly dividing by two can lead to saturation errors. A small modification to the Wang and Landau method to avoid this problem is to use the f factor proportional to, where is the number of steps of the simulation.