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

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-chainʹs 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.