Minimizing the average mean-first passage time for Markov chains associated with a graph

Historically Markov chains have been one of the most useful tools for modeling a wide range of dynamical systems. Given a Markov chain there are three fundamental questions: What is the long-term behavior? How fast does the chain approach the long-term behavior? What is the short-term behavior?;For example, if the Markov chain is that associated with Google's PageRank which models randomly surfing the world wide web, the long-term behavior is given by the distribution that records the expected portion of time that the surfer would be at any given url; a fast speed of convergence allows Google to approximate the long-term behavior by random walks of under 50 steps; and the short-term behavior concerns what is the expected number of steps for a random walk starting at url x to first encounter a url y.;This dissertation is concerned with the short-term behavior of Markov chains. Given a Markov chain, and states i and j , the mean first passage time from i to j is the expected value of the number of steps that it takes to first reach state j given that the initial state is i. The average mean first passage time is the average of the mean first passage times over all states i and j. The average mean first passage time is also known as the Kemeny constant, and in the case that the Markov chain is finite and given by the transition matrix P can be expressed nicely in terms of the eigenvalues of P.;This dissertation concerns an optimization problem for Markov chains with a given structure. The structure is prescribed by a connected graph G on n vertices, and Mark(G) is the set of all n x n, symmetric, stochastic matrices P = [pij] such that pij > 0 only if i = j or i is adjacent to j in G. The optimization problem is to determine the infinimum of the Kemeny constant over Mark(G).;The main results of the dissertation are: (a) The infimum of the Kemeny constant over Mark(G) is achieved by a matrix in Mark( G). (b) The minimum Kemeny constant over Mark(G) is achieved by a matrix which is invariant under each graph automorphism of G. (c) The determination of the graphs on n vertices with largest and smallest minimum Kemeny constant. (d) Results on the structure of the transition matrices that achieve the smallest minimum Kemeny constant for a given graph G. (e) The determination of the minimum Kemeny constant for many families of graphs including: complete graphs, paths, stars, brooms, double-brooms, generalized stars,suns, windmills, and unions of two cliques.