Stratified sampling method for complex redistricting plans introduced
Towards stratified sampling for redistricting plans
Computers and Society
Summary
Choosing fair ways to divide areas into voting districts is complicated because there are so many possible plan combinations. The authors propose a method to group similar plans into categories using a new language made of district clusters. This helps organize and estimate the importance of different groups of plans, creating a base for improved sampling techniques in future work. They tested their approach using real data from Connecticut's congressional districts but did not yet complete or test the full sampling method.
What this means in practice
- •For political data analysts: Use the proposed clustering-based framework to create strata for organizing large sets of redistricting plans and improve future sampling approaches.
- •For graph partitioning software engineers: Incorporate soft assignment of partitions into strata definitions to better estimate subspace sizes and transitions in large combinatorial spaces of balanced graph partitions.
Tested on one dataset.
Authors
Zijian Wang, Gregory J. Herschlag, Joon-Hyeok Yim, Jonathan C. Mattingly, Anna C. Gilbert
Abstract
Rapid algorithmic developments have accelerated the sampling of redistricting ensembles (balanced graph partitions), yet evaluating rare events and sampling complex target measures remains a core challenge due to the high-dimensional and combinatorial nature of the phase space. We address a prerequisite for stratified sampling on this space: constructing and diagnosing candidate strata with suitable coverage and overlap. We build a grammar on observed plans by clustering districts into representative ``letters'' and using them to form plan-level ``words.'' A partition of unity over these words gives a soft assignment of plans to strata and allows us to estimate stratum masses and an overlap-induced flux matrix. We demonstrate this computational pipeline using real-world congressional redistricting data from Connecticut and examine how strata learned from one target distribution behave under related distributions. The resulting construction provides a foundation for future stratified sampling on spaces of redistricting plans or balanced graph partitions. We do not implement a complete stratified sampler here; evaluating whether the proposed strata improve sampling efficiency or reduce estimator variance is left for future work.