Journal article
Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains
V Ejov, N Litvak, GT Nguyen, PG Taylor
Journal of Applied Probability | CAMBRIDGE UNIV PRESS | Published : 2011
Abstract
We prove the conjecture formulated in Litvak and Ejov (2009), namely, that the trace of the fundamental matrix of a singularly perturbed Markov chain that corresponds to a stochastic policy feasible for a given graph is minimised at policies corresponding to Hamiltonian cycles. © 2011 Applied Probability Trust.
Grants
Awarded by Netherlands Organisation for Scientific Research (NWO)
Awarded by Australian Research Council
Funding Acknowledgements
The authors gratefully acknowledge the support of the Netherlands Organisation for Scientific Research (NWO), under Meervoud grant number 632.002.401, the Australian Research Council Discovery Grant DP0666632, the Australian Research Council Linkage International Grants LX0560049 and LX0881972, and the Australian Research Council Centre of Excellence in the Mathematics and Statistics of Complex Systems. The authors are indebted to an anonymous referee and J. A. Filar for many insightful comments and discussions.