In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. There are influential Markov chain Monte Carlo methods for doing so that are based on sampling and splitting random spanning trees. Empirical evidence suggests that the distributions such algorithms sample from place higher weight on more "compact" redistricting plans, which is a practically useful and desirable property. In this paper, we confirm these observations analytically, establishing an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled. This result provides theoretical underpinnings for algorithms that are already making a significant real-world impact.

翻译：在设计和分析政治重新划区地图时,从人口普查区块图的所有分区空间取样到人口相等的相联子图中往往有用。有影响力的Markov连锁Monte Carlo这样做的方法是以采样和分解随机横贯树木为基础的。经验证据表明,这种算法样本从较“复杂”的重新划区计划较高重量的位置上进行分配,是一种实际有用和可取的财产。在本文中,我们从分析角度确认这些观察,在分隔地区边界的总长度与这种地图被采样的可能性之间建立反向指数关系。这一结果为已经产生重大真实世界影响的算法提供了理论依据。