Browsing by Subject "Metropolis-Hastings"

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    METROPOLIZED FOREST RECOMBINATION FOR MONTE CARLO SAMPLING OF GRAPH PARTITIONS
    (SIAM Journal on Applied Mathematics, 2023-08-01) Autry, E; Carter, D; Herschlag, GJ; Hunter, Z; Mattingly, JC
    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.
  • Thumbnail Image
    ItemOpen Access
    Metropolized Multiscale Forest Recombination for Redistricting
    (Multiscale Modeling & Simulation, 2021-01) Autry, EA; Carter, D; Herschlag, GJ; Hunter, Z; Mattingly, JC
  • Thumbnail Image
    ItemOpen Access
    Stochastic Study of Gerrymandering
    (2015-05-06) Vaughn, Christy
    In the 2012 election for the US House of Representatives, only four of North Carolina’s thirteen congressional districts elected a democrat, despite a majority democratic vote. This raises the question of whether gerrymandering, the process of drawing districts to favor a political party, was employed. This study explores election outcomes under different choices of district boundaries. We represent North Carolina as a graph of voting tabulation districts. A districting is a division of this graph into thirteen connected subgraphs. We define a probability distribution on districtings that favors more compact districts with close to an equal population in each district. To sample from this distribution, we employ the Metropolis-Hastings variant of Markov Chain Monte Carlo. After sampling, election data from the 2012 US House of Representatives election is used to determine how many representatives would have been elected for each party under the different districtings. Of our randomly drawn districts, we find an average of 6.8 democratic representatives elected. Furthermore, none of the districtings elect as few as four democratic representatives, as was the case in the 2012 election.