# Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans

arXiv: https://arxiv.org/abs/2008.06131 · HTML: https://mlsanity.com/paper/2008.06131/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2020.

## Built on by (most cited first, 8 of 8)

- [Liouville Flow Importance Sampler](https://mlsanity.com/paper/2405.06672/) (2024)
- [Revisiting Compactness for District Plans](https://mlsanity.com/paper/2501.02325/) (2025)
- [The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions](https://mlsanity.com/paper/2510.17714/) (2025)
- [Agentmandering: A Game-Theoretic Framework for Fair Redistricting via Large Language Model Agents](https://mlsanity.com/paper/2511.04076/) (2025)
- [Statistical Guarantees in the Search for Less Discriminatory Algorithms](https://mlsanity.com/paper/2512.23943/) (2025)
- [Fast and Effective Redistricting Optimization via Composite-Move Tabu Search](https://mlsanity.com/paper/2605.06682/) (2026)
- [Constituency Optimisation Through Hamiltonian Representation Of Mandates (COTHROM): Algorithmic Redistricting of Irish Election Boundaries](https://mlsanity.com/paper/2606.20637/) (2026)
- [Wasserstein Gradient Flows and Forward-Only Diffusion Are Not Enough for Multimodal Sampling](https://mlsanity.com/paper/2610.02081/) (2026)

## Abstract (arXiv)

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 maps with a moderate or large number of districts, incorporate realistic legal constraints, and accurately and efficiently sample from a selected target distribution. Unfortunately, most existing methods struggle in at least one of these areas. We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution. Because it draws many plans in parallel, the SMC algorithm can efficiently explore the relevant space of redistricting plans better than the existing Markov chain Monte Carlo (MCMC) algorithms that generate plans sequentially. 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. We find that the proposed algorithm converges faster and with fewer samples than a comparable MCMC algorithm. Open-source software is available for implementing the proposed methodology.