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

Vladimir Ejov, Nelly Litvak, Giang Nguyen, Peter Taylor

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)901-910
    Number of pages10
    JournalJOURNAL OF APPLIED PROBABILITY
    Volume48
    Issue number4
    DOIs
    Publication statusPublished - Dec 2011

    Keywords

    • Hamiltonian cycle
    • Perturbed Markov chain
    • 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