Search

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 is able to sample from a specified measure on partitions or spanning forests. Being able to sample from a specified measure is a requirement of what we consider as the gold standard in quantifying the extent to which a particular map is a gerrymander. 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 statespace from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities which are required for the Metropolis--Hastings algorithm. We demonstrate this method by sampling redistricting plans on several measures of interest and find promising convergence results on several key observables of interest. We also explore some limitations in the measures that are efficient to sample from and investigate the feasibility of using parallel tempering to extend this space of measures. [ABSTRACT FROM AUTHOR]

We develop a Metropolized Multiscale Forest Recombination Markov Chain on redistricting plans. The chain is designed to be usable as the proposal in a Markov Chain Monte Carlo (MCMC) algorithm. Sampling the space of plans amounts to dividing a graph into a partition with a specified number of elements each of which corresponds to a different district according to a specified probability measure. The districts satisfy a collection of hard constraints, and the probability measure may be weighted with regard to a number of other criteria. The multiscale algorithm is similar to our previously developed Metropolized Forest Recombination proposal; however, this algorithm provides improved scaling properties and may also be used to preserve nested communities of interest such as counties and precincts. Both works use a proposal which extends the ReCom algorithm [D. DeFord, M. Duchin, and J. Solomon, Harvard Data Sci. Rev., (2021)] which leveraged spanning trees to merge and split districts. In this work, we extend the state space so that each district is defined by a hierarchy of trees. In this sense, the proposal step in both algorithms can be seen as a "Forest ReCom." The collection of plans sampled by the MCMC algorithm can serve as a baseline against which a particular plan of interest is compared. If a given plan has different racial or partisan qualities than what is typical of the collection of plans, the given plan may have been gerrymandered and is labeled as an outlier. Metropolizing relative to a policy driven probability measure removes the possibility of algorithmically inserted biases. [ABSTRACT FROM AUTHOR]