Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans

DOI10.48550/ARXIV.2008.06131MaRDI QIDQ58510zbMATH OpenFDO

Authors Cory McCartan, Kosuke Imai, Cory W. McCartan, Kosuke Imai

Publication date 13 August 2020

Published in The Annals of Applied Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.06131

zbMATH Keywords

gerrymanderinggraph partitionsequential Monte Carlospanning trees

Mathematics Subject Classification ID

Applications of statistics (62Pxx)

Abstract: Random sampling of graph partitions under constraints has become a popular tool for evaluating legislative redistricting plans. Analysts detect partisan gerrymandering by comparing a proposed redistricting plan with an ensemble of sampled alternative plans. For successful application, sampling methods must scale to maps with a moderate or large number of districts, incorporate realistic legal constraints, and accurately and efficiently sample from a selected target distribution. Unfortunately, most existing methods struggle in at least one of these areas. We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution. Because it draws many plans in parallel, the SMC algorithm can efficiently explore the relevant space of redistricting plans better than the existing Markov chain Monte Carlo (MCMC) algorithms that generate plans sequentially. Our algorithm can simultaneously incorporate several constraints commonly imposed in real-world redistricting problems, including equal population, compactness, and preservation of administrative boundaries. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania. We find that the proposed algorithm converges faster and with fewer samples than a comparable MCMC algorithm. Open-source software is available for implementing the proposed methodology.

Cites work

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 3801587 (Why is no real title available?)
• A tabu search heuristic and adaptive memory procedure for political districting
• An optimization based heuristic for political districting
• Assessing significance in a Markov chain without mixing
• Automated Redistricting Simulation Using Markov Chain Monte Carlo
• Bayesian data analysis.
• Elements of Information Theory
• Inference from iterative simulation using multiple sequences
• Numerically stable online estimation of variance in particle filters
• On sequential Monte Carlo, partial rejection control and approximate Bayesian computation
• Rank-normalization, folding, and localization: an improved \(\widehat{R}\) for assessing convergence of MCMC (with Discussion)
• Reconfiguration of connected graph partitions via recombination
• Rejection Control and Sequential Importance Sampling
• Sequential Monte Carlo Methods in Practice
• Sequential Monte Carlo Samplers
• The number of spanning trees in graphs with a given degree sequence
• The sample size required in importance sampling
• Three applications of entropy to gerrymandering
• Variance estimation in the particle filter

Cited in

(1)

• Irreducibility of recombination Markov chains in the triangular lattice

This page was built for publication: Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q58510)