This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Litvak, N. Articles by Ejov, V. Search for Related Content

Markov Chains and Optimality of the Hamiltonian Cycle

Faculty of Electrical Engineering, Mathematics and Computer Science, Department of Applied Mathematics, University of Twente, 7500 AE, Enschede, The Netherlands
Centre of Industrial and Applied Mathematics, School of Mathematics and Statistics, University of South Australia, Mawson Lakes, South Australia 5095, Australia
N.Litvak{at}ewi.utwente.nl
Vladimir.Ejov{at}unisa.edu.au

We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental matrix for all admissible values of the perturbation parameter. In contrast to the previous work on this topic, our arguments are primarily based on probabilistic rather than algebraic methods.

Key Words: Markov chains; Hamiltonian cycle; fundamental matrix; singular perturbation
History: Received: June 6, 2007; revision received: August 8, 2008;