The Optimal Sink and the Best Source in a Markov Chain

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e. g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance ("information") that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.