Algorithmic Redistricting: How to Use Simulation Methods for Analyzing Large Datasets
Over Winter Term I had the opportunity to take a class on how mathematics plays a role in gerrymandering and redistricting elections. This got me thinking can we use mathematical and statistical concepts in drawing these districts? This blog explores how I used Markov Chain Monte Carlo simulations can to detect gerrymandering and create fairer electoral maps.
February 7, 2025 · 4 min read
Link to the original codebase : Here
1. Why Use MCMC?
Redistricting involves assigning geographic units, such as precincts or wards, to districts while maintaining equal population, contiguity, and legal constraints. The number of possible redistricting plans is astronomically large, making brute-force analysis impractical. MCMC sampling provides a practical alternative by exploring a representative subset of potential maps in a statistically meaningful way.
2. How MCMC Generates District Plans
MCMC is a probabilistic sampling method that iteratively modifies a districting plan to create a sequence of plans that represent the space of all valid maps. The process involves:
Graph Representation: A district map is represented as a graph, where nodes are geographic units and edges indicate adjacency. The graph is stored as an adjacency list to optimize computational efficiency.
Minimum Spanning Trees (MSTs): To efficiently generate redistricting plans, we construct MSTs that group adjacent geographic units while maintaining contiguity. MSTs help ensure that districts are formed in a way that minimizes unnecessary fragmentation. The MST is built using Kruskal's or Prim's algorithm to find the minimum set of edges needed to maintain connectivity.
Recombination (ReCom) Algorithm: This method merges and splits districts while ensuring population balance and contiguity. By cutting along MST edges, the algorithm creates new districts in a structured yet random manner. The ReCom step uses a spanning tree partitioning technique to maintain compactness.
Mathematical Constraints: The algorithm enforces criteria such as:
Population Equality: Each district must be within a specified deviation from the ideal population size.
Geographic Contiguity: All units within a district must be connected.
Compactness Measures: Metrics like Polsby-Popper and Schwartzberg ratio are used to ensure districts are not overly irregular.
By running the GerryChain library, we generate thousands of alternative districting plans efficiently. These plans serve as a benchmark to compare an existing plan against neutral alternatives.
Evaluating Districting Plans Using MCMC
Once we generate an ensemble of districting plans, we analyze key metrics to assess fairness. MCMC provides insights into how an observed districting plan compares to thousands of randomly drawn alternatives.
1. Using Minimum Spanning Trees for Random Sampling
Minimum spanning trees play a crucial role in district generation. By leveraging MSTs, the recombination algorithm can:
Reduce the number of unnecessary cuts while maintaining contiguity.
Ensure that new districts maintain geographic coherence.
Provide an efficient way to explore the space of possible districting plans while minimizing abrupt district boundary changes.
2. Mathematical Basis for Evaluating Outliers
We use statistical measures to compare the observed districting plan with the ensemble of neutral plans:
Standard Deviation & Z-Scores: Measures how far the observed seat distribution deviates from the mean.
Efficiency Gap Formula: EG=WastedPartyA−WastedPartyBTotalVotesEG = \frac{Wasted_{Party A} - Wasted_{Party B}}{Total Votes} where wasted votes are those beyond the necessary threshold to win or all votes for a losing candidate.
Mean-Median Score: MM=Mean(DemocraticVoteShare)−Median(DemocraticVoteShare)MM = Mean(Democratic Vote Share) - Median(Democratic Vote Share) A positive MM score suggests systematic bias.
3. Efficiency of MCMC Compared to Other Methods
Unlike traditional optimization techniques that may get stuck in local optima, MCMC ensures thorough exploration of the space of redistricting plans. It balances exploration and exploitation, allowing for a representative sample of valid plans within a reasonable computational time frame.
Advantages
Scalability: MCMC methods can analyze large datasets and explore complex districting spaces efficiently.
Statistical Rigor: By generating thousands of districting plans, we obtain robust, data-driven insights into potential biases.
Flexibility: MCMC can accommodate a variety of constraints, making it adaptable to different redistricting criteria.
Challenges
Computational Demands: While MCMC is more efficient than exhaustive search, generating thousands of maps still requires significant processing power.
Parameter Sensitivity: The effectiveness of MCMC depends on well-chosen parameters, such as the number of iterations and sampling methods.
Legal and Policy Implications: While MCMC provides statistical evidence of gerrymandering, its adoption in policy decisions depends on legal and political considerations.
As computational power increases and redistricting challenges become more complex, MCMC will continue to be a crucial tool for evaluating electoral fairness. By integrating MCMC with machine learning and geospatial analysis, researchers and policymakers can refine redistricting methods to promote fair representation.