In Wang Landau method, how can I avoid large entropy difference?

Question

Summary: In Wang Landau method, you have to calculate the probability $\exp (- \Delta S)$ but $\Delta S$ is generally large when the size of the system is not small. How can I make $\Delta S$ small?

---

I'm writing a monte carlo simulation with Wang and Landau algorithm. When the size of the system is small, the density of states is correctly gotten. However, when the size is large (*1), much more iterations are needed to flatten the energy histogram and thus the entropy of each energy bin becomes large. For example, when the entropy refinement parameter $f = 1.0$ (note this is the initial value), the energy histogram $H$ is given as below.

H[0] = 618479
H[1] = 619151
H[2] = 620313
H[3] = 620378
H[4] = 620409
H[5] = ...

And entropy $S$ is also given as below. (Since $f = 1.0$ now, $H$ and $S$ have the same values.)

S[0] = 618479
S[1] = 619151
S[2] = 620313
S[3] = 620378
S[4] = 620409
S[5] = ...

These histograms seem flat enough, but the difference of elements is of order $O(1000)$. We have to decide whether or not to accept the suggested new states with probability $\exp (- \Delta S)$, but this is zero when $\Delta S$ is large. So the only states whose $S$ is small are accepted and the algorithm doesn't proceed at all.

How can I solve this problem? I think it is not practical to wait until the histogram becomes completely flat. I wonder if there is a more feasible solution.

---

Footnote

(*1): I assume $L \times L$ grid graph. I can compute $L \leq 9$ but not $L \geq 10$. You may think $10 \times 10$ grid graph is "not large", though.

---

Supplement

• Actually I'm trying to estimate the number of rook paths of a grid graph, using Wang Landau method rather than strict enumeration. The system is $(L + 1)^2$ nodes placed on a grid (Fig.1). Nearest neighbors are randomly linked. We propose a new state by choosing one (virtual) edge, and flip it (Fig.2) (i.e. if there is a edge there, cut it, and if there isn't, create a new edge). In the ground state, the edges constitute a path which links first node (upper left) and last node (lower right). This is just my challenge, and not an existing model.

• The histograms above were gotten in a few minutes on my personal computer. I don't know this is long or short, but at least in $L \leq 9$ case (in which histograms are gotten in dozens of seconds or so), the estimated number of solutions are very similar to the true one. So I think my model isn't bad...

Answer 1

The effective entropy function $S(E)$ used in the Wang-Landau algorithm is, like the true thermodynamic entropy, an extensive quantity. In general terms, there's nothing you can do about that. You want the sampling to be inversely proportional to the density of states $\Omega(E)=\exp[S(E)]$, in $k_B=1$ units. Ultimately, the method will become impractical for large enough systems.

However, I don't think that's the problem here. I suspect that you are simply running the first stage of Wang-Landau for too long. A typical flatness criterion is when the minimum histogram value comes within, say, 95% of the average value: $\min[H(E)]>0.95 \,\overline{H(E)}$. For a typical test system (2D Ising model on a $10\times 10$ lattice using single spin updating) I would achieve this flatness after visiting each energy around $2000$ times (there are about $100$ distinct energies). The range of histogram values between max and min is around $350$, but the differences between nearby histogram entries are in the range $1\leq \Delta S\leq10$, and this is the quantity of interest to the MC algorithm. So, I've only done $\sim 200000$ spin flips at that stage.

At this point, it is necessary to reduce the entropy-updating factor, reset the histograms, and continue to stage 2, and then similarly onwards until you've reached the desired convergence criterion for $f$. At each stage, typically, the computational effort to achieve the 95% flatness criterion goes up, as the entropy histogram is refined. For my Ising model, after $40$ or so stages, I've invested of order $10^8$--$10^9$ spin flips in total, but the overwhelming majority of the effort comes in the latter stages, each of which might take $100$ times longer than the first stage.

You seem to be visiting each energy more than $600000$ times in the first stage! So, I think the statistical fluctuations on numbers of that size will be working against you. When the system becomes stuck, it needs to accumulate $\sim 1000$ "hits" before it can escape. But this may mean that it is $\sim 1000$ units adrift from other neighbouring states.

I recommend trying again, but implementing the flatness criterion in the usual way, to reduce the entropy updating factor and proceed to the next stage, so your system progressively refines the entropy weights.

Answer 2

Now I've just found the solution. What's wrong was the interval of the flatness check. As I noted in my question, when the size is large, much more iterations are needed to flatten the energy histogram ($=$ there are larger number of distinct energy states), so I had to dynamically change the interval according to the value of $L$ rather than fix it to some constant value. In my case, if $L < 10$, the interval was $10^4$ monte carlo steps. But this was not appropriate for $L \geq 10$. So I set $10^5$ or even $10^6$ monte carlo steps as the interval, and then the problem solved. (Note this modification doesn't change the calculation time since much more iteration are needed to flatten the histogram.) I'm calculating the case of $L = 11, 12, \cdots$ and I'm getting plausible results.