UCSB CS Theory Colloquium Series

Fall 2021

Friday, November 5, 2pm, Phelps 2510
Sarah Cannon (Claremont McKenna)

                Title: Properties of Redistricting Markov Chains
Markov chains have become widely-used to generate random political districting plans. These random districting plans can be used to form a baseline for comparison, and any proposed districting plans that differ significantly from this baseline can be flagged as potentially gerrymandered. However, very little is known about these Markov chains - Are they irreducible? What is their mixing time? For some, even the stationary distribution remains unknown. This talk will give an overview of how Markov chains are used in the context of redistricting, present recent work that answers some of these questions, and discuss the many theory-related open questions that remain.