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.

翻译：我们提出了一个新的框架来取消某些马可夫连锁蒙特卡洛(MCMC)算法。和MCMC一样,我们首先将计数问题降低到从边缘分布序列中取样。对于后一项任务,我们引入了一种称为与过去混合的方法,在对数时间中,可以评估固定的马尔科夫链状态的一或一不变数变量。由于大多数情况下存在对数随机选择,这导致非常简单的脱序。我们提供了这一框架的两个应用,即高压独立集和高压彩色集算法,在当地白麻类配对条件下,最高到更低的顺序系数,其最先进的随机对应方。