Voting Rights, Markov Chains, and Optimization by Short Bursts

Sarah Cannon (), Ari Goldbloom-Helzner (), Varun Gupta (), Matthews Jn () and Bhushan Suwal ()
Additional contact information
Sarah Cannon: Claremont McKenna College
Ari Goldbloom-Helzner: Brown University
Varun Gupta: University of Pennsylvania
Matthews Jn: University of Chicago
Bhushan Suwal: Boston University

Methodology and Computing in Applied Probability, 2023, vol. 25, issue 1, 1-38

Abstract: Abstract Finding outlying elementsin 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.

Keywords: Voting rights; Markov chain; Random walk; Optimization; Redistricting; Outlier analysis; 60-08; (Probability; Theory; and; Stochastic; Processes; -; Computational; methods; for; problems; pertaining; to; probability; theory) (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-023-09994-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:25:y:2023:i:1:d:10.1007_s11009-023-09994-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-023-09994-1

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().