RT Journal Article
SR 00
ID 10.1016/j.jmaa.2019.123488
A1 Miclo, Laurent
A1 Borkar, Vivek S.
T1 On the fastest finite Markov processes
JF Journal of Mathematical Analysis and Applications
YR 2020
FD 2020-01
VO vol. 481
IS n° 2
SP 123488
OP 123488
K1 Fastest Markov chains/processes
K1 Communication speed
K1 Spectra of Markov operators
K1 Hamiltonian cycles
K1 Dynamic programming
K1 Differentiation of Markov operators
AB 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.
PB Academic Press
SN 0022-247X
LK https://publications.ut-capitole.fr/id/eprint/33811/
UL http://tse-fr.eu/pub/123885