The Minimum Coefficient of Ergodicity for a Markov Chain with a Given Directed Graph

Suppose that T is an n×n stochastic matrix, and denote its directed graph by D(T). The function τ(T) = 12 maxi,j=1,...,n{||(ei − ej)>T ||1} is known as a coefficient of ergodicity for T, and measures the rate at which the iterates of a Markov chain with transition matrix T converge to the stationary distribution vector. Many Markov chains are equipped with an underlying combinatorial structure that is described by a directed graph, and in view of that fact, we consider the following problem: given a directed graph D, find τmin(D) ≡ min τ(T), where the minimum is taken over all stochastic matrices T such that D(T) is a spanning subgraph of D. In this paper, we characterise τmin(D) as the solution to a linear program-ming problem. We then go on to provide an upper bound on τmin(D) in terms of the maximum outdegree of D, and a lower bound on τmin(D) in terms of the maximum indegree of D, characterising the equality cases in both bounds. Connections are established between the equality case in the lower bound and certain balanced incomplete block designs