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.