Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T07:55:48.658Z Has data issue: false hasContentIssue false

Proof of the Hamiltonicity-Trace Conjecture for Singularly Perturbed Markov Chains

Published online by Cambridge University Press:  14 July 2016

Vladimir Ejov*
Affiliation:
University of South Australia
Nelly Litvak*
Affiliation:
University of Twente
Giang T. Nguyen*
Affiliation:
University of South Australia
Peter G. Taylor*
Affiliation:
University of Melbourne
*
∗ Postal address: School of Mathematics and Statistics, University of South Australia, Mawson Lakes campus, Mawson Lakes SA 5095, Australia. Email address: ejovvl@gmail.com
∗∗ Postal address: Faculty of Electrical Engineering, Mathematics and Computer Science, Department of Applied Mathematics, University of Twente, PO Box 217, 7500 AE Enschede, The Netherlands. Email address: n.litvak@ewi.utwente.nl
∗∗∗ Current address: Département d'informatique, Université Libre de Bruxelles, CP 212, Boulevard du Triomphe, 2, B-1050 Bruxelles, Belgium. Email address: giang.nguyen@ulb.ac.be
∗∗∗∗ Postal address: Department of Mathematics and Statistics, University of Melbourne, Parkville VIC 3010, Australia. Email address: p.taylor@ms.unimelb.edu.au
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2011