About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
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 Dayar1,*, Nihal Pekergin2,3,*, Sana Younes2,*
  • 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
Copyright © 2006–2025 ACM
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL