When auditing a redistricting plan, a persuasive method is to compare the
plan with an ensemble of neutrally drawn redistricting plans. Ensembles are
generated via algorithms that sample distributions on balanced graph
partitions. To audit the partisan difference between the ensemble and a given
plan, one must ensure that the non-partisan criteria are matched so that we may
conclude that partisan differences come from bias rather than, for example,
levels of compactness or differences in community preservation. Certain
sampling algorithms allow one to explicitly state the policy-based probability
distribution on plans, however, these algorithms have shown poor mixing times
for large graphs (i.e. redistricting spaces) for all but a few specialized
measures. In this work, we generate a multiscale parallel tempering approach
that makes local moves at each scale. The local moves allow us to adopt a wide
variety of policy-based measures. We examine our method in the state of
Connecticut and succeed at achieving fast mixing on a policy-based distribution
that has never before been sampled at this scale. Our algorithm shows promise
to expand to a significantly wider class of measures that will (i) allow for
more principled and situation-based comparisons and (ii) probe for the typical
partisan impact that policy can have on redistricting.

审计选区规划中的一个有说服力的方法是将该方案与一组中立绘制的选区计划进行比较，这些集合是通过在平衡的图分割上采样分布的算法生成的。我们生成了一种多尺度并行退火方法，在每个尺度上进行局部移动，该方法允许采用多种基于政策的衡量标准。我们在康涅狄格州进行了实证研究，并成功在前所未有的尺度上对尚未采样的基于政策的分布进行快速混合。我们的算法显示出扩展到更广泛的衡量标准的潜力，这将 (i) 允许更有原则性和情境基础的比较，并 (ii) 探索政策对选区划分的典型党派影响。