Generalized Sequential Monte Carlo Sampling for Redistricting Simulation

• URL: http://arxiv.org/abs/2603.22188v1
• Date: Mon, 23 Mar 2026 16:48:43 GMT
• Title: Generalized Sequential Monte Carlo Sampling for Redistricting Simulation
• Abstract summary: We generalize the Sequential Monte Carlo (SMC) algorithm of McCartan and Imai (2023), one of the commonly used approaches.<n>Our generalized SMC (gSMC) algorithm can split off regions of arbitrary size, rather than a single district, enabling the sampling of multi-member districts.<n>We demonstrate the effectiveness of the proposed methodology through analyses of the Irish Parliament, which uses multi-member districts, and the Pennsylvania House of Representatives, which has more than 200 single-member districts.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Simulation methods have become important tools for quantifying partisan and racial bias in redistricting plans. We generalize the Sequential Monte Carlo (SMC) algorithm of McCartan and Imai (2023), one of the commonly used approaches. First, our generalized SMC (gSMC) algorithm can split off regions of arbitrary size, rather than a single district as in the original SMC framework, enabling the sampling of multi-member districts. Second, the gSMC algorithm can operate over various sampling spaces, providing additional computational flexibility. Third, we derive optimal-variance incremental weights and show how to compute them efficiently for each sampling space. Finally, we incorporate Markov chain Monte Carlo (MCMC) steps, creating a hybrid gSMC-MCMC algorithm that can be used for large-scale redistricting applications. We demonstrate the effectiveness of the proposed methodology through analyses of the Irish Parliament, which uses multi-member districts, and the Pennsylvania House of Representatives, which has more than 200 single-member districts.

Related papers

• Learning Discrete Bayesian Networks with Hierarchical Dirichlet Shrinkage [52.914168158222765]
  We detail a comprehensive Bayesian framework for learning DBNs.<n>We give a novel Markov chain Monte Carlo (MCMC) algorithm utilizing parallel Langevin proposals to generate exact posterior samples.<n>We apply our methodology to uncover prognostic network structure from primary breast cancer samples.
  arXiv  Detail & Related papers  (2025-09-16T17:24:35Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
  We propose two methods for exploiting parallelism in the MCMC. In the first, we replace the MCMC with another numerical Bayesian approach. In the second, we consider data partitioning.
  arXiv  Detail & Related papers  (2023-01-22T09:56:26Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Variational Combinatorial Sequential Monte Carlo Methods for Bayesian Phylogenetic Inference [4.339931151475307]
  We introduce Vari Combinatorial Monte Carlo (VCSMC), a powerful framework that establishes variational search to learn over intricate structures. We show that VCSMC and CSMC are efficient and explore higher probability spaces than existing methods on a range of tasks.
  arXiv  Detail & Related papers  (2021-05-31T19:44:24Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Accelerating MCMC algorithms through Bayesian Deep Networks [7.054093620465401]
  Markov Chain Monte Carlo (MCMC) algorithms are commonly used for their versatility in sampling from complicated probability distributions. As the dimension of the distribution gets larger, the computational costs for a satisfactory exploration of the sampling space become challenging. We show an alternative way of performing adaptive MCMC, by using the outcome of Bayesian Neural Networks as the initial proposal for the Markov Chain.
  arXiv  Detail & Related papers  (2020-11-29T04:29:00Z)
• Kernel learning approaches for summarising and combining posterior similarity matrices [68.8204255655161]
  We build upon the notion of the posterior similarity matrix (PSM) in order to suggest new approaches for summarising the output of MCMC algorithms for Bayesian clustering models. A key contribution of our work is the observation that PSMs are positive semi-definite, and hence can be used to define probabilistically-motivated kernel matrices.
  arXiv  Detail & Related papers  (2020-09-27T14:16:14Z)
• Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans [0.0]
  We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania.
  arXiv  Detail & Related papers  (2020-08-13T23:26:34Z)
• A Parallel Evolutionary Multiple-Try Metropolis Markov Chain Monte Carlo Algorithm for Sampling Spatial Partitions [0.0]
  We develop an Evolutionary Markov Chain Monte Carlo (EMCMC) algorithm for sampling spatial partitions that lie within a spatial state space. Our algorithm combines the advantages of evolutionary algorithms (EAs) as a large and complex state space traversal and the theoretical convergence properties of Markov Chain Monte Carlo algorithms for sampling from unknown distributions. We further expand the reach of our EMCMC algorithm by harnessing the computational power afforded by massively parallel architecture.
  arXiv  Detail & Related papers  (2020-07-22T14:28:44Z)
• Involutive MCMC: a Unifying Framework [64.46316409766764]
  We describe a wide range of MCMC algorithms in terms of iMCMC. We formulate a number of "tricks" which one can use as design principles for developing new MCMC algorithms. We demonstrate the latter with two examples where we transform known reversible MCMC algorithms into more efficient irreversible ones.
  arXiv  Detail & Related papers  (2020-06-30T10:21:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.