5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Hamiltonian Transition Matrices

Download630 downloads
  • @INPROCEEDINGS{10.4108/icst.valuetools.2011.245841,
        author={Konstantin  Avrachenkov and Ali  Eshragh and Jerzy A.  Filar},
        title={Hamiltonian Transition Matrices},
        proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={6},
        keywords={hamiltonia path problem hamiltonian transition matrices markov chains},
        doi={10.4108/icst.valuetools.2011.245841}
    }
    
  • Konstantin Avrachenkov
    Ali Eshragh
    Jerzy A. Filar
    Year: 2012
    Hamiltonian Transition Matrices
    VALUETOOLS
    ICST
    DOI: 10.4108/icst.valuetools.2011.245841
Konstantin Avrachenkov1,*, Ali Eshragh2, Jerzy A. Filar2
  • 1: INRIA Sophia Antipolis France
  • 2: School of Mathematics and Statistics University of South Australia Australia
*Contact email: K.Avrachenkov@inria.fr

Abstract

In this pedagogical note, 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.