Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain |
| |
| Authors: | Mengran Xue Sandip Roy |
| |
| Institution: | Department of Electrical Engineering, Washington State University, Pullman, WA, United States |
| |
| 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-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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
