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)

8 Downloads (Pure)

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

2024 OA procedure
MSC-60J10
MSC-05C45
MSC-11C20
Perturbed Markov chain
Hamiltonian cycle
Stochastic matrix

Access to Document

10.1239/jap/1324046008

ArticleLicence: Taverne

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 = "2024 OA procedure, MSC-60J10, MSC-05C45, MSC-11C20, Perturbed Markov chain, 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 = "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 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 - 2024 OA procedure

KW - MSC-60J10

KW - MSC-05C45

KW - MSC-11C20

KW - Perturbed Markov chain

KW - Hamiltonian cycle

KW - Stochastic matrix

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

Fingerprint

Cite this