METROPOLIZED FOREST RECOMBINATION FOR MONTE CARLO SAMPLING OF GRAPH PARTITIONS
Date
2023-08-01
Journal Title
Journal ISSN
Volume Title
Repository Usage Stats
views
downloads
Citation Stats
Attention Stats
Abstract
We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm is able to sample from a specified measure on partitions or spanning forests. Being able to sample from a specified measure is a requirement of what we consider as the gold standard in quantifying the extent to which a particular map is a gerrymander. Our proposal chain modifies the recently developed method called recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the statespace from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities which are required for the Metropolis-Hastings algorithm. We demonstrate this method by sampling redistricting plans on several measures of interest and find promising convergence results on several key observables of interest. We also explore some limitations in the measures that are efficient to sample from and investigate the feasibility of using parallel tempering to extend this space of measures.
Type
Department
Description
Provenance
Citation
Permalink
Published Version (Please cite this version)
Publication Info
Autry, E, D Carter, GJ Herschlag, Z Hunter and JC Mattingly (2023). METROPOLIZED FOREST RECOMBINATION FOR MONTE CARLO SAMPLING OF GRAPH PARTITIONS. SIAM Journal on Applied Mathematics, 83(4). pp. 1366–1391. 10.1137/21M1418010 Retrieved from https://hdl.handle.net/10161/30137.
This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.
Collections
Scholars@Duke

Gregory Joseph Herschlag
I am interested in studying techniques to understand fairness in redistricting. I am also interested in computational fluid dynamics and high-performance computing.

Jonathan Christopher Mattingly
Jonathan Christopher Mattingly grew up in Charlotte, NC where he attended Irwin Ave elementary and Charlotte Country Day. He graduated from the NC School of Science and Mathematics and received a BS is Applied Mathematics with a concentration in physics from Yale University. After two years abroad with a year spent at ENS Lyon studying nonlinear and statistical physics on a Rotary Fellowship, he returned to the US to attend Princeton University where he obtained a PhD in Applied and Computational Mathematics in 1998. After 4 years as a Szego assistant professor at Stanford University and a year as a member of the IAS in Princeton, he moved to Duke in 2003. He is currently a Professor of Mathematics and of Statistical Science.
His expertise is in the longtime behavior of stochastic system including randomly forced fluid dynamics, turbulence, stochastic algorithms used in molecular dynamics and Bayesian sampling, and stochasticity in biochemical networks.
Since 2013 he has also been working to understand and quantify gerrymandering and its interaction of a region's geopolitical landscape. This has lead him to testify in a number of court cases including in North Carolina, which led to the NC congressional and both NC legislative maps being deemed unconstitutional and replaced for the 2020 elections.
He is the recipient of a Sloan Fellowship and a PECASE CAREER award. He is also a fellow of the IMS and the AMS. He was awarded the Defender of Freedom award by Common Cause for his work on Quantifying Gerrymandering.
Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.