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

2 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

Fingerprint

Hamiltonicity
Singularly Perturbed
Markov chain
Trace
Fundamental Matrix
Hamiltonian circuit
Graph in graph theory
Policy
Graph

Keywords

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

Cite this

Ejov, Vladimir ; Litvak, Nelly ; Nguyen, Giang T. ; Taylor, Peter G. / Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains. In: Journal of applied probability. 2011 ; Vol. 48, No. 4. pp. 901-910.
@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",

}

Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains. / Ejov, Vladimir; Litvak, Nelly; Nguyen, Giang T.; Taylor, Peter G.

In: Journal of applied probability, Vol. 48, No. 4, 2011, p. 901-910.

Research output: Contribution to journalArticleAcademicpeer-review

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 -