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

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

doi:10.1239/jap/1324046008

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

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

Stochastic Operations Research

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

6 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 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 - 2011

Keywords

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

Access to Document

10.1239/jap/1324046008

Cite this

@article{b513adf33f134d0ba0ce984d39e94d07,

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

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

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

author = "Vladimir Ejov and Nelly Litvak and Nguyen, {Giang T.} and Taylor, {Peter G.}",

year = "2011",

doi = "10.1239/jap/1324046008",

language = "English",

volume = "48",

pages = "901--910",

journal = "Journal of applied probability",

issn = "0021-9002",

publisher = "University of Sheffield",

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

AU - Taylor, Peter G.

PY - 2011

Y1 - 2011

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

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

KW - EWI-21160

KW - MSC-60J10

KW - MSC-05C45

KW - MSC-11C20

KW - METIS-284962

KW - Perturbed Markov chain

KW - IR-79218

KW - Hamiltonian cycle

KW - Stochastic matrix

U2 - 10.1239/jap/1324046008

DO - 10.1239/jap/1324046008

M3 - Article

VL - 48

SP - 901

EP - 910

JO - Journal of applied probability

JF - Journal of applied probability

SN - 0021-9002

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this