Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1052.65004
Neumann, M.; Xu, J.
Improved bounds for a condition number for Markov chains.
(English)
[J] Linear Algebra Appl. 386, 225-241 (2004). ISSN 0024-3795

Let $P$ and $\widetilde P=P+E$ be transition matrices of some finite ($n$ states) homogeneous ergodic Markov chains, $\pi$ and $\widetilde\pi$ be their stationary distributions. The article is devoted to the condition number $\kappa_4$, i.e. the constant for which $$|\pi-\widetilde\pi|_\infty\le\kappa_4|E|_\infty.$$ New upper bounds for $\kappa_4$ are obtained in terms of $Q=(q_{ij})_{i,j=1}^n=I-P$ and its group inverse $Q^{\#}$. E.g. $$\kappa_4\le { \delta_2+\sigma_2\delta_3+\dots+\sigma_{n-2}\delta_{n-1}+\sigma_{n-1} \over \chi },$$ where $$\sigma_k=\max_{j_1,j_2}(q_{j_2,j_1}+q_{j_2,j_2})\cdots \max_{j_1\dots j_k}(q_{j_k,j_1}+\dots+q_{j_k,j_k}),$$ $$\delta_k=\max_{j_1\dots j_k} {\prod_{i=1}^n q_{ii}\over q_{j_1j_1}\dots q_{j_kj_k}}, \chi=\prod_{\lambda_j\not=1}(1-\lambda_j),$$ $\lambda_j$ are eigenvalues of $P$. \par Numerical results show that these bounds are approximately two times better than the estimate of {\it C. D. Meyer} for $n=10$ [SIAM J. Matrix. Anal. Appl. 15, No.~3, 715--728 (1994; Zbl 0809.65143)].
[R. E. Maiboroda (Ky{\"\i}v)]
MSC 2000:
*65C40 Computational Markov chains
60J10 Markov chains with discrete parameter
65F35 Matrix norms, etc. (numerical linear algebra)

Keywords: stationary distribution; group inversion; perturbation theory; numerical results

Citations: Zbl 0809.65143

Highlights
Master Server