Performance Limitations of Flat-Histogram Methods

We determine the optimal scaling of local-update flat-histogram methods with system size by using a perfect flat-histogram scheme based upon the exact density of states of 2D Ising models. The typical tunneling time needed to sample the entire bandwidth does not scale with the number of spins $N$ as the minimal $N^2$ of an unbiased random walk in energy space. While the scaling is power law for the ferromagnetic and fully frustrated Ising model, for the $\pm J$ nearest-neighbor spin glass the distribution of tunneling times is governed by a fat-tailed Fréchet extremal value distribution that obeys exponential scaling. Furthermore, the shape parameters of these distributions indicate that statistical sample means become ill defined already for moderate system sizes within these complex energy landscapes.

Figure 1

Scaling of tunneling times $\tau$ from the ground state to the anti–ground state as a function of system size $L$ for a perfect flat histogram method that samples using the exact density of states. Shown are results for the ferromagnet (FM) and fully frustrated (FF) 2D Ising models with both local and $N$-fold way updates; the inset illustrates the frustrated couplings. In all cases polynomial scaling $\tau \propto L^{2d+z}$ is found, with $z_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}^{\mathrm{F}\mathrm{M}}=0.743\pm 0.007$, $z_{N\mathrm{\text{−}}\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{d}}^{\mathrm{F}\mathrm{M}}=0.729\pm 0.011$, $z_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}^{\mathrm{F}\mathrm{F}}=1.727\pm 0.004$, and $z_{N\mathrm{\text{−}}\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{d}}^{\mathrm{F}\mathrm{F}}=1.692\pm 0.004$.

Figure 2

Normalized distributions of tunneling times (left panels) and the ratio of the number of first excited states to the number of ground states $\rho (E_1)/\rho (E_0)$ (right panels). For both system sizes, $L=6$ and $L=16$, 1000 randomly generated 2D $\pm J$ spin glass realizations are sampled. The measured histograms of tunneling times (using local updates and the exact density of states) and $\rho (E_1)/\rho (E_0)$ both follow fat-tailed Fréchet distributions (solid lines).

Figure 3

Scaling of the parameters of Fréchet distribution of the tunneling times [see Eq. (1)] of the 2D $\pm J$ Ising spin glass using perfect flat histogram sampling as a function of system size $L$. Solid and dashed lines show least squares fits assuming exponential and algebraic (power law) scaling, respectively. The exponential fits of the data with $L\ge 8$ for $\mu$ and $\beta$ give ${\chi }^2=12$ and $7.6$, respectively, being significantly better than algebraic fits with ${\chi }^2=130$ and $61$, respectively. The inset shows the scaling of the shape parameter.

Figure 4

Correlation between tunneling times and ratios of the number of first excited states to the number of ground states $\rho (E_1)/\rho (E_0)$. Shown are data from 1000 randomly generated 2D $\pm J$ spin glass realizations of fixed system size $L=16$.

Figure 5

Evolution of the tunneling times $\tau$ during the calculation of the density of states using the Wang-Landau algorithm. Main panel: 2D Ising ferromagnet; inset: typical samples for the 2D $\pm J$ spin glass. For each system size the tunneling times are averaged over $50$ (FM), respectively $500$ (SG) independent runs, and are given in units of the average tunneling time ${\tau }_{\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{c}\mathrm{t}}$ measured using the exact density of states.