Two Characterizations of General Ergodic Markov Chain Families with Small First Passage Time

Markov chain is a stochastic process which has been found effective in modelling a wide variety of situations and phenomena in computer science. In many such applications, the first passage times of certain states of Markov chains become matters of interest. One such example is randomized search heuristics for solving combinatorial optimization problems. The execution of many such heuristics can be modelled by a Markov chain where each state corresponds to a feasible solution, and the target state is the one corresponding to minimum cost (for minimization problem). So the run time of such an algorithm is the first passage time of the target state. Other examples include gamble and situations that can be modelled as gambles, randomized routing algorithms in computer networks, etc. The thesis focusses on characterizing families of ergodic Markov chains having small first passage time of some goal state. To appropriately define `small', we consider Markov chains parametrized by binary strings and define `short first passage time' to be at most a fixed polynomial in the size of the string that gives rise to the chain. We introduce two notions of 'success' as we call it, and show them to be equivalent. The thesis presents two characterizations of success. The first one is that the ratio of the ergodic flow out of each set of states not containing the goal state to the capacity of the state is at least some inverse polynomial in the size of the string giving rise to the chain. The second characterization, which is easily seen to be a sufficient condition, is that the family of Markov chains is rapidly mixing and the stationary probability of the goal state is at least some inverse polynomial in the size of the generating string. Thus rapid mixing and first passage time turn out to be closely related. Finally we illustrate the applicability of our results by giving alternative proofs of some known results due to Wegener on performance of the Metropolis algorithm on the minimum spanning tree problem for connecting triangles.