Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain

Abstract:

Motivated by the wide application of Markov-chain steady-state-probability estimation, we pursue a spectral and graph-theoretic performance analysis of a classical estimator for steady-state probabilities here. Specifically, we connect a performance measure to estimate the structure of the underlying graph defined on the Markov-chains state transitions. To do so, (1) we present a series of upper bounds on the performance measure in terms of the subdominant eigenvalue of the state transition matrix, which is closely connected with the graph structure; (2) as an illustration of the graph-theoretic analysis, we then relate the subdominant eigenvalue to the connectivity of the graph, including for the strong-connectivity case and the weak-link case. We also apply the results to characterize estimation in Markov chains with rewards. © 2011 The Franklin Institute.

Año de publicación:

2011

Keywords:

Fuente:

scopus