Open Access Senior Thesis
Bachelor of Arts
Over the past decade, there has been an increased focus on how political districts are drawn and partitioned. How districts are drawn, and what population groups are included in different districts, can have a large impact on who is elected. Politicians have used this fact to manipulate election outcomes to give an advantage to a particular group in a process known as gerrymandering. Gerrymandering is not always unconstitutional, but generally goes against the fundamental principle of one person one vote. It is important to be able to detect and quantify, particularly in cases where gerrymandering has been used to suppress minority votes. However, this can be a difficult task. Various mathematical tools have been used to help aid in this process, primarily trying to create a baseline of possible plans through random sampling. The main problem is how little we know about how well these tools work. We don't know the distribution the random sampling draws from and we also don't know how large the sample needs to be for it to be representative.
This research studies mixing time, or how long the Markov chain needs to be run for it to generate a reasonable sample. We look specifically at the mixing time of Recombination, a type of Markov Chain used for sampling districting plans. We want to see how long the mixing time is if we start at a particular plan to reach the stationary distribution. We will do this by calculating total variation distance between a distribution. We transition from one plan to another using the transition matrix. To analyze this we will plot the total variation distances over time. We want to see the impact of starting at different plans, the size of graphs, and other factors on convergence to the stationary distribution. The main correlation we have mathematical evidence for is the inverse relationship between the total number of plans possible and mixing time. It also appears that as the number of districts increases by one, the mixing time at least doubles.
Kolesnik, Emma, "Convergence Time of the Recombination Markov Chain on Small Planar Graphs" (2021). Scripps Senior Theses. 1739.