Conditional steady-state bounds for a subset of states in Markov chains

Tugrul  Dayar; Nihal  Pekergin; Sana  Younes

1st International ICST Workshop on Tools for solving Structured Markov Chains

Research Article

Conditional steady-state bounds for a subset of states in Markov chains

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1145/1190366.1190368,
    author={Tugrul  Dayar and Nihal  Pekergin and Sana  Younes},
    title={Conditional steady-state bounds for a subset of states in Markov chains},
    proceedings={1st International ICST Workshop on Tools for solving Structured Markov Chains},
    publisher={ACM},
    proceedings_a={SMCTOOLS},
    year={2012},
    month={4},
    keywords={Markov chains conditional steady-state vector stochastic comparison strong stochastic order bounding},
    doi={10.1145/1190366.1190368}
}

Tugrul Dayar
Nihal Pekergin
Sana Younes
Year: 2012
Conditional steady-state bounds for a subset of states in Markov chains
SMCTOOLS
ACM
DOI: 10.1145/1190366.1190368

Tugrul Dayar¹^,*, Nihal Pekergin^2,3^,*, Sana Younes²^,*

1: Department of Computer Engineering, Bilkent University, TR-06800 Bilkent, Ankara, Turkey
2: PRiSM, Universite de Versailles-St.Quentin, 45 av. des Etats Unis, 78035 Versailles, France.
3: Centre Marin Mersenne, Universite Paris 1, 90 rue Tolbiac, 75013 Paris, France.

*Contact email: tugrul@cs.bilkent.edu.tr, nih@prism.uvsq.fr, sayo@prism.uvsq.fr

Abstract

The problem of computing bounds on the conditional steady-state probability vector of a subset of states in finite, ergodic discrete-time Markov chains (DTMCs) is considered. An improved algorithm utilizing the strong stochastic (st-)order is given. On standard benchmarks from the literature and other examples, it is shown that the proposed algorithm performs better than the existing one in the strong stochastic sense. Furthermore, in certain cases the conditional steady-state probability vector of the subset under consideration can be obtained exactly.

Keywords: Markov chains conditional steady-state vector stochastic comparison strong stochastic order bounding

Published: 2012-04-05
Publisher: ACM

: http://dx.doi.org/10.1145/1190366.1190368