Voting Rights, Markov Chains, and Optimization by Short Bursts

DOI10.48550/ARXIV.2011.02288zbMATH Open1515.60026arXiv2011.02288OpenAlexW3097040850MaRDI QIDQ58522FDOQ58522

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)

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.

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

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

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)

Cites Work

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

Cited In (2)

• Irreducibility of recombination Markov chains in the triangular lattice
• redist

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)