Stochastic matrix

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A square (possibly infinite) matrix with non-negative elements, for which

The set of all stochastic matrices of order is the convex hull of the set of stochastic matrices consisting of zeros and ones. Any stochastic matrix can be considered as the matrix of transition probabilities of a discrete Markov chain .

The absolute values of the eigenvalues of stochastic matrices do not exceed 1; 1 is an eigenvalue of any stochastic matrix. If a stochastic matrix is indecomposable (the Markov chain has one class of positive states), then 1 is a simple eigenvalue of (i.e. it has multiplicity 1); in general, the multiplicity of the eigenvalue 1 coincides with the number of classes of positive states of the Markov chain . If a stochastic matrix is indecomposable and if the class of positive states of the Markov chain has period , then the set of all eigenvalues of , as a set of points in the complex plane, is mapped onto itself by rotation through an angle . When , the stochastic matrix and the Markov chain are called aperiodic.

The left eigenvectors of of finite order, corresponding to the eigenvalue :

 (1)

and satisfying the conditions , , define the stationary distributions of the Markov chain ; in the case of an indecomposable matrix , the stationary distribution is unique.

If is an indecomposable aperiodic stochastic matrix of finite order, then the following limit exists:

 (2)

where is the matrix all rows of which coincide with the vector (see also Markov chain, ergodic; for infinite stochastic matrices , the system of equations (1) may have no non-zero non-negative solutions that satisfy the condition ; in this case is the zero matrix). The rate of convergence in (2) can be estimated by a geometric progression with any exponent that has absolute value greater than the absolute values of all the eigenvalues of other than 1.

If is a stochastic matrix of order , then any of its eigenvalues satisfies the inequality (see [3]):

The union of the sets of eigenvalues of all stochastic matrices of order has been described (see [4]).

A stochastic matrix that satisfies the extra condition

is called a doubly-stochastic matrix. The set of doubly-stochastic matrices of order is the convex hull of the set of permutation matrices of order (i.e. doubly-stochastic matrices consisting of zeros and ones). A finite Markov chain with a doubly-stochastic matrix has the uniform stationary distribution.

References

 [1] F.R. [F.R. Gantmakher] Gantmacher, "The theory of matrices" , 1 , Chelsea, reprint (1977) (Translated from Russian) [2] R. Bellman, "Introduction to matrix analysis" , McGraw-Hill (1960) [3] M. Marcus, H. Minc, "A survey of matrix theory and matrix inequalities" , Allyn & Bacon (1964) [4] F.I. Karpelevich, "On the characteristic roots of matrices with non-negative entries" Izv. Akad. Nauk SSSR Ser. Mat. , 15 (1951) pp. 361–383 (In Russian)

Given a real -matrix with non-negative entries, the question arises whether there are invertible positive diagonal matrices and such that is a doubly-stochastic matrix, and to what extent the and are unique. Such theorems are known as -theorems. They are of interest in telecommunications and statistics, [a3][a5].

A matrix is fully decomposable if there do not exist permutation matrices and such that

A -matrix is fully indecomposable if it is non-zero.

Then for a non-negative square matrix there exist positive diagonal matrices and such that is doubly stochastic if and only if there exist permutation matrices and such that is a direct sum of fully indecomposable matrices [a1], [a2].

References

 [a1] R. Sinkhorn, P. Knopp, "Concerning nonnegative matrices and doubly stochastic matrices" Pacific J. Math. , 21 (1967) pp. 343–348 [a2] R.A. Brualdi, S.V. Parter, H. Schneider, "The diagonal equivalence of a nonnegative matrix to a stochastic matrix" J. Math. Anal. Appl. , 16 (1966) pp. 31–50 [a3] S. Fienberg, "An iterative procedure for estimation in contingency tables" Ann. Math. Stat. , 41 (1970) pp. 907–917 [a4] R.S. Krupp, "Properties of Kruithof's projection method" Bell Systems Techn. J. , 58 (1979) pp. 517–538 [a5] I. Csiszár, "I-divergence geometry of probability distributions and minimization problems" Ann. Probab. , 3 (1975) pp. 146–158 [a6] R.D. Nussbaum, "Iterated nonlinear maps and Hilbert's projective method II" Memoirs Amer. Math. Soc. , 401 (1989) [a7] M.F. Neuts, "Structured stochastic matrices of type and their applications" , M. Dekker (1989) [a8] E. Seneta, "Non-negative matrices and Markov chains" , Springer (1981)
How to Cite This Entry:
Stochastic matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stochastic_matrix&oldid=15634
This article was adapted from an original article by A.M. Zubkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article