Voting Rights, Markov Chains, and Optimization by Short Bursts

被引:4
作者
Cannon, Sarah [1 ]
Goldbloom-Helzner, Ari [2 ]
Gupta, Varun [3 ]
Matthews, J. N. [4 ]
Suwal, Bhushan [5 ]
机构
[1] Claremont McKenna Coll, Claremont, CA 91711 USA
[2] Brown Univ, Providence, RI USA
[3] Univ Penn, Philadelphia, PA USA
[4] Univ Chicago, Chicago, IL USA
[5] Boston Univ, Boston, MA USA
关键词
Voting rights; Markov chain; Random walk; Optimization; Redistricting; Outlier analysis; Computational methods for problems pertaining to probability theory);
D O I
10.1007/s11009-023-09994-1
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页数:38
相关论文
共 32 条
[1]  
Anderson E, 2011, NOLA
[2]  
[Anonymous], 2021, MILL V MERR
[3]  
[Anonymous], 2018, DWIGHT V KEMP
[4]  
[Anonymous], 2018, JOHNS V ARD
[5]  
[Anonymous], 1997, NEGR V CIT MIAM BEAC
[6]  
Autrey E, 2021, Arxiv, DOI arXiv:1911.01503
[7]  
Bartlettv.Strickland, 2009, BARTL V STRICKL
[8]  
Bethune-Hillv.Virginia State Board of Elections, 2017, BETH HILL V VIRG STA
[9]   Mathematics of Nested Districts: The Case of Alaska [J].
Caldera, Sophia ;
DeFord, Daryl ;
Duchin, Moon ;
Gutekunst, Samuel C. ;
Nix, Cara .
STATISTICS AND PUBLIC POLICY, 2020, 7 (01) :39-51
[10]  
Chen J, 2018, EXPERT REPORT J CHEN