Multi-Scale Merge-Split Markov Chain Monte Carlo for Redistricting

Understand

We develop a Multi-Scale Merge-Split 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 which each correspond to a different district.
• The districts satisfy a collection of hard constraints and the measure may be weighted with regard to a number of other criteria.