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

Vladimir Ejov; Nelly Litvak; Giang Nguyen; Peter Taylor

doi:10.1239/jap/1324046008

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

Vladimir Ejov, Nelly Litvak, Giang Nguyen, Peter Taylor

Research output: Contribution to journal › Article › peer-review

6 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 language	English
Pages (from-to)	901-910
Number of pages	10
Journal	JOURNAL OF APPLIED PROBABILITY
Volume	48
Issue number	4
DOIs	https://doi.org/10.1239/jap/1324046008
Publication status	Published - Dec 2011

Keywords

Hamiltonian cycle
Perturbed Markov chain
Stochastic matrix

Access to Document

10.1239/jap/1324046008

Cite this

@article{d6bfe6e5e1b0481b8fdf485923e14558,

title = "Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains",

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.",

keywords = "Hamiltonian cycle, Perturbed Markov chain, Stochastic matrix",

author = "Vladimir Ejov and Nelly Litvak and Giang Nguyen and Peter Taylor",

year = "2011",

month = dec,

doi = "10.1239/jap/1324046008",

language = "English",

volume = "48",

pages = "901--910",

journal = "JOURNAL OF APPLIED PROBABILITY",

issn = "0021-9002",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

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

AU - Ejov, Vladimir

AU - Litvak, Nelly

AU - Nguyen, Giang

AU - Taylor, Peter

PY - 2011/12

Y1 - 2011/12

N2 - 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.

AB - 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.

KW - Hamiltonian cycle

KW - Perturbed Markov chain

KW - Stochastic matrix

UR - http://www.scopus.com/inward/record.url?scp=84855256018&partnerID=8YFLogxK

U2 - 10.1239/jap/1324046008

DO - 10.1239/jap/1324046008

M3 - Article

SN - 0021-9002

VL - 48

SP - 901

EP - 910

JO - JOURNAL OF APPLIED PROBABILITY

JF - JOURNAL OF APPLIED PROBABILITY

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this