Performance limitations of flat-histogram methods -: art. no. 097201

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 +/-J nearest-neighbor spin glass the distribution of tunneling times is governed by a fat-tailed Frechet 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.