Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]