Source-linked AI summary
Recombination: A family of Markov chains for redistricting
Daryl DeFord, Moon Duchin, Justin Solomon
TL;DR
Redistricting analysis must reason over an enormous space of valid plans while translating vague legal and political criteria into workable models. The paper formulates redistricting as graph partitioning, introduces ReCom as an alternative to Flip, and finds efficient, stable sampling in experiments, while noting unresolved mixing and stationary-distribution theory.
Problem
The number of valid districting plans is too large to enumerate, making representative sampling important for comparing proposed plans with viable alternatives.
Method
The paper models plans as connected graph partitions and introduces ReCom Markov chains, comparing them with single-unit Flip proposals.
Results
ReCom ensembles show qualitatively broader outcomes than Flip in an extreme example and remain stable across trials and starting points in experiments.
Takeaways & Limitations
Ensemble-based analysis can place districting plans in the context of diverse alternatives and assess properties such as partisan balance, shape, and demographics.
Takeaways & Limitations
Precise characterization of ReCom and Flip stationary distributions remains extremely challenging, and rigorous mixing-time bounds are generally unavailable.
Abstract
from arXiv · showhide
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.
1 Introduction
Redistricting requires exploring an enormous space of valid districting plans, motivating randomized ensembles and Markov chains for comparison. The paper introduces ReCom as an alternative to Flip and presents evidence of improved mixing, stability, and practical usefulness.
- Motivation: Valid districting plans are too numerous to enumerate, even after imposing contiguity and legislative or commission criteria.The space can reach googol-scale sizes.
- Motivation: Ensembles sample valid alternatives so proposed plans can be compared with the range of possible district properties.Outlier analysis has been used in legal challenges to partisan gerrymanders.
- Contribution: ReCom is a new Markov-chain family on graph partitions that is designed for redistricting and compared with the single-unit Flip walk.ReCom recombines districts, whereas Flip changes a geographic unit’s neighboring-district label.
- Contribution: ReCom provides evidence of efficient mixing toward distributions consistent with traditional districting criteria, with little or no user parameter tuning.The authors contrast this with slow-mixing Flip chains.
- Experiments: Real-data experiments examine qualitative sampling behavior, including simulated annealing and parallel tempering, and include a Virginia House of Delegates case study.The paper also supplies an open-source ReCom implementation.
- Limitations of prior approaches: Flip’s local proposals can leave the initial map structure visible after 1 million steps and may require substantially more steps for reliable samples.The paper cautions that customized litigation implementations are not reproduced exactly.
2 Markov chains
The paper uses MCMC to sample redistricting plans while relying on Markov-chain convergence theory and diagnostics. It contrasts the familiar local Flip proposal with ReCom, which produces quality ensembles on full-scale problems despite unresolved theoretical limits.
- Markov-chain foundations: A Markov chain moves through a state space using a transition rule whose next-state probability depends only on the current state.MCMC methods use such chains for statistical sampling.
- Markov-chain foundations: Ergodic chains converge from any initial state to a unique stationary distribution, while mixing time measures the steps needed to reach a chosen closeness threshold.Rigorous mixing-time bounds are rare in applications.
- Markov-chain foundations: Reversible chains enable stronger theorems about assessing stationarity before the sampling distribution fully approaches its stationary target.These tools do not eliminate distribution-design and user-choice sensitivity.
- Flip and ReCom: Flip reassigns one geographic unit to a neighboring district, whereas ReCom uses a spanning-tree-based alternative proposal.The paper identifies basic Flip’s disadvantages as slow mixing and undesirable stationary-distribution properties.
- Empirical performance: ReCom chains of tens of thousands of steps produce full-scale ensembles that pass many convergence and distributional-design tests.Depending on the data, runs take hours to a few days on a standard laptop.
3 Setting up the redistricting problem
The paper models redistricting as partitioning a geographic dual graph into connected districts, then formulates practical rules and priorities as modeling choices. This framework supports sampling from a vast but operationally constrained plan space.
- 3.1 Redistricting as a graph partition problem: A geographic partition becomes a dual graph with one vertex per unit and edges joining geographically adjacent units.Iowa counties provide an example of this construction.
- 3.1 Redistricting as a graph partition problem: A districting plan partitions graph vertices into subsets inducing connected components, equivalently assigning each vertex one of k district labels.This recasts redistricting as graph partitioning.
- 3.1 Redistricting as a graph partition problem: Seed plans must be valid initial states, and flood-fill or spanning-tree methods can construct contiguous, tolerably population-balanced starts.Multiple seeds help test independence from the starting point.
- 3.2 Sampling from the space of valid plans: Even restrictive districting rules can leave enormous plan spaces: pairing Minnesota’s current House districts yields 6,156,723,718,225,577,984 valid Senate plans.This is over 6×10^18 plans under a narrow nesting interpretation.
- 3.2 Sampling from the space of valid plans: Population balance, contiguity, compactness, splitting, and minority-opportunity rules require operational modeling decisions because legal language is often imprecise.Compactness is represented by counting cut edges, interpreted as discrete perimeter.
- 3.2 Sampling from the space of valid plans: Tighter population-balance requirements can increase rejection rates and impede Markov-chain efficiency.The paper notes that ensembles with at most 1% deviation can still provide useful comparators in some congressional settings.
4 The flip and recombination chains
The paper formalizes districting plans as connected graph partitions and compares single-node Flip proposals with larger ReCom proposals. Flip is simple and reversible but can mix slowly under tight constraints, while ReCom accepts higher per-step cost for improved mixing and distributional properties.
- 4.1 Notation: A districting plan partitions graph vertices into k districts, with each district required to induce a connected subgraph.The validity function C checks whether a plan satisfies the selected constraints.
- 4.2 Flip proposals: Flip changes one boundary node’s district assignment at a time while preserving contiguity through rejection sampling.Proposals that fail contiguity or another constraint are regenerated from the previous state until one passes.
- 4.2.1 Node choice, contiguity, rejection sampling: Flip selects uniformly among boundary node–district pairs, producing a reversible chain whose stationary distribution weights plans by their boundary-pair counts.The resulting stationary distribution is non-uniform.
- 4.2.1 Node choice, contiguity, rejection sampling: Flip’s small perturbations aid explainability and stepwise computation but can leave the chain near its initial plan for extremely long runs.Under strict constraints, the state space may become disconnected for this proposal.
- 4.3 ReCom proposals: ReCom costs more computationally per step than Flip, but the paper argues that superior mixing and distributional properties make the tradeoff favorable.The paper also reports evidence for fast mixing and stable results with ReCom compared with Flip.
- 4.3 ReCom proposals: ReCom merges selected districts, forms their induced subgraph, and repartitions that region with a contiguity-preserving algorithm.The paper emphasizes bipartitioning because spanning-tree selection is slower on the full graph when k is large.
5 Theoretical comparison
The paper contrasts ReCom and Flip in both sampling behavior and computational tractability. ReCom favors compact plans and shows stable practical sampling, while Flip mixes slowly and uniform sampling is dominated by non-compact partitions.
- 5 Theoretical comparison: Precise mathematical characterization of the stationary distributions of Flip and ReCom remains extremely challenging and is still under active research.The paper therefore uses experiments and high-level explanations to characterize qualitative behavior.
- 5.1 Distributional design: compactness: ReCom preferentially samples compact districts, whereas Flip ensembles contain plans with long, winding boundaries.Compactness is evaluated here using discrete perimeter and related geometric features.
- 5.2 Complexity and mixing: ReCom appears to mix efficiently, while Flip mixes slowly; tens of thousands of ReCom steps produce stable results on practical-scale Pennsylvania and Virginia problems.The reported experiments involve roughly 9,000 Pennsylvania precincts and roughly 100,000 Virginia census blocks.
- 5.1 Distributional design: compactness: There are far more chaotic than regular partitions, and relaxing a boundary-size limit causes the number of grid bipartitions to grow exponentially.This numerical imbalance explains why uniform distributions concentrate near maximal boundary lengths.
- 5.1 Distributional design: compactness: ReCom uses spanning-tree cuts to produce connected subgraphs and down-weights skinny necks and tentacles because they admit fewer spanning trees.A district with a two- or three-node neck can reduce spanning-tree counts by factors of C^2 or C^3, making it ten or thirty times less likely to be selected.
- 5.2 Complexity and mixing: ReCom destroys the previous boundary between two districts at each step, suggesting that memory of the starting point may be lost in steps polynomial in k and independent of n.This conjectured behavior is notable because the state space of balanced k-partitions of an n × n grid is larger than exponential in n.
6 Experimental comparison
Experiments on grids and geographic dual graphs compare Flip with ReCom under unconstrained, constrained, weighted, and annealed sampling. Across these settings, Flip often mixes slowly or remains near its initial plan, while ReCom produces more compact and diverse ensembles.
- Experimental setup: Missouri census geographies yield dual graphs ranging from 115 to 343,565 nodes, illustrating the scale of the experimental inputs.The four graphs contain 115, 1,395, 1,393, and 343,565 nodes.
- Sampling distributions, with and without tight constraints: On Arkansas block-group graphs, Flip produced plans with upwards of 90% boundary nodes and roughly 45% cut edges, while ReCom stayed near the initial plan’s under-20% and around-5% values.The comparison holds across essentially the entire Flip run.
- Sampling distributions, with and without tight constraints: Tight constraints can keep Flip valid yet trapped near its initial plan, whereas ReCom responds better to sharp constraints and avoids tending toward limit values.Flip may repeatedly reassign the same boundary nodes or remain within a small connected component.
- Projection to summary statistics: Over 1,000,000 Flip steps, the synthetic-election ensembles primarily reported four seats or zero seats, while 10,000 ReCom steps produced three, four, or five seats and qualitatively agreed across scenarios.The Flip chain remained far from mixed after one million steps, so the experiment does not compare stationary distributions.
- Weighting, simulated annealing, and parallel tempering: Simulated annealing caused Flip walks on Tennessee and Kentucky block groups to return near their starting states because tendrils retracted while boundary assignments rarely changed.The modified Flip walk therefore failed to move effectively through the partition space.
- Weighting, simulated annealing, and parallel tempering: ReCom generates plans with relatively few cut edges by default, while direct attempts to make Flip plans more compact can impede exploration.The paper notes that weighted spanning-tree ReCom is not implemented with a full reversible Metropolis–Hastings algorithm.
7 Case study: Virginia House of Delegates
The Virginia case study uses ReCom-generated alternatives to evaluate whether elevated Black voting-age population in the enacted plan is explained by geography. The ensemble instead supports a packing-and-cracking pattern, while the authors caution that ensemble analysis does not stand alone.
- Case background: Virginia’s enacted 2011 House of Delegates plan was challenged in litigation concerning elevated Black voting-age population across districts.Courts found 55% BVAP unnecessarily elevated in 11 of 12 districts and associated dilution elsewhere.
- Comparison ensemble: The analysis compares the enacted plan with a large, diverse ensemble of alternatives generated without considering racial statistics.This provides a counterfactual beyond the limited set of human-made comparison plans.
- Chain comparison: Flip chains failed to produce diverse ensembles in the Virginia analysis, whereas ReCom chains passed quality tests involving compactness and convergence in racial or partisan projections.Figures 11–13 summarize these comparisons.
- Findings: ReCom comparisons indicate that the enacted plan’s BVAP pattern is not explained by Virginia’s human geography and is consistent with packing and cracking.Elevated BVAP in the top 12 districts coincided with depressed BVAP in the next four districts and the nine after them.
- Interpretive scope: The authors emphasize that ensemble analysis does not stand alone in assessing the Virginia plan.The supplied passage ends before specifying the accompanying evidence or qualification.
8 Discussion and Conclusion
The discussion emphasizes ensemble analysis as a practical way to compare districting plans against viable alternatives, while identifying substantial mathematical and computational questions that remain. ReCom shows repeatable measurements in experiments, but the broader methodology still faces open questions about theory, robustness, and adversarial behavior.
- Discussion and Conclusion: Ensemble analysis places districting plans in the context of diverse, representative alternatives across partisan balance, shape, and demographics.Extreme outliers may indicate that a plan reflects goals not incorporated into the model design.
- Discussion and Conclusion: Full enumeration is infeasible because the space of valid districting plans is extraordinarily large, making ensemble design mathematically, statistically, and computationally difficult.Comparator plans must remain legally viable and pragmatically plausible, and mixing times help assess whether MCMC samples the prescribed stationary distribution.
- Discussion and Conclusion: ReCom ensembles produced measurements that did not vary substantially across trials or new starting points in synthetic and observed-data experiments.The reported experiments included runs assembled over several days on a standard laptop.
- Open Questions: Open directions include proving rapid mixing and characterizing spanning-tree ReCom’s stationary distribution and boundary-length behavior.The authors also identify ergodicity and state-space diameter bounds as difficult open questions.
- Open Questions: Further work should test projection mixing, alternative balanced bipartitioning methods, parallelization, graph perturbation stability, and statistics for racial and partisan gerrymandering.The paper also raises whether adversaries could design plans that evade outlier detection under a known Markov proposal.
- Implementation: ReCom is distributed as open-source software with tools for map processing and MCMC-based plan analysis, alongside public code and data intended to support reproducibility and public trust.The release is presented as a model for open and reproducible redistricting-tool development.
A Plots for Virginia Case Study
The Virginia case-study figures examine ReCom and Flip ensembles through convergence, compactness, partisan statistics, and BVAP distributions. They show slow starting-point dependence for Flip and a shorter apparent convergence scale for ReCom, while comparing enacted-plan demographics with generated alternatives.
- BVAP comparison: Eight proposed plans are compared by ordering BVAP across the 33 districts affected by the court ruling, but their collection does not establish how many additional 37-55% BVAP plans are expected or possible.The enacted 2011 plan skips the key 37-55% BVAP range entirely.
- Convergence heuristics: 10 million Flip steps are not enough to mitigate starting-point dependence, whereas 20,000 ReCom steps seems sufficient, with most progress in the first 10,000.The comparison uses enacted-plan BVAP levels and two synthetically generated seed plans.
- Compactness comparison: Flip ensembles saturate the worst allowable compactness score, defined here as twice the enacted plan’s value.The figure compares boundary-length histograms and traces.
- Projection to partisan statistics: The partisan-statistics comparison uses mean-median scores to illustrate Flip ensembles’ dependence on starting point after one million steps.Mean-median is a signed measure of party advantage and a leading partisan metric in political science.
- Ensemble analysis: The ensemble analysis compares enacted-plan BVAP levels with population-balanced, compact plans preserving state demographics and geography, including a version winnowed to ≤60% BVAP.The figure presents both the full ReCom ensemble and the winnowed ensemble.