Towards derandomising Markov Chain Monte Carlo

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.

Weiming Feng

Assistant Professor

I am an Assistant Professor in the School of Computing and Data Science at The University of Hong Kong. My research in theoretical computer science focuses on sampling and counting algorithms, including Markov chain Monte Carlo methods, spatial mixing of Gibbs distributions, and computational phase transitions, with applications in statistics and learning theory.

Heng Guo

Reader

I am a Reader in Algorithms and Complexity in the School of Informatics at the University of Edinburgh. My research studies algorithms from a complexity perspective, particularly computational counting and sampling.

Chunyang Wang

Postdoc

I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.

Jiaheng Wang

Postdoc

I am a HIIT Postdoctoral Fellow at the University of Helsinki, hosted by Mikko Koivisto. My research is in theoretical computer science, with a focus on algorithms and complexity for approximate counting and related combinatorial structures.

Yitong Yin

Professor

I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.