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

### Zentralblatt MATH Berlin [Germany]

© FIZ Karlsruhe GmbH

Zentralblatt MATH master server is maintained by the Editorial Office in Berlin, Section Mathematics and Computer Science of FIZ Karlsruhe and is updated daily.

Other Mirror Sites

Copyright © 2013 Zentralblatt MATH | European Mathematical Society | FIZ Karlsruhe | Heidelberg Academy of Sciences