METROPOLIZED FOREST RECOMBINATION FOR MONTE CARLO SAMPLING OF GRAPH PARTITIONS

Loading...
Thumbnail Image

Date

2023-08-01

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

7
views
48
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.

Department

Description

Provenance

Citation

Published Version (Please cite this version)

10.1137/21M1418010

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.

Scholars@Duke

Herschlag

Gregory Joseph Herschlag

Associate Research Professor of Mathematics

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

Mattingly

Jonathan Christopher Mattingly

Kimberly J. Jenkins Distinguished University Professor of New Technologies

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.