EUVIMEDEUVIMED entdecken
Crossref

Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

Eric Autry, Daniel Carter, Gregory J. Herschlag, Zach Hunter, Jonathan C. Mattingly

SIAM Journal on Applied Mathematics · 31.08.2023 · 83 (4) · 1366-1391

DOI: 10.1137/21m1418010 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Applied Mathematics, online erschienen am 05.07.2023. Verfasst von Eric Autry und 4 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 33 Literaturangaben. Gefördert von: SAMSI, TRIPODS, Rhodes Information Initiative.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • SAMSI
  • TRIPODS
  • Rhodes Information Initiative
  • National Science Foundation

Zitieren

APA

Autry, E., Carter, D., Herschlag, G. J., Hunter, Z., & Mattingly, J. C. (2023). Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions. SIAM Journal on Applied Mathematics, 83(4), 1366-1391. https://doi.org/10.1137/21m1418010

Vancouver

Autry E, Carter D, Herschlag GJ, Hunter Z, Mattingly JC. Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions. SIAM Journal on Applied Mathematics. 2023;83(4):1366-1391. doi:10.1137/21m1418010

BibTeX
@article{Autry2023,
  author = {Autry, Eric and Carter, Daniel and Herschlag, Gregory J. and Hunter, Zach and Mattingly, Jonathan C.},
  title = {Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions},
  journal = {SIAM Journal on Applied Mathematics},
  year = {2023},
  volume = {83},
  number = {4},
  pages = {1366--1391},
  doi = {10.1137/21m1418010}
}
Kostenlos starten →