Skip to Main content Skip to Navigation
Journal articles

On transition matrices of Markov chains corresponding to Hamiltonian cycles

Abstract : In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix P in this class corresponds to a Hamiltonian cycle in a given graph G on n nodes and to an irreducible, periodic, Markov chain. We show that a number of important matrices traditionally associated with Markov chains, namely, the stationary, fundamental, deviation and the hitting time matrix all have elegant expansions in the first n−1 powers of P , whose coefficients can be explicitly derived. We also consider the resolvent-like matrices associated with any given Hamiltonian cycle and its reverse cycle and prove an identity about the product of these matrices.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Friday, November 25, 2016 - 11:21:48 AM
Last modification on : Friday, July 8, 2022 - 10:04:16 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 3:29:50 PM


Files produced by the author(s)




Konstantin Avrachenkov, Ali Eshragh, Jerzy A. Filar. On transition matrices of Markov chains corresponding to Hamiltonian cycles. Annals of Operations Research, Springer Verlag, 2016, 243 (1-2), pp.19 - 35. ⟨10.1007/s10479-014-1642-2⟩. ⟨hal-01402827⟩



Record views


Files downloads