Name
Title | ||
|---|---|---|
Spectral and graph-theoretic bounds on steady-state-probability estimation performance for an ergodic Markov chain |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/ACC.2011.5990901 | Journal of The Franklin Institute-engineering and Applied Mathematics |
Keywords | Field | DocType |
markov processes,eigenvalues and eigenfunctions,graph theory,matrix algebra,probability,markov-chain steady state probabilities,ergodic markov chain,graph structure,graph-theoretic bounds,performance measure,spectral bounds,state transition matrix,steady-state-probability estimation performance,strong-connectivity case,subdominant eigenvalue,weak-link case,estimation,covariance matrix,steady state,upper bound | Adjacency matrix,Discrete mathematics,Markov chain mixing time,Graph energy,Spectral graph theory,Markov chain,Markov kernel,Mathematics,Absorbing Markov chain,Examples of Markov chains | Journal |
Volume | Issue | ISSN |
348 | 9 | 0743-1619 |
ISBN | Citations | PageRank |
978-1-4577-0080-4 | 6 | 0.67 |
References | Authors | |
17 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mengran Xue | 1 | 61 | 13.36 |
| Sandip Roy | 2 | 301 | 53.03 |