# Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans

arXiv: https://arxiv.org/abs/2401.17455 · HTML: https://mlsanity.com/paper/2401.17455/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 30 Jan 2024.

## Builds on (most cited first, 6 of 6)

- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Fairmandering: A column generation heuristic for fairness-optimized political districting](https://mlsanity.com/paper/2103.11469/) (2021)
- [Assessing significance in a Markov chain without mixing](https://mlsanity.com/paper/1608.02014/) (2016)
- [Complexity and Geometry of Sampling Connected Graph Partitions](https://mlsanity.com/paper/1908.08881/) (2019)
- [Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions](https://mlsanity.com/paper/1911.01503/) (2019)
- [Mathematically Quantifying Non-responsiveness of the 2021 Georgia Congressional Districting Plan](https://mlsanity.com/paper/2203.06552/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions](https://mlsanity.com/paper/2510.17714/) (2025)

## Abstract (arXiv)

When auditing a redistricting plan, a persuasive method is to compare the plan with an ensemble of neutrally drawn redistricting plans. Ensembles are generated via algorithms that sample distributions on balanced graph partitions. To audit the partisan difference between the ensemble and a given plan, one must ensure that the non-partisan criteria are matched so that we may conclude that partisan differences come from bias rather than, for example, levels of compactness or differences in community preservation. Certain sampling algorithms allow one to explicitly state the policy-based probability distribution on plans, however, these algorithms have shown poor mixing times for large graphs (i.e. redistricting spaces) for all but a few specialized measures. In this work, we generate a multiscale parallel tempering approach that makes local moves at each scale. The local moves allow us to adopt a wide variety of policy-based measures. We examine our method in the state of Connecticut and succeed at achieving fast mixing on a policy-based distribution that has never before been sampled at this scale. Our algorithm shows promise to expand to a significantly wider class of measures that will (i) allow for more principled and situation-based comparisons and (ii) probe for the typical partisan impact that policy can have on redistricting.