A Cycle Walk for Sampling Measures on Spanning Forests for Redistricting
For political redistricting, this method provides a more flexible and efficient MCMC framework that can handle policy-relevant compactness measures beyond traditional spanning-tree-based approaches.
The paper introduces the Cycle Walk, a new MCMC method for sampling balanced graph partitions for redistricting that combines local and global updates. Experiments show improved convergence for distributions with weaker weight on spanning-tree counts, enabling sampling from a broader class of redistricting distributions.
We introduce the Cycle Walk, a new Markov chain Monte Carlo method for sampling distributions on balanced graph partitions, motivated by applications in political redistricting. The method operates on spanning forests and combines two types of updates: local "cycle" moves within districts and global moves that exchange population between adjacent districts while preserving balance constraints. This construction enables efficient Metropolis--Hastings correction while allowing proposals at multiple spatial scales. We show that the Cycle Walk naturally interpolates between existing approaches based on local updates and a class of global update methods derived from recombination (RECOM). Through a range of numerical experiments on synthetic graphs and real-world precinct data, we demonstrate that the Cycle Walk exhibits improved empirical convergence diagnostics for distributions that place weaker weight on spanning-tree counts, a regime that is challenging for existing methods. In particular, the algorithm remains effective when incorporating alternative compactness measures that more closely reflect policy-relevant criteria. These results suggest that the Cycle Walk provides a flexible and computationally efficient framework for sampling from a broader class of redistricting distributions than previously accessible with MCMC techniques.