Markov Chains for Sampling Matchings
View/ Open
Date
2008Author
Matthews, James
Metadata
Abstract
Markov Chain Monte Carlo algorithms are often used to sample combinatorial structures
such as matchings and independent sets in graphs. A Markov chain is defined
whose state space includes the desired sample space, and which has an appropriate stationary
distribution. By simulating the chain for a sufficiently large number of steps,
we can sample from a distribution arbitrarily close to the stationary distribution. The
number of steps required to do this is known as the mixing time of the Markov chain.
In this thesis, we consider a number of Markov chains for sampling matchings, both
in general and more restricted classes of graphs, and also for sampling independent sets
in claw-free graphs. We apply techniques for showing rapid mixing based on two main
approaches: coupling and conductance. We consider chains using single-site moves,
and also chains using large block moves.
Perfect matchings of bipartite graphs are of particular interest in our community.
We investigate the mixing time of a Markov chain for sampling perfect matchings in
a restricted class of bipartite graphs, and show that its mixing time is exponential in
some instances. For a further restricted class of graphs, however, we can show subexponential
mixing time.
One of the techniques for showing rapid mixing is coupling. The bound on the
mixing time depends on a contraction ratio b. Ideally, b < 1, but in the case b = 1 it
is still possible to obtain a bound on the mixing time, provided there is a sufficiently
large probability of contraction for all pairs of states. We develop a lemma which
obtains better bounds on the mixing time in this case than existing theorems, in the
case where b = 1 and the probability of a change in distance is proportional to the
distance between the two states. We apply this lemma to the Dyer-Greenhill chain for
sampling independent sets, and to a Markov chain for sampling 2D-colourings.