First steps towards quantifying district compactness in the ReCom sampling method

Ensemble analysis has become an important tool for analyzing and quantifying gerrymandering; the main idea is to generate a large, random sample of districting plans (an "ensemble") to which any proposed plan may be compared. If a proposed plan is an extreme outlier compared to the ensemble with regard to various redistricting criteria, this may indicate that the plan was deliberately engineered to produce a specific outcome. A variety of methods have been used to construct ensembles of plans, and a fundamental question that arises is: How accurately does an ensemble constructed by a particular method represent the entire space of valid plans -- or, if a method has an inherent bias towards particular types of plans, can this bias be identified and quantified? Recently, Markov Chain Monte Carlo (MCMC) methods have become a predominant tool for constructing ensembles of plans. In this paper, we focus on the MCMC method known as "ReCom," which was introduced in 2018 by the Metric Geometry and Gerrymandering Group. This method appears to produce plans with relatively compact districts compared to some other methods, and we sought to understand this phenomenon in greater detail. In order to model the basic ReCom step, we constructed large ensembles of plans consisting of two districts for two grid graphs and for the precinct graph of Boulder County, CO. We found that, to a high degree of accuracy, the sampling probability for any particular plan is proportional to an exponentially decaying function of a discrete measure that approximates the length of the boundary between the two districts in the plan. This suggests a more quantitative formulation of the observation that ReCom tends to produce relatively compact districts, and it represents an important first step towards understanding the full sampling probability distribution associated to the ReCom method.