Although Monte Carlo calculations using Importance Sampling have matured into the most widely employed method for determining first principle results in QCD, they spectacularly fail for theories with a sign problem or for which certain rare configurations play an important role. Non-Markovian Random walks, based upon iterative refinements of the density-of-states, overcome such overlap problems. I will review the Linear Logarithmic Relaxation (LLR) method and, in particular, focus onto ergodicity and exponential error suppression. Applications include the high-state Potts model, SU(2) and SU(3) Yang-Mills theories as well as a quantum field theory with a strong sign problem: QCD at finite densities of heavy quarks.

15 pages, 14 figures. Plenary talk presented at the 34th International Symposium on Lattice Field Theory, 24-30 July 2016, University of Southampton, UK, added references, corrected typos