Minimising the largest mean first passage time of a Markov chain: The influence of directed graphs

For a Markov chain described by an irreducible stochastic matrix A of order n, the mean first passage time mi,j measures the expected time for the Markov chain to reach state j for the first time given that the system begins in state i, thus quantifying the short-term behaviour of the chain. In this article, a lower bound for the maximum mean first passage time is found in terms of the stationary distribution vector of A, and some matrices for which equality is attained are produced. The main objective of this article is to characterise the directed graphs for which any stochastic matrix A respecting this directed graph attains equality in this lower bound, producing a class of Markov chains with optimal short-term behaviour.