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

We pursue a spectral and graph-theoretic performance analysis of a classical estimator for Markov-chain steady state probabilities. Specifically, we connect a performance measure for the estimate to 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.