  We develop a new Markov chain on graph partitions that makes relatively
global moves yet is computationally feasible to be used as the proposal in the
Metropolis-Hastings method. Our resulting algorithm can be made reversible and
able to sample from a specified measure on partitions. Both of these properties
are critical to some important applications and computational Bayesian
statistics in general. Our proposal chain modifies the recently developed
method called Recombination (ReCom), which draws spanning trees on joined
partitions and then randomly cuts them to repartition. We improve the
computational efficiency by augmenting the state space from partitions to
spanning forests. The extra information accelerates the computation of the
forward and backward proposal probabilities. We demonstrate this method by
sampling redistricting plans and find promising convergence results on several
key observables of interest.
