Towards stratified sampling for redistricting plans
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.
Related
- Post-stratified importance sampling
- Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
- Auxiliary-Driven Transformations for Efficient Mean Estimation Under Stratified Systematic Sampling
- All reweighted paths lead to Rome: Unification of reweighting schemes for stratified path sampling
- Expected Batch Optimal Transport Plans and Consequences for Flow Matching
BibTeX
@misc{wang2026towards,
title = {{Towards stratified sampling for redistricting plans}},
author = {Zijian Wang and Gregory J. Herschlag and Joon-Hyeok Yim and Jonathan C. Mattingly and Anna C. Gilbert},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18741},
eprint = {2609.18741},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18741},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards stratified sampling for redistricting plans
AU - Zijian Wang
AU - Gregory J. Herschlag
AU - Joon-Hyeok Yim
AU - Jonathan C. Mattingly
AU - Anna C. Gilbert
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18741
UR - https://arxiv.org/abs/2609.18741
AB - 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.
ER -