Towards derandomising Markov chain Monte Carlo
Preprint
Abstract
We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts.Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- Perfect sampling from spatial mixingRandom Structures & Algorithms, 2022
- Rapid mixing of hypergraph independent setsRandom Structures & Algorithms, 2018
- DNF sparsification and a faster deterministic counting algorithmcomputational complexity, 2013
- Left and right convergence of graphs with bounded degreeRandom Structures & Algorithms, 2012
- Deterministic random walks on regular treesRandom Structures & Algorithms, 2010
- Multivariate Fuss–Catalan numbersDiscrete Mathematics, 2008
- Path coupling using stopping times and counting independent sets and colorings in hypergraphsRandom Structures & Algorithms, 2008
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- A geometric inequality and the complexity of computing volumeDiscrete & Computational Geometry, 1986
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986