Voting Rights, Markov Chains, and Optimization by Short Bursts

DOI10.48550/ARXIV.2011.02288MaRDI QIDQ58522zbMATH OpenOpenAlexFDO

Authors Sarah Cannon, Ari Goldbloom-Helzner, Varun Gupta, Jn Matthews, Bhushan Suwal

Publication date 23 October 2020

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

optimizationMarkov chainoutlier analysisrandom walkredistrictingvoting rights

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational methods in Markov chains (60J22)

Abstract: Finding outlying elements in probability distributions can be a hard problem. Taking a real example from Voting Rights Act enforcement, we consider the problem of maximizing the number of simultaneous majority-minority districts in a political districting plan. An unbiased random walk on districting plans is unlikely to find plans that approach this maximum. A common search approach is to use a biased random walk: preferentially select districting plans with more majority-minority districts. Here, we present a third option, called short bursts, in which an unbiased random walk is performed for a small number of steps (called the burst length), then re-started from the most extreme plan that was encountered in the last burst. We give empirical evidence that short-burst runs outperform biased random walks for the problem of maximizing the number of majority-minority districts, and that there are many values of burst length for which we see this improvement. Abstracting from our use case, we also consider short bursts where the underlying state space is a line with various probability distributions, and then explore some features of more complicated state spaces and how these impact the effectiveness of short bursts.

Recommendations

• Random walks and the universe of districting plans
• Local search algorithms for political districting
• Metropolized multiscale forest recombination for redistricting
• A computational approach to unbiased districting
• Optimal partisan districting on planar geographies

Cites work

• Assessing significance in a Markov chain without mixing
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.

Cited in

(3)

• redist
• Irreducibility of recombination Markov chains in the triangular lattice
• Random walks and the universe of districting plans

This page was built for publication: Voting Rights, Markov Chains, and Optimization by Short Bursts

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