Convergence and refinement of the Wang–Landau algorithm


Abstract

Recently, Wang and Landau proposed a new random walk algorithm that can be very efficiently applied to many problems. Subsequently, there has been numerous studies on the algorithm itself and many proposals for improvements were put forward. However, fundamental questions such as what determines the rate of convergence has not been answered. To understand the mechanism behind the Wang–Landau method, we did an error analysis and found that a steady state is reached where the fluctuations in the accumulated energy histogram saturate at values proportional to [log(f)]−1/2. This value is closely related to the error corrections to the Wang–Landau method. We also study the rate of convergence using different “tuning” parameters in the algorithm.

PACS

  • 05.10.Ln;
  • 65.40.Gr;
  • 02.50.-r

Keywords

  • Monte Carlo;
  • Density of states;
  • Random walk

1. Introduction

Computational methods have been used extensively for solving complex problems in the past few decades. In particular, in statistical physics equilibrium quantities of a system with many degrees of freedom are measured. The framework of statistical physics is formalized such that all equilibrium quantities can be derived from the partition function,

equation1
View the MathML source
σ is the state of the system, E is the energy corresponding to σ  , kB is the Boltzmann constant and T is the temperature. The summation is over all possible states and the number of possible states is a colossal number which cannot be enumerated. Nevertheless, computational methods such as Monte Carlo techniques [1] are used to sample the partition function; in particular, Metropolis importance sampling [2] has achieved considerable success. However, new techniques are emerging and are replacing the Metropolis importance sampling, especially near phase transition boundaries where the Metropolis importance sampling becomes inefficient. A class of new techniques, called generalized ensemble methods, such as the multicanonical method [3] and [4], the broad histogram method [5] and the flat histogram method [6] and [7], were developed based on re-writing the partition function as a sum over energies
equation2
View the MathML source
where the partition function is reduced from a sum over all states to a sum over ∼N   energy levels. The partition function would be tractable if the energy density of states g(E) could be calculated.

Recently, a systematic, iterative, random walk method [8], [9] and [10] has been proposed as one of the generalized ensemble methods. Now generally known as the Wang–Landau algorithm, it has received much attention in literature and has been applied to a wide range of problems [11], [12], [13] and [14]. There have also been numerous proposed improvements and studies of the efficiency of this method [15], [16], [17], [18], [19], [20], [21], [22] and [23]; however, there are still many unanswered questions, e.g., what determines the rate of convergence to the true density of states and is there any universality behavior related to this algorithm? In this paper, we attempt to quantify the mechanism behind the Wang–Landau method and study the effects of using different “tuning” parameters.