``Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans.''



Random sampling of graph partitions under constraints has become a popular tool for evaluating legislative redistricting plans. Analysts detect partisan gerrymandering by comparing a proposed redistricting plan with an ensemble of sampled alternative plans. For successful application, sampling methods must scale to large maps with many districts, incorporate realistic legal constraints, and accurately sample from a selected target distribution. Unfortunately, most existing methods struggle in at least one of these three areas. We present a new Sequential Monte Carlo (SMC) algorithm that draws representative redistricting plans from a realistic target distribution of choice. Because it yields nearly independent samples, the SMC algorithm can efficiently explore the relevant space of redistricting plans than the existing Markov chain Monte Carlo algorithms that yield dependent samples. Our algorithm can simultaneously incorporate several constraints commonly imposed in real-world redistricting problems, including equal population, compactness, and preservation of administrative boundaries. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania. Open-source software is available for implementing the proposed methodology.

  Related Papers and Software

Fifield, Benjamin, Michael Higgins, Kosuke Imai, and Alexander Tarr. (2020). ``Automated Redistricting Simulator Using Markov Chain Monte Carlo.''Journal of Computational and Graphical Statistics, Forthcoming.
Fifield, Benjamin, Kosuke Imai, Jun Kawahara, and Christopher T. Kenny. (2020). ``The Essential Role of Empirical Validation in Legislative Redistricting Simulation.'' Statistics and Public Policy, Forthcoming.
Fifield, Benjamin, Christopher T. Kenny, Cory MaCartan, Alexander Tarr, and Kosuke Imai. ``redist: Computational Algorithms for Redistricting Simulation.'' available through The Comprehensive R Archive Network and GitHub.

© Kosuke Imai
 Last modified: Tue Aug 18 09:09:51 EDT 2020