On the fastest finite Markov processes

Résumé

Consider a finite state irreducible Markov process with transition graph G and invariant probability distribution π. Its inverse communication speed is defined as the expectation of the time to go from x to y when are sampled independently according to π. We study this in the context of both discrete and continuous time. One of our goals is to show (under a suitable normalization condition on the transition rates for the continuous time case) that the shortest inverse communication speed among all Markov processes compatible with G and π is attained on those whose successive positions follow a Hamiltonian cycle, assuming one exists, and that π is close enough to the uniform distribution υ. This result is no longer true when π is sufficiently different from υ. Another purpose of the paper is to prove that when the invariance with respect to π is dropped and the inverse communication speed is replaced by the unweighted sum of the hitting times, then the Hamiltonian cycles, when they exist, are still the minimizers over all processes compatible with the prescribed directed graph G of permitted transitions, not only Markov processes, thus extending some previous results.

Mots-clés

Fastest Markov chains/processes; Communication speed; Spectra of Markov operators; Hamiltonian cycles; Dynamic programming; Differentiation of Markov operators;