Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains

Vladimir Ejov, Nelly Litvak, Giang T. Nguyen, Peter G. Taylor

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

We prove the conjecture formulated in Litvak and Ejov (2009), 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.
Original languageEnglish
Pages (from-to)901-910
Number of pages10
JournalJournal of applied probability
Volume48
Issue number4
DOIs
Publication statusPublished - 2011

Keywords

  • EWI-21160
  • MSC-60J10
  • MSC-05C45
  • MSC-11C20
  • METIS-284962
  • Perturbed Markov chain
  • IR-79218
  • Hamiltonian cycle
  • Stochastic matrix

Fingerprint Dive into the research topics of 'Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains'. Together they form a unique fingerprint.

  • Cite this