Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
复制标题
图分区蒙特卡罗采样的都市森林重组
DOI：
10.1137/21m1418010
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Mattingly
中科院分区：
文献类型：
--
作者：
E. Autry;Daniel Carter;G. Herschlag;Zach Hunter;J. Mattingly
我们在图形分区上开发了一个新的马尔可夫链，该链使相对全局的移动在计算上是可行的，可以用作大都市束缚方法的建议。我们生成的算法可以使其可逆，并能够从分区的指定度量中采样。这两种属性对于某些重要的应用程序和计算贝叶斯统计数据至关重要。我们的提案链修改了最近开发的称为重组（ROCOM）的方法，该方法绘制了在连接分区上跨越树，然后将它们随机切割为重新分配。我们通过从分区到跨越森林的状态空间来提高计算效率。额外的信息加速了向前和向后提案概率的计算。我们通过对重新划分计划进行抽样来证明这种方法，并在几个关键的观察物中找到有希望的融合结果。
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.
在马尔可夫链测试中将效果与显着性分开
影响因子：
1.6
作者：
Chikina, Maria;Frieze, Alan;Mattingly, Jonathan C.;Pegden, Wesley
通讯作者：
Pegden, Wesley
DOI：
10.1073/pnas.1617540114
发表时间：
2017-03-14
影响因子：
11.1
作者：
Chikina, Maria;Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley