# Recombination: A family of Markov chains for redistricting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2019.

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

- [Many processors, little time: MCMC for partitions via optimal transport couplings](https://mlsanity.com/paper/2202.11258/) (2022)
- [Sampling-based techniques for designing school boundaries](https://mlsanity.com/paper/2206.03703/) (2022)
- [Memetic algorithms for Spatial Partitioning problems](https://mlsanity.com/paper/2208.02867/) (2022)
- [Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans](https://mlsanity.com/paper/2401.17455/) (2024)
- [Implications of Distance over Redistricting Maps: Central and Outlier Maps](https://mlsanity.com/paper/2203.00872/) (2022)
- [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)

## Abstract (arXiv)

Redistricting is the problem of partitioning a set of geographical units into a fixed number of districts, subject to a list of often-vague rules and priorities. In recent years, the use of randomized methods to sample from the vast space of districting plans has been gaining traction in courts of law for identifying partisan gerrymanders, and it is now emerging as a possible analytical tool for legislatures and independent commissions. In this paper, we set up redistricting as a graph partition problem and introduce a new family of Markov chains called Recombination (or ReCom) on the space of graph partitions. The main point of comparison will be the commonly used Flip walk, which randomly changes the assignment label of a single node at a time. We present evidence that ReCom mixes efficiently, especially in contrast to the slow-mixing Flip, and provide experiments that demonstrate its qualitative behavior. We demonstrate the advantages of ReCom on real-world data and explain both the challenges of the Markov chain approach and the analytical tools that it enables. We close with a short case study involving the Virginia House of Delegates.