Show simple item record

dc.contributor.advisorCryan, Maryen
dc.contributor.advisorJerrum, Marken
dc.contributor.authorMatthews, Jamesen
dc.date.accessioned2009-09-16T14:38:48Z
dc.date.available2009-09-16T14:38:48Z
dc.date.issued2008
dc.identifier.urihttp://hdl.handle.net/1842/3072
dc.description.abstractMarkov 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.en
dc.format.extent698104 bytesen
dc.format.mimetypeapplication/pdfen
dc.language.isoen
dc.subjectInformaticsen
dc.subjectComputer Scienceen
dc.subjectMarkov Chain Monte Carlo algorithmen
dc.subjectMarkov chainen
dc.titleMarkov Chains for Sampling Matchingsen
dc.typeThesis or Dissertationen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record