Miclo, Laurent and Borkar, Vivek S. (2020) On the fastest finite Markov processes. Journal of Mathematical Analysis and Applications, vol. 481 (n° 2). p. 123488.

[thumbnail of pii/S0022247X19307565] Text
Download (93kB)
Identification Number : 10.1016/j.jmaa.2019.123488


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.

Item Type: Article
Language: English
Date: January 2020
Refereed: Yes
Uncontrolled Keywords: Fastest Markov chains/processes, Communication speed, Spectra of Markov operators, Hamiltonian cycles, Dynamic programming, Differentiation of Markov operators
Divisions: Institut de mathématiques de Toulouse, TSE-R (Toulouse)
Site: UT1
Date Deposited: 20 Jan 2020 14:58
Last Modified: 02 Sep 2021 12:59
OAI Identifier: oai:tse-fr.eu:123885
URI: https://publications.ut-capitole.fr/id/eprint/33811
View Item


Downloads per month over past year