Ph.D. (2008) Cornell University
Abstract: In this dissertation, we study the limiting behavior of finite Markov chains. In particular we are interested in the time it takes for a Markov chain to merge. We say that a Markov chain is merging if the distributions of the chain started from two arbitrary initial distributions are asymptotically the same. In the case that the chain admits an invariant distribution, it will converge toward its invariant distribution.
When a Markov chain is driven by a single kernel, we say it is time homogeneous. Several classical models of time homogeneous Markov chains are considered. We give improved estimates for the time required for these models to reach their invariant distributions.
If the Markov chain is not driven by a single Markov kernel, then we say it is time inhomogeneous. In order to study the limiting behavior of time inhomogeneous finite Markov chains, we develop singular value, Nash inequality and logarithmic Sobolev techniques. We introduce the concept of c-stability which is a generalization of the Markov chain admitting an invariant measure. Using these techniques we analyze several examples of time inhomogeneous chains and obtain precise bounds on the time required for the chain to merge.