Sampling from complicated and unknown distributions: Monte Carlo and Markov Chain Monte Carlo methods for redistricting

Sampling from complicated and unknown distributions has wide-ranging applications. Standard Monte Carlo techniques are designed for known distributions and are difficult to adapt when the distribution is unknown. Markov Chain Monte Carlo (MCMC) techniques are designed for unknown distributions, but when the underlying state space is complex and not continuous, the application of MCMC becomes challenging and no longer straightforward. Both of these techniques have been proposed for the astronomically large redistricting application that is characterized by an extremely complex and idiosyncratic state space. We explore the theoretic applicability of these methods and evaluate their empirical performance.