Week 4 is done! We’ve only got two weeks left in the main program and things are starting to come together in a way that’s really, really exciting. This week I worked with the group building the Markov chain Monte Carlo (MCMC) simulator. Briefly, an MCMC sampler solves the problem of ‘we know how to draw from distribution A but what we’d really like to do is draw from distribution B’. In redistricting, we’d like to be able to generate a whole lot of legal districting plans in order to compare a proposed map to a random ensemble to, for example, determine if the proposed map treats a minority group unfairly. Unfortunately, we don’t know how to efficiently sample from that distribution. What we can do efficiently is start with some plan and randomly mutate it for a while. A Markov chain has a mixing time, which basically is the number of random mutations you have to make before your current state tells you nothing about where you started. For example, if I start with the five letter string ‘apple’ and my Markov chain randomly changes one letter at a time, after about 15 steps my string might be ‘udgxh’ and if I just hand you that string, you probably can’t meaningfully tell whether my initial string was ‘apple’ or ‘elbow’ or ‘zebra’, so we say that this Markov chain mixes quickly.
One major obstruction in the use of MCMC methods in redistricting is that we don’t really know how fast the chain mixes. Since there are so many constraints to obey, including equal population, contiguity, and compactness, there are relatively few moves (with respect to the number of allowable plans) the Markov chain can take at any time, so even if you run the chain for a few thousand or million steps, the resulting map doesn’t look extremely different from the original. This doesn’t mean that the method is useless or hopeless, however. Jon Mattingly and his team used an MCMC method on maps of North Carolina and were able to show that even though the Markov chain can only explore plans somewhat similar to the original, that the original scored much worse on factors like compactness and Voting Rights Act compliance than extremely similar maps, which is compelling evidence of the original map being a gerrymander.
As we’ve now passed the midway point of the five weeks of projects, we’re going to pivot towards bringing various projects to a place where we can walk away from them and the 2019 iteration of the VRDI won’t have to start from scratch. This week I think I’ll be working with someone on building a webapp to visualize and interact with the output of the MCMC code and getting back to the spectral stuff from last week.
Share this post on social media:
Did you like that post?
You can suscribe to the
Zach is a PhD student at the University of Pennsylvania, Department of Computer and Information Science. His research interests include game theory and mechanism design, machine learning, and computing for the social sciences.