Empirical sampling of connected graph partitions for redistricting

Area of Science:

• Computational social science
• Statistical physics
• Political science

Background:

• Connected graph partitions are foundational to statistical models used in political districting analysis.
• Current redistricting methods employ sampling techniques adapted from statistical physics.

Purpose of the Study:

• To investigate the relationship between political redistricting and statistical physics, particularly self-avoiding walks.
• To analyze Markov chain Monte Carlo (MCMC) methods for districting plans by leveraging insights from self-avoiding walks.

Main Methods:

• Analysis of phase transitions and asymptotic behavior in self-avoiding walks.
• Examination of mixing times for Glauber dynamics-based Markov chains in the context of redistricting.
• Investigation of factors like population balance, connectivity, and irregular graphs.
• Assessment of the robustness of districting plan properties against score functions and state-dual graphs.

Main Results:

• Self-avoiding walk phase transitions influence the mixing times of Markov chains used in redistricting.
• Population balance and connectivity requirements introduce complexities to Markov chain analysis.
• The robustness of districting plan properties depends on score functions and the underlying graph structure.

Conclusions:

• Understanding statistical physics concepts like self-avoiding walks is crucial for advancing MCMC methods in political redistricting.
• Further research is needed at the intersection of statistical physics, Markov chains, and political districting analysis.