# The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions

arXiv: https://arxiv.org/abs/2510.17714 · HTML: https://mlsanity.com/paper/2510.17714/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 40 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Builds on (most cited first, 23 of 23)

- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans](https://mlsanity.com/paper/2008.06131/) (2020)
- [Assessing significance in a Markov chain without mixing](https://mlsanity.com/paper/1608.02014/) (2016)
- [Complexity and Geometry of Sampling Connected Graph Partitions](https://mlsanity.com/paper/1908.08881/) (2019)
- [Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions](https://mlsanity.com/paper/1911.01503/) (2019)
- [Compact Redistricting Plans Have Many Spanning Trees](https://mlsanity.com/paper/2109.13394/) (2021)
- [Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plan](https://mlsanity.com/paper/2203.06552/) (2022)
- [Optimal Legislative County Clustering in North Carolina](https://mlsanity.com/paper/1908.11801/) (2019)
- [A Computational Approach to Measuring Vote Elasticity and Competitiveness](https://mlsanity.com/paper/2005.12731/) (2020)
- [Mathematics of Nested Districts: The Case of Alaska](https://mlsanity.com/paper/2005.12732/) (2020)
- [The Essential Role of Empirical Validation in Legislative Redistricting Simulation](https://mlsanity.com/paper/2006.10148/) (2020)
- [Colorado in Context: Congressional Redistricting and Competing Fairness Criteria in Colorado](https://mlsanity.com/paper/2011.06049/) (2020)
- [Compactness statistics for spanning tree recombination](https://mlsanity.com/paper/2103.02699/) (2021)
- [Subexponential mixing for partition chains on grid-like graphs](https://mlsanity.com/paper/2206.00579/) (2022)
- [On the Complexity of Sampling Redistricting Plans](https://mlsanity.com/paper/2206.04883/) (2022)
- [Sampling Balanced Forests of Grids in Polynomial Time](https://mlsanity.com/paper/2310.15152/) (2023)
- [Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans](https://mlsanity.com/paper/2401.17455/) (2024)
- [A Uniformly Random Solution to Algorithmic Redistricting](https://mlsanity.com/paper/2402.13868/) (2024)
- [Bounds and Bugs: The Limits of Symmetry Metrics to Detect Partisan Gerrymandering](https://mlsanity.com/paper/2406.12167/) (2024)
- [Don't Trust A Single Gerrymandering Metric](https://mlsanity.com/paper/2409.17186/) (2024)
- [Sampling Tree-Weighted Partitions Without Sampling Trees](https://mlsanity.com/paper/2508.11130/) (2025)
- [Free Elections in the Free State: Ensemble Analysis of Redistricting in New Hampshire](https://mlsanity.com/paper/2509.07328/) (2025)
- [A Cycle Walk for Sampling Measures on Spanning Forests for Redistricting](https://mlsanity.com/paper/2509.08629/) (2025)

## Abstract (arXiv)

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.