The Wang-Landau algorithm reaches the flat histogram criterion in finite time (Q2443184)

The paper considers a punctual problem: to prove that in some circumstances a particular update used in implementations of the Wang-Landau algorithm (general version defined by \textit{Y. F. Atchadé} and \textit{J. S. Liu} [Stat. Sin. 20, No. 1, 209--233 (2010; Zbl 1181.62022)]) assures more performance than another one. In more detail, this Markov chain Monte Carlo (MCMC) algorithm analyses samples from a set of states in order to be correlated to a distribution defined by the user, by penalizing regions already visited and giving preference for choosing unexplored regions, the final goal being to cover all considered regions. The vector of ``penalties'' uses -- in practical implementations -- two forms of updates (considered in the paper as update (1) and update (2)). For decreasing the scheduling of choices in a certain random time, a ``flat histogram'' (FH) criterion is used. The main result is that in some natural assumptions (4 in the two states model, 5 for more than the two states model) -- used to clarify proofs -- the FH criterion is met in finite time only by update (1). The paper is very specialized, useful only for specialists. But the result is important in implementations of this type of Monte Carlo algorithms, by showing the best choice of updates of penalties vectors for practical results (in theoretical research the choice of the form of the penalties vector is not important).