The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities
Carl Dean Meyer · SIAM Journal on Algebraic and Discrete Methods · 1980
Let ${\mathbf{T}}$ denote the transition matrix of an ergodic chain, $\mathbf{\mathcal{C}}$ , and let ${\mathbf{A}} = {\mathbf{I}} - {\mathbf{T}}$. Let ${\mathbf{E}}$ be a perturbation matrix such that $\mathbf{\tilde{T}} = {\mathbf{T}} - {\mathbf{E}}$ is also the transition matrix of an ergodic chain, $\mathbf{\tilde{\mathcal{C}}}$. Let $\boldsymbol{\omega} $ and $\boldsymbol{\tilde \omega} $ denote the limiting probability (row) vectors for $\mathbf{\mathcal{C}}$ and $\mathbf{\tilde{\mathcal{C}}}$. The purpose of this paper is to exhibit inequalities bounding the relative error $\| \boldsymbol{\omega} - \boldsymbol{\tilde \omega} \| / \| \boldsymbol{\omega} \|$ by a very simple function of ${\mathbf{E}}$ and ${\mathbf{A}}$. Furthermore, the inequality will be shown to be the best one which is possible. This bound can be significant in the numerical determination of the limiting probabilities for an ergodic chain. In addition to presenting a sharp bound for $\| \boldsymbol{\omega} - \boldsymbol{\tilde \omega} \| / \| \boldsymbol{\omega} \|$, we will derive an explicit expression for $\boldsymbol{\tilde \omega} $, in which $\boldsymbol{\tilde \omega} $ is given as a function of ${\mathbf{E}},{\mathbf{A}},\boldsymbol{\omega} $ and some other related terms.