The concern of this thesis is a performance analysis of certain Markov chain Monte Carlo algorithms. The performance of Markov chain Monte Carlo algorithms in general is determined by the rate of convergence toward stationarity of the Markov chains involved. There now exists a substantial body of work on this subject and to begin with a synopsis of “classical” techniques for bounding convergence rate is given. Such techniques are: coupling, spectral gap, conductance and canonical paths. The focus then shifts to recent improvements on these techniques followed by sample applications: the first one illustrates how the path coupling method simplifies the analysis of a Markov chain for generating random lozenge tilings. The next example highlights the gains made by average conductance over “classical” conductance for the bases-exchange walk on balanced matroids. The result for the latter example is obtained by an inductive argument and is subsequently improved by the use of so-called logarithmic Sobolev constants. Bounding the logarithmic Sobolev constant is here achieved by following a decomposition-cum-induction approach. Such decompositional approaches for analysing Markov chain convergence are another manifestation of the “divide-and-conquer” paradigm. The thesis concludes with the treatment of a novel decomposition method and its application to bounding the convergence rate of a random process on bounded Cayley trees.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:662270 |
| Date | January 2004 |
| Creators | Son, Jung-Bae |
| Publisher | University of Edinburgh |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/1842/23200 |
Page generated in 0.0014 seconds