Stochastic matrix

From Free net encyclopedia

In mathematics, especially in probability theory and statistics, and also in linear algebra and computer science, a left stochastic matrix is a square matrix whose columns are probability vectors, i.e., the entries in each column are nonnegative real numbers whose sum is 1. Likewise, a right stochastic matrix is a square matrix whose rows are probability vectors. In a doubly stochastic matrix all rows and all columns are probability vectors. Stochastic matrices can be considered representations of the transition probabilities of a finite Markov chain.

Here is an example of a right stochastic matrix P:

<math>P = \begin{bmatrix}

0.5 & 0.3 & 0.2 \\ 0.2 & 0.8 & 0 \\ 0.3 & 0.3 & 0.4 \end{bmatrix}</math>

If G is a left stochastic matrix, then a steady-state vector or equilibrium vector for G is a probability vector h such that:

<math> Gh = h </math>

An example:

<math>G = \begin{bmatrix}

0.95 & 0.03 \\ 0.05 & 0.97 \end{bmatrix}</math> and

<math>h = \begin{bmatrix}

0.375 \\ 0.625 \end{bmatrix}</math>

<math>Gh = \begin{bmatrix}

0.95 & 0.03 \\ 0.05 & 0.97 \end{bmatrix}

\begin{bmatrix}

0.375 \\ 0.625 \end{bmatrix} = \begin{bmatrix} 0.35625 + 0.01875 \\ 0.01875 + 0.60625 \end{bmatrix} = \begin{bmatrix} 0.375 \\ 0.625 \end{bmatrix}</math>

This case shows that Gh = 1h. For equations that show Gh = βh for some real number β, like Gh = 4h or Gh = −21h, see eigenvector.

A stochastic matrix P is regular if some matrix power P^k contains only strictly positive entries.

Using stochastic matrix P, from above:

<math>P^2 = \begin{bmatrix}

0.37 & 0.26 & 0.33 \\ 0.45 & 0.70 & 0.45 \\ 0.18 & 0.04 & 0.22 \end{bmatrix}</math>

Therefore, P is a regular stochastic matrix.

The Stochastic Matrix Theorem says if A is a regular stochastic matrix, then A has a steady-state vector t so that if x_o is any initial state and x_k+1 = Ax_k for k = 0, 1, 2, ..... then the Markov chain {x_k} converges to t as k -> infinity. That is:

<math>\lim_{k \to \infty} A^k \textbf{x}_0 = \textbf{t}.</math>

See also Muirhead's inequality and Perron-Frobenius theorem.fr:matrice stochastique