Stochastic matrix: Definition from Answers.com

In mathematics, a stochastic matrix, probability matrix, or transition matrix is used to describe the transitions of a Markov chain. It has found use in probability theory, statistics and linear algebra, as well as computer science. There are several different definitions and types of stochastic matrices;

A right stochastic matrix is a square matrix each of whose rows consists of nonnegative real numbers, with each row summing to 1.

A left stochastic matrix is a square matrix whose columns consist of nonnegative real numbers whose sum is 1.

A doubly stochastic matrix where all entries are nonnegative and all rows and all columns sum to 1.

A common convention in English language mathematics literature is to use the right stochastic matrix; this convention will be used in this article.

In the same vein, one may define a stochastic vector as a vector whose elements consist of nonnegative real numbers which sum to 1. Thus, each row (or column) of a stochastic matrix is a probability vector, which are sometimes called stochastic vectors.

1 Definition and properties
2 Example: the cat and mouse
- 2.1 Long term averages
- 2.2 Phase-type representation
3 See also
4 References

Definition and properties

A stochastic matrix describes a Markov chain $\boldsymbol{X}_{t}$ over a finite state space S.

If the probability of moving from $i$ to $j$ in one time step is $P r (j | i) = P i, j$ , the stochastic matrix P is given by using $P i, j$ as the $i t h$ row and $j t h$ column element, e.g.,

$P=\left(\begin{matrix}p_{1,1}&p_{1,2}&\dots&p_{1,j}&\dots\\ p_{2,1}&p_{2,2}&\dots&p_{2,j}&\dots\\ \vdots&\vdots&\ddots&\vdots&\ddots\\ p_{i,1}&p_{i,2}&\dots&p_{i,j}&\dots\\ \vdots&\vdots&\ddots&\vdots&\ddots \end{matrix}\right)$

Since the probability of transitioning from state $i$ to some state must be 1, we have that this matrix is a right stochastic matrix, so that

$\sum_j P_{i,j}=1\,$

The probability of transitioning from $i$ to $j$ in two steps is then given by the $(i, j) t h$ element of the square of $P$ :

$\left(P ^{2}\right)_{i,j}$ .

In general the probability transition of going from any state to another state in a finite Markov chain given by the matrix $P$ in k steps is given by $P k$ .

An initial distribution is given as a row vector.

A stationary probability vector $\boldsymbol{\pi}$ is defined as a vector that does not change under application of the transition matrix; that is, it is defined as a left eigenvector of the probability matrix, associated with eigenvalue 1:

$\boldsymbol{\pi}P=\boldsymbol{\pi}$ .

The Perron-Frobenius theorem ensures that such a vector exists, and that the largest eigenvalue associated with a stochastic matrix is always 1. For a matrix with strictly positive entries, this vector is unique. In general, however, there may be several such vectors.

For a matrix with strictly positive entries, this vector can be computed by observing that for any $i$ we have the following limit,

$\lim_{k\rightarrow\infty}\left(P^{k}\right)_{i,j}=\boldsymbol{\pi}_{j}$ ,

where $\boldsymbol{\pi}_{j}$ is the $j t h$ element of the row vector $\boldsymbol{\pi}$ . This implies that the long-term probability of being in a state $j$ is independent of the initial state $i$ . That either of these two computations give one and the same stationary vector is a form of an ergodic theorem, which is generally true in a wide variety of dissipative dynamical systems: the system evolves, over time, to a stationary state.

Example: the cat and mouse

Suppose you have a timer and a row of five adjacent boxes, with a cat in the first box and a mouse in the fifth one at time zero. The cat and the mouse both jump to a random adjacent box when the timer advances. E.g. if the cat is in the second box and the mouse in the fourth one, the probability is one fourth that the cat will be in the first box and the mouse in the fifth after the timer advances. When the timer advances again, the probability is one that the cat is in box two and the mouse in box four. The cat eats the mouse if both end up in the same box, at which time the game ends. The random variable K gives the number of time steps the mouse stays in the game.

The Markov chain that represents this game contains the following five states:

State 1: cat in the first box, mouse in the third box: (1, 3)
State 2: cat in the first box, mouse in the fifth box: (1, 5)
State 3: cat in the second box, mouse in the fourth box: (2, 4)
State 4: cat in the third box, mouse in the fifth box: (3, 5)
State 5: the cat ate the mouse and the game ended: F.

We use a stochastic matrix to represent the transition probabilities of this system,

$P = \begin{bmatrix} 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1 & 0 & 0 \\ 1/4 & 1/4 & 0 & 1/4 & 1/4 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}.$

Long term averages

As state five is an absorbing state the long term average vector $\boldsymbol{\pi}=(0,0,0,0,1)$ . Regardless of the initial conditions the cat will eventually catch the mouse.

Phase-type representation

The survival function of the mouse. Note the mouse will survive at least the first time step.

As the game has an absorbing state 5 the distribution of time to absorption is discrete phase-type distributed. Therefore by letting

$\boldsymbol{\tau}=[0,1,0,0]$

and by removing state five to make a sub-stochastic matrix,

$T=\begin{bmatrix} 0 & 0 & 1/2 & 0\\ 0 & 0 & 1 & 0\\ 1/4 & 1/4 & 0 & 1/4\\ 0 & 0 & 1/2 & 0\\ \end{bmatrix},$

then the expected time of the mouse's survival is,

$E[K]=\boldsymbol{\tau}(I-T)^{-1}\boldsymbol{1}=4.5$ .

Higher order moments are given by,

$E[K(K-1)\dots(K-n+1)]=n!\boldsymbol{\tau}(I-{T})^{-n}{T}^{n-1}\mathbf{1}$ .

Where $I$ is the identity matrix, and $\mathbf{1}$ represents a column matrix of all ones.

References

G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modelling, 1st edition. Chapter 2: PH Distributions; ASA SIAM, 1999.
José H. Nieto, Marko Riedel, El gato, el reloj y el ratón., newsgroup es.ciencia.matematicas

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What is the difference between stochastic and random? Read answer...
	What is the difference between stochastic and deterministic? Read answer...
	What is the difference between 'stochastic' and 'probabilistic'? Read answer...

	What is a stochastic variable?
	What is Demographic stochasticity?
	What is the application of stochastic process?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Stochastic matrix". Read more

Stochastic matrix

Contents

Definition and properties

Example: the cat and mouse

Long term averages

Phase-type representation

See also

References