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

详细信息    查看全文

• 作者：Mengran  ; Xue  ; ;   ; ^{mxue@eecs.wsu.edu} ; Sandip  ; Roy
• 刊名：Journal of The Franklin Institute
• 出版年：2011
• 出版时间：November 2011
• 年：2011
• 卷：348
• 期：9
• 页码：2448-2467
• 全文大小：228 K

文摘

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.