  In the last decade, computational approaches to graph partitioning have made
a major impact in the analysis of political redistricting, including in U.S.
courts of law. Mathematically, a districting plan can be viewed as a balanced
partition of a graph into connected subsets. Examining a large sample of valid
alternative districting plans can help us recognize gerrymandering against an
appropriate neutral baseline. One algorithm that is widely used to produce
random samples of districting plans is a Markov chain called recombination (or
ReCom), which repeatedly fuses adjacent districts, forms a spanning tree of
their union, and splits that spanning tree with a balanced cut to form new
districts. One drawback is that this chain's stationary distribution has no
known closed form when there are three or more districts. In this paper, we
modify ReCom slightly to give it a property called reversibility, resulting in
a new Markov chain, RevReCom. This new chain converges to the simple, natural
distribution that ReCom was originally designed to approximate: a plan's
stationary probability is proportional to the product of the number of spanning
trees of each district. This spanning tree score is a measure of district
"compactness" (or shape) that is also aligned with notions of community
structure from network science. After deriving the steady state formally, we
present diagnostic evidence that the convergence is efficient enough for the
method to be practically useful, giving high-quality samples for full-sized
problems within several hours. In addition to the primary application of
benchmarking of redistricting plans (i.e., describing a normal range for
statistics), this chain can also be used to validate other methods that target
the spanning tree distribution.
