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.