Balanced Spanning Tree Distributions Have Separation Fairness
Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors compact, contiguous, and population-balanced districts. However, whether such samples are truly representative or exhibit hidden biases remains an open question. In this work, we introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans. Focusing on grid graphs and two-district partitions, we prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness. Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process. Along the way, we prove a novel local-interchangeability lemma for 2-partitions on grids, showing that any separation of adjacent vertices can be undone via a constant-sized modification. This lemma, along with our other tools for analyzing the structure of partitions and loop-erased random walks, may be of independent interest.
