JDS Journal of Data Science 1683-86021680-743X1680-743X School of Statistics, Renmin University of China JDS1243 10.6339/26-JDS1243 Computing in Data Science The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions McWhorterAtticusatticus.w.mcwhorter.gr@dartmouth.edu1∗ DeFordDaryl2 Department of Mathematics, Dartmouth College, USA Department of Mathematics and Statistics, Vassar College, USA Corresponding author. Email: atticus.w.mcwhorter.gr@dartmouth.edu. 20262810202600118 Supplementary Material

The 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.

131120252482026 2026 The Author(s). Published by the School of Statistics and the Center for Applied Statistics, Renmin University of China.2026 Open access article under the CC BY license.

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.

 computational redistricting graph partitioning Markov Chain Monte Carlo Metropolis Hastings spanning trees This work was funded by the Dartmouth Fellowship to Atticus McWhorter and by the Alfred P. Sloan Foundation (G-2021-16778) and the National Science Foundation (DMS-1928930) which supported Daryl DeFord during his visit to SLMath in 2023 where this collaboration began. 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 (2019). Redistricting reform in Virginia: Districting criteria in context. Virginia Policy Review, 12(2): 120–146. 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 × 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 Procaccia AD, Tucker-Foltz J (2022). Compact redistricting plans have many spanning trees. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3754–3771. SIAM, Philadelphia, PA. 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