Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation.
翻译：新型马尔可夫链蒙特卡罗（MCMC）方法通过图划分实现了大规模重划方案集合的生成。然而，现有算法如可逆重组（RevReCom）与Metropolized森林重组（MFR）仅限于采样与生成树相关的分布。本文提出标记边游走（MEW），这是一种用于在可调分布下从图划分空间采样的新型MCMC算法。该游走作用于带标记边的生成树空间，其可计算的转移概率可用于Metropolis-Hastings算法。在实际对偶图上的实证结果表明，该算法在与生成树无关的目标分布下具有收敛性。因此，MEW代表了灵活集合生成技术的重要进展。
相关内容
微信扫码咨询专知VIP会员