论文标题
朝向马尔可夫链蒙特卡洛
Towards derandomising Markov chain Monte Carlo
论文作者
论文摘要
我们提出了一个新框架，以使某些马尔可夫链蒙特卡洛（MCMC）算法取代。与MCMC一样，我们首先将计数问题减少到从边缘分布序列中进行取样。对于后一个任务，我们将一种称为“耦合的方法”引入了过去，在对数时间中可以评估一个或恒定数量的变量来自固定的马尔可夫链状态。由于最多有对数随机选择，因此这会导致非常简单的降低。我们提供了该框架的两种应用，即在局部引理类型条件下匹配的局部引理类型条件，最多可及其最先进的随机对应物。
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.
