Automated Redistricting Simulation Using Markov Chain Monte Carlo

Citation

Fifield, Benjamin, Michael Higgins, Kosuke Imai, and Alexander Tarr. (2020). “Automated Redistricting Simulation Using Markov Chain Monte Carlo.” Journal of Computational and Graphical Statistics, Vol. 29, No. 4, pp. 715-728.

Abstract

Legislative redistricting is a critical element of representative democracy. A number of political scientists have used simulation methods to sample redistricting plans under various constraints in order to assess their impact on partisanship and other aspects of representation. However, while many optimization algorithms have been proposed, surprisingly few simulation methods exist in the published scholarship. Furthermore, the standard algorithm has no theoretical justification, scales poorly, and is unable to incorporate fundamental constraints required by redistricting processes in the real world. To fill this gap, we formulate redistricting as a graph-cut problem and for the first time in the literature propose a new automated redistricting simulator based on Markov chain Monte Carlo. The proposed algorithm can incorporate contiguity and equal population constraints at the same time. We apply simulated and parallel tempering to improve the mixing of the resulting Markov chain. Through a small-scale validation study, we show that the proposed algorithm can approximate a target distribution more accurately than the standard algorithm. We also apply the proposed methodology to data from Pennsylvania to demonstrate the applicability of our algorithm to real-world redistricting problems. The open-source software is available for implementing the proposed methodology.

Download Paper

Download Appendix

Related Paper and Software

• An earlier version of the paper: Fifield, Benjamin, Michael Higgins, Kosuke Imai, and Alexander Tarr. (2014). “A New Automated Redistricting Simulator Using Markov Chain Monte Carlo.”
• Fifield, Benjamin, Kosuke Imai, Jun Kawahara, and Christopher T. Kenny. (2020). “The Essential Role of Empirical Validation in Legislative Redistricting Simulation.” Statistics and Public Policy, Vol. 7, No. 1, pp 52-68.
• McCartan, Cory, and Kosuke Imai. “Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans.”
• Fifield, Benjamin, Christopher T. Kenny, Cory MaCartan, and Kosuke Imai. “redist: Computational Algorithms for Redistricting Simulation.” available through The Comprehensive R Archive Network and GitHub.