Redistricting is the problem of partitioning a set of geographic units into a fixed number of subsets called districts, subject to a list of rules and priorities. These districts are used for elections, making their delineation highly consequential. It has been hard for quantitative researchers to orient to an application in which some of the rule vagueness is a feature rather than a bug—but law and policy often prefer ranges to optimizations or ideals. In recent years, the use of randomized methods to sample from the vast space of districting plans has been gaining traction in U.S. courts of law for identifying partisan gerrymanders, and it is now emerging as a promising assessment tool for legislatures and independent commissions, even before districts are enacted. In this paper, we set up redistricting as a graph partition problem and introduce a new family of Markov chains called recombination (or ReCom), focusing on a variant whose key step uses spanning trees. ReCom is a large-step random walk on the space of graph partitions, in contrast with commonly used Flip walks, which change the assignment label of one or a few nodes at a time. Important points of comparison concern the speed of convergence to stationarity, the form of the target distribution, and the characteristics of samples that can be obtained in practical time. We use real-world data to demonstrate advantages of spanning-tree ReCom and its relative weighting of plans, and we give a broader exposition of both the challenges of this approach and the analytical tools that it enables. We close with a short case study of race and redistricting in the Virginia House of Delegates.
Keywords: redistricting, gerrymandering, Markov chains, sampling