Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans
This work addresses the challenge of principled and efficient auditing of redistricting plans for policymakers and researchers, though it appears incremental as it builds on existing sampling methods with a novel adaptation.
The paper tackles the problem of slow mixing times in sampling algorithms for generating ensembles of redistricting plans, which are needed for auditing partisan bias. The authors introduce a multiscale parallel tempering approach that achieves fast mixing on a policy-based distribution at the scale of the state of Connecticut, enabling sampling that was previously infeasible.
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.