Techniques in The Markov Chain Monte Carlo Method

Abstract

Consider the problem of sampling from a set of combinatorial objects according to a certain given distribution. The Markov chain Monte Carlo (MCMC) method is a possible solution for this problem. The method consists of setting up an ergodic Markov chain whose state space is the set of combinatorial objects we wish to sample from and which converges to a stationary distribution identical to the required distribution on the set of objects. Starting from a suitable start state we simulate the Markov chain for a certain number of steps (sufficient steps to guarantee a probability distribution close enough to the desired one) and output the state thus reached. The most important issue which needs to be dealt with is a bound on the number of steps required to reach close to the stationary distribution. When a chain approaches the stationary distribution without taking too many steps it is said to be rapidly mixing. The main aim of the method is to construct chains that are provably rapidly mixing. This thesis is about the techniques used in the Markov chain Monte Carlo method. We begin with Markov chain preliminaries. Next we introduce the concepts of conductance and resistance which are useful for showing rapid mixing. We follow this up with an example each of the two methods. Conductance arguments are used to approximate the permanent of a matrix with non-negative entries and resistance arguments are used to solve the 0-1 knapsack problem. After this we turn to coupling, another technique useful for demonstrating rapid mixing. We give a new and simple proof of the fact that maximal couplings exist. The proof also sheds intuition into the nature of coupling. And finally, as an application of coupling to computer science, we construct a rapidly mixing Markov chain for colourings of a graph with the number of colours being greater than twice the maximum degree of the graph.