论文标题
关于采样重新划分计划的复杂性
On the Complexity of Sampling Redistricting Plans
论文作者
论文摘要
政治重新划分问题的至关重要的任务是对重新划分计划进行采样，即将人口普查块的图表分配到地区。 我们证明了重组[Deford-Duchin-Solomon'21] - 一种流行的Markov链，用于采样重新分配计划 - 在$ \ Mathbb {Z} _2的简单子图上呈指数速度的速度混合。
A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of $\mathbb{Z}_2.$ We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.
