The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
Pub. online: 28 October 2026
Type: Computing In Data Science
Open Access
Open Access
Received
13 November 2025
13 November 2025
Accepted
24 August 2026
24 August 2026
Published
28 October 2026
28 October 2026
Abstract
Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partitioning problem. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) have strong preferences for distributions related to the spanning tree measure. In this paper we introduce the Marked Edge Walk (MEW), a novel Markov chain proposal for sampling from the space of graph partitions. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under a broad class of target distributions less constrained by spanning tree counts, including policy-based distributions, such as competitiveness on New Hampshire that are independent of spanning trees, and compactness and partisan symmetry distributions on New Hampshire and Texas that, while related to spanning trees, can now be properly targeted with a smaller degree of spanning tree bias, which represents an advancement in flexible ensemble generation.
Supplementary material
Supplementary MaterialThe data and code needed to replicate these findings can be found at https://github.com/amcwhorter/MEW/. All computations were performed on doob, a 96-core 3.6GHz AMD Epyc system managed by the Dartmouth College Department of Mathematics.The supplementary material for this article is available on the official website of the Journal of Data Science at https://jds-online.org/. It may include additional results, appendices, tables, figures, code, and data.
References
Akitaya HA, Cannon S, Herschlag G, Schoenbach G, Tapp K, Tucker-Foltz J (2026). The balanced up-down walk. arXiv preprint: https://arxiv.org/abs/2602.11993.
Autry E, Carter D, Herschlag GJ, Hunter Z, Mattingly JC (2023). Metropolized forest recombination for Monte Carlo sampling of graph partitions. SIAM Journal on Applied Mathematics, 83(4): 1366–1391. https://doi.org/10.1137/21M1418010
Autry EA, Carter D, Herschlag GJ, Hunter Z, Mattingly JC (2021). Metropolized multiscale forest recombination for redistricting. Multiscale Modeling & Simulation, 19(4): 1885–1914. https://doi.org/10.1137/21M1406854
Cai JY, Kruse J, Mayer K, Szabo DP (2024). A uniformly random solution to algorithmic redistricting. arXiv preprint: https://arxiv.org/abs/2402.13868.
Caldera S, DeFord D, Duchin M, Gutekunst SC, Nix C (2020). Mathematics of nested districts: The case of Alaska. Statistics and Public Policy, 7(1): 39–51. https://doi.org/10.1080/2330443X.2020.1774452
Cannon S, Duchin M, Randall D, Rule P (2022). Spanning trees and redistricting: new methods for sampling and validation. arXiv preprint: https://arxiv.org/abs/2210.01401.
Cannon S, Pegden W, Tucker-Foltz J (2024). Sampling balanced forests of grids in polynomial time. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), 1676–1687. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3618260.3649699
Cannon S, Pegden W, Tucker-Foltz J (2025). Sampling tree-weighted partitions without sampling trees. arXiv preprint: https://arxiv.org/abs/2508.11130.
Charikar M, Liu P, Liu T, Vuong TD (2023). On the complexity of sampling redistricting plans. arXiv preprint: https://arxiv.org/abs/2206.04883.
Chikina M, Frieze A, Mattingly JC, Pegden W (2020). Separating effect from significance in Markov chain tests. Statistics and Public Policy, 7(1): 101–114. https://doi.org/10.1080/2330443X.2020.1806763
Chikina M, Frieze A, Pegden W (2017). Assessing significance in a Markov chain without mixing. Proceedings of the National Academy of Sciences, 114(11): 2860–2864. https://doi.org/10.1073/pnas.1617540114
Chuang G, Herschlag G, Mattingly JC (2025). Multiscale parallel tempering for fast sampling on redistricting plans. Multiscale Modeling & Simulation, 23(4): 1515–1550. https://doi.org/10.1137/24M1635806
Clelland J, Colgate H, DeFord D, Malmskog B, Sancier-Barbosa F (2022). Colorado in context: Congressional redistricting and competing fairness criteria in Colorado. Journal of Computational Social Science, 5(1): 189–226. https://doi.org/10.1007/s42001-021-00119-7
Clelland J, DeFord D, Duchin M (2020). Aftermath: The ensemble approach to political redistricting. Math Horizons, 27(3): 34–35. https://doi.org/10.1080/10724117.2019.1680187
Clelland JN, Bossenbroek N, Heckmaster T, Nelson A, Rock P, VanAusdall J (2021). Compactness statistics for spanning tree recombination. arXiv preprint: https://arxiv.org/abs/2103.02699.
DeFord D, Duchin M, Solomon J (2020). A computational approach to measuring vote elasticity and competitiveness. Statistics and Public Policy, 7(1): 69–86. https://doi.org/10.1080/2330443X.2020.1777915
DeFord D, Duchin M, Solomon J (2021). Recombination: A family of Markov chains for redistricting. Harvard Data Science Review, 3(1). https://doi.org/10.1162/99608f92.eb30390f
DeFord D, Veomett E (2026). Bounds and bugs: The limits of symmetry metrics to detect partisan gerrymandering. Election Law Journal: Rules, Politics, and Policy, 25(2): 127–153. https://doi.org/10.1089/elj.2024.0038
DeFord DR, Herschlag G, Mattingly JC (2025). A cycle walk for sampling measures on spanning forests for redistricting. arXiv preprint: https://arxiv.org/abs/2509.08629.
Donnay C, Kahle M (2025). Asymptotics of redistricting the $n\times n$ grid. The American Mathematical Monthly, 132(9): 856–866. https://doi.org/10.1080/00029890.2025.2542711
Fifield B, Higgins M, Imai K, Tarr A (2020a). Automated redistricting simulation using Markov chain Monte Carlo. Journal of Computational and Graphical Statistics, 29(4): 715–728. https://doi.org/10.1080/10618600.2020.1739532
Fifield B, Imai K, Kawahara J, Kenny CT (2020b). The essential role of empirical validation in legislative redistricting simulation. Statistics and Public Policy, 7(1): 52–68. https://doi.org/10.1080/2330443X.2020.1791773
Frieze A, Pegden W (2023). Subexponential mixing for partition chains on grid-like graphs. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3317–3329. SIAM, Philadelphia, PA. https://doi.org/10.1137/1.9781611977554.ch127
Herschlag G, Kang HS, Luo J, Graves CV, Bangia S, Ravier R, Mattingly JC (2020). Quantifying gerrymandering in North Carolina. Statistics and Public Policy, 7(1): 30–38. https://doi.org/10.1080/2330443X.2020.1796400
Mathematicians, Law Professors, and Students (amici curiae) (2019). Amicus brief of mathematicians, law professors, and students in support of the appellees and affirmance. Brief for amici curiae, Rucho v. Common Cause, Nos. 18-422, 18-726, Supreme Court of the United States, filed March 8, 2019. Counsel: G.-U. E. Charles, D. Gupta (counsel of record), and D. Wilf-Townsend. https://www.supremecourt.gov/DocketPDF/18/18-726/91448/20190308182045139_18-422%2018-726%20Amicus%20BOM%20Mathematicians.pdf.
McCartan C, Imai K (2023). Sequential Monte Carlo for sampling balanced and compact redistricting plans. The Annals of Applied Statistics, 17(4): 3300–3323. https://doi.org/10.1214/23-AOAS1763
McWhorter A, DeFord D (2026). Free elections in the free state: Ensemble analysis of redistricting in New Hampshire. Journal of Computational Social Science, 9(2): 35. https://doi.org/10.1007/s42001-026-00466-3
Najt E, DeFord D, Solomon J (2019). Complexity and geometry of sampling connected graph partitions. arXiv preprint: https://arxiv.org/abs/1908.08881.
Najt E, DeFord D, Solomon J (2021). Empirical sampling of connected graph partitions for redistricting. Physical Review E, 104(6): 064130. https://doi.org/10.1103/PhysRevE.104.064130
O’Sullivan P, Imai K, McCartan C (2026). Generalized sequential Monte Carlo sampling for redistricting simulation. arXiv preprint: https://arxiv.org/abs/2603.22188.
Palmer M, Schneer B, DeLuca K (2024). A partisan solution to partisan gerrymandering: The define–combine procedure. Political Analysis, 32(3): 295–310. https://doi.org/10.1017/pan.2023.39
Ratliff T, Somersille S, Veomett E (2025). Don’t trust a single gerrymandering metric. La Matematica, 4(3): 764–809. https://doi.org/10.1007/s44007-025-00172-y
Zhao Z, Hettle C, Gupta S, Mattingly JC, Randall D, Herschlag GJ (2022). Mathematically quantifying non-responsiveness of the 2021 Georgia congressional districting plan. In: Proceedings of the 2nd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO ’22), Article 15, 1–11. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3551624.3555300
