Markov Chain Problems with Applications

点击翻译按钮获取中文摘要

This research project examines problems which demand a better understanding of and analysis of certain reversible and nonreversible Markov chains. In particular, applying Markov chain techniques to develop approximate algorithms which solve such problems as: (1) Counting Euler tours, using Monte Carlo methods; (2) Counting tournaments, using Markov chain techniques. Another aspect of the project is the step by step proof of a `conjectured` optimal bound for the expected time for n random walks on a graph to coalesce to a single walk. The final part of this project focuses on extensions of results on rapidly mixing reversible Markov chains to nonreversible chains.