Introduction to Discrete MCMC (with Scrabble)

This page organizes the software resources that I wrote to accompany my notes on MCMC. These resources are still a work in progress but I hope they will be useful to people encountering this material for the first time. The underlying code for all of these tools is available on GitHub.

Introduction

As MCMC sampling has become an increasingly popular tool for evaluating districting plans, people from a diverse set of backgrounds are encountering these methods for the first time. These notes and Sage Widgets represent my attempt at explaining the underlying ideas in a concrete and friendly fashion, with lots of opportunity for interaction and exploration. Throughout the .pdf document there are many links to individual interactive tools for exploring the ideas further. These tools and brief descriptions of their purposes are linked below. The organizational structure of this page follows that of the accompanying text.

If you are interested in building your own Sage @interact modules, I have prepared some notes and examples at the bottom of this page. I frequently use these tools for both teaching and research and highly recommend them.

Scrabble

I have always thought that Scrabble tiles are a great tool for teaching Markov chains and MCMC. They are familiar to many people, the tiles themselves come in a non-uniform distribution, and each tile has an associated point value that leads to an entirely separate distribution. The table below shows the frequency and point distributions for the American English tileset.

Letter ABCDEFGHIJKLMN OPQRSTUVWXYZ
Frequency 922412232911426 8216464221212
Score 13321424185131 131011114484100

Throughout these interactive programs, we make use of a few specific Markov chains and score functions that are worth highlighting in advance (full descriptions and plots are also in the .pdf):

Probability Background

This section introduces the ideas of distributions, random variables, and expected values using examples like rolling a die or drawing a Scrabble tile.

Monte Carlo Sampling

This section introduces the idea of Monte Carlo sampling as an efficient way to estimate numerical values when we can evaluate random samples easily.

Markov Chains

This section introduces Markov chains and the related concept of walks on graphs.

Markov Chain Monte Carlo

Finally, we reach the main topic of this discussion, actual MCMC sampling. This section introduces the Metropolis--Hastings variant of MCMC and gives several examples, making use of the previously introduced Markov chains and score functions. There is only one widget in this section but it incorporates many of the previous tools.

Mixing Times

Although much of the literature on mixing times requires mathematical tools that are beyond the scope of this introduction, this section provides some intuition for how the properties of the chain and Metropolis-Hastings waiting process can impact the convergence rate.

Lifted Markov Chains

One approach for forming faster mixing Markov chains is the idea of a ``lifted'' walk, where we make use of an auxiliary graph that has a known rapidly mixing chain. The key idea is that in well-behaved graphs (e.g. those with lots of symmetry) we can construct faster mixing chains by lifting to a larger graph with even nicer properties. Although this is unintuitive at first glance, as we are moving to a setting with more nodes to try to get more rapid mixing, this example demonstrates the main properties that make this procedure work.

MCMC for Redistricting

The last section of the notes focuses on applying MCMC methods to the problem of sampling legislative districting plans. This requires both an additional layer of abstraction, as the states in our Markov chain are now partitions of graphs instead of individual nodes, as well as more concrete engagement with the real-world data and laws that govern the process. We see how all of the concepts introduced in the previous sections - defining the state space, picking a proposal method, computing the acceptance function, etc. - have to be modified to work in this applied setting. The section concludes with a discussion of annealing and partitions of grids.