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.
Type de document :
Article dans une revue
Annals of Operations Research, Springer Verlag, 2016, 243 (1-2), pp.19 - 35. 〈http://link.springer.com/article/10.1007%2Fs10479-014-1642-2〉. 〈10.1007/s10479-014-1642-2〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402827
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 25 novembre 2016 - 11:21:48
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : mardi 21 mars 2017 - 15:29:50

Fichier

HamMatrixRev1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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. 〈http://link.springer.com/article/10.1007%2Fs10479-014-1642-2〉. 〈10.1007/s10479-014-1642-2〉. 〈hal-01402827〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

125