On the Hamiltonicity gap and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singu-larly perturbed (controlled) Markov chains. We also consider a func-tional on the space of stationary policies of the process that consists of the (1,1)-entry of the fundamental matrices of the Markov chains induced by these policies. We focus on the subset of these policies that induce doubly stochastic probability transition matrices which we re-fer to as the “doubly stochastic policies”. We show that when the perturbation parameter, ε, is sufficiently small, the minimum of this functional over the space of the doubly stochastic policies is attained at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non-Hamiltonian, the above mini-mum is strictly greater than that in a Hamiltonian case. We call the size of this difference the “Hamiltonicity Gap ” and derive a conserva-tive lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the vari-ance of the first hitting time of the home node, over doubly stochastic policies. Key words: Hamiltonian cycle, controlled Markov chains, optimal policy, singular perturbation