Irreducibility of recombination Markov chains in the triangular lattice

DOI10.1016/J.DAM.2023.12.019arXiv2305.17239OpenAlexW4391074073MaRDI QIDQ6202939FDOQ6202939

Authors: Sarah Cannon 

Publication date: 27 February 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In the United States, regions are frequently divided into districts for the purpose of electing representatives. How the districts are drawn can affect who's elected, and drawing districts to give an advantage to a certain group is known as gerrymandering. It can be surprisingly difficult to detect gerrymandering, but one algorithmic method is to compare a current districting plan to a large number of randomly sampled plans to see whether it is an outlier. Recombination Markov chains are often used for this random sampling: randomly choose two districts, consider their union, and split this union in a new way. This works well in practice, but the theory behind it remains underdeveloped. For example, it's not known if recombination Markov chains are irreducible, that is, if recombination moves suffice to move from any districting plan to any other. Irreducibility of recombination Markov chains can be formulated as a graph problem: for a graph $G$, is the space of all partitions of $G$ into $k$ connected subgraphs ($k$ districts) connected by recombination moves? We consider three simply connected districts and district sizes $k_{1}pm1$ vertices, $k_{2}pm1$ vertices, and $k3pm1$ vertices. We prove for arbitrarily large triangular regions in the triangular lattice, recombination Markov chains are irreducible. This is the first proof of irreducibility under tight district size constraints for recombination Markov chains beyond small or trivial examples.

Full work available at URL: https://arxiv.org/abs/2305.17239

Recommendations

• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Metropolized multiscale forest recombination for redistricting
• Reconfiguration of connected graph partitions
• Random walks and the universe of districting plans

zbMATH Keywords

graph partitionMarkov chainrecombinationirreducibletriangular latticemath of redistricting

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Assessing significance in a Markov chain without mixing
• Metropolized multiscale forest recombination for redistricting
• Automated Redistricting Simulation Using Markov Chain Monte Carlo
• Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Voting Rights, Markov Chains, and Optimization by Short Bursts
• Reconfiguration of connected graph partitions via recombination
• Graph theory
• Markov chain algorithms for planar lattice structures
• Political geometry. Rethinking redistricting in the US with math, law, and everything in between
• Reconfiguration of connected graph partitions
• A Markov chain algorithm for compression in self-organizing particle systems
• Explainer: compactness, by the numbers

This page was built for publication: Irreducibility of recombination Markov chains in the triangular lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202939)