On optimal condition numbers for Markov chains

DOI10.1007/S00211-008-0172-8MaRDI QIDQ957931zbMATH OpenOpenAlexFDO

Authors S. J. Kirkland, M. Neumann, Nung-Sing Sze

Publication date 1 December 2008

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00211-008-0172-8

condition numbers ergodicity coefficients finite Markov chains perturbation bounds

Conditioning of matrices (15A12) Stochastic matrices (15B51) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Review text

The authors consider the sensitivity of the stationary distribution of finite homogeneous ergodic Markov chain to perturbations in its transition matrix. Let \(T\) and \({\tilde T} = T - E\) be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on \(n\) states. A function \(\kappa(T)\) is called a condition number for Markov chains with respect to the \((\alpha,\beta)\)-norm pair if \(\|\pi- \tilde{\pi}\|_\alpha \leq \kappa(T)\|E\|_\beta\). Here \(\pi\) and \({\tilde \pi}\) are the stationary distribution vectors of the two chains, respectively, \(E\) is the perturbation in transition matrix. Various condition numbers, particularly with respect to the \((1, \infty)\) and \((\infty, \infty)\)-norm pairs have been suggested in the literature. They were ranked according to their size by \textit{G. E. Cho} and \textit{C. D. Meyer} [Linear Algebra Appl. 335, 137--150 (2001; Zbl 0983.60062)]. In this paper it is shown that the generalized ergodicity coefficient \[ \tau_p(A^{\#}) = \sup_{y^te=0} \frac {\| y^t A^{\#} \|_p} {\|y\|_1}, \] where \(e\) is the \(n\)-vector of all 1's and \(A^{\#}\) is the group generalized inverse of \(A = I - T\), is the smallest condition number of Markov chains with respect to the \((p, \infty)\)-norm pair. This result is used to identify the smallest condition number of Markov chains among the \((\infty, \infty)\) and \((1, \infty)\)-norm pairs. These are, respectively, \(\kappa_3\) and \(\kappa_6\) in the Cho-Meyer list of 8 condition numbers. Kirkland has shown that \(\kappa_3(T)\geq (n-1)/(2n)\) and he has characterized transition matrices for which equality holds. In the paper it is proved again that \(2\kappa_3(T)\leq \kappa_6(T)\) which appears in the Cho-Meyer paper. Transition matrices \(T\) for which \(\kappa_6(T)= (n-1)/n\) are characterized. There is actually only one such matrix: \(T = (J_n - I)/(n - 1)\), where \(J_n\) is the \(n \times n\) matrix of all 1 's.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: On optimal condition numbers for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957931)