Naive asymptotics for hitting time bounds in Markov chains

A set of sufficient conditions is obtained for Markov chains to yield upper and lower passage time bounds. While obtaining expected passage times is strictly a numerical procedure for general Markov chains, the results presented here outline a simple approach to bound expected passage times provided...

Full description

Saved in:
Bibliographic Details
Published in:Acta informatica 1992-06, Vol.29 (6-7), p.579-594
Main Author: REGO, V
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set of sufficient conditions is obtained for Markov chains to yield upper and lower passage time bounds. While obtaining expected passage times is strictly a numerical procedure for general Markov chains, the results presented here outline a simple approach to bound expected passage times provided the chains satisfy certain easy to check criteria. The results may be useful in modelling situations, such as in the analysis of algorithms, where simple ways of obtaining average complexity estimates are required.
ISSN:0001-5903
1432-0525
DOI:10.1007/BF01185562