Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.17714 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914115953360896 |
|---|---|
| author | McWhorter, Atticus DeFord, Daryl |
| author_facet | McWhorter, Atticus DeFord, Daryl |
| contents | Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. 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 target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17714 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions McWhorter, Atticus DeFord, Daryl Data Structures and Algorithms Machine Learning Physics and Society Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. 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 target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation. |
| title | The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions |
| topic | Data Structures and Algorithms Machine Learning Physics and Society |
| url | https://arxiv.org/abs/2510.17714 |