We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions. Both of these properties are critical to some important applications and computational Bayesian statistics in general. Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the state space from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities. We demonstrate this method by sampling redistricting plans and find promising convergence results on several key observables of interest.
翻译:我们在图形分区上开发一个新的Markov链条,使相对全球移动,但在计算上是可行的,可以用作大都会-哈斯廷斯法中的建议。我们所产生的算法可以被逆转,并且能够从分区的某一特定测量中取样。这两个属性对于一些重要的应用和一般的计算巴耶斯统计至关重要。我们的建议链条修改了最近开发的称为再组合(ReCommination)的方法,该方法在连接的分区上画树,然后随机将其切换为再分割。我们通过扩大从分区到横跨森林的状态空间来提高计算效率。额外信息加快了前向和后向建议概率的计算。我们通过取样重新分区计划来展示这一方法,并在一些关键的兴趣观测中找到有希望的趋同结果。