NationMaster - Encyclopedia: Stochastic matrix

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; For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... Probability theory is the branch of mathematics concerned with analysis of random phenomena. ... This article is about the field of statistics. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

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 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 mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... This article or section does not adequately cite its references or sources. ... The English language is a West Germanic language that originates in England. ...

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 stochastic vector. Stochastic vectors are also sometimes called probability vectors. In linear algebra, a row vector is a 1 Ã— n matrix, that is, a matrix consisting of a single row: The transpose of a row vector is a column vector. ... In mathematics and statistics, a probability vector or stochastic vector is a vector with non-negative entries that add up to one. ...

1 Definition and properties
2 Example: the cat and mouse
3 See also
4 References

Definition and properties

A stochastic matrix describes a Markov chain $boldsymbol{X}_{t}$ over a finite state space S. In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, the definition of the probability space is the foundation of probability theory. ...

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., Probability is the likelihood that something is the case or will happen. ...

$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. In linear algebra, a row vector is a 1 Ã— n matrix, that is, a matrix consisting of a single row: The transpose of a row vector is a column vector. ...

The stationary probability vector $boldsymbol{pi}$ is defined as the vector that does not change under application of the transition matrix; that is, it is defined as the eigenvector of the probability matrix, associated with eigenvalue 1: In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...

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

The Perron-Frobenius theorem ensures that this vector exists, and that the largest eigenvalue associated with a stochastic matrix is always 1. In mathematics, the Perron-Frobenius theorem is a theorem in matrix theory about the eigenvalues and eigenvectors of a real positive n×n matrix: Let A = (aij) be a real n×n matrix with positive entries . ...

The stationary probability vector may be computed by taking the limit

$lim_{krightarrowinfty}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. 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. In mathematics, a measure-preserving transformation T on a probability space is said to be ergodic if the only measurable sets invariant under T have measure 0 or 1. ... In quantum mechanics, a stationary state is an eigenstate of a Hamiltonian, or in other words, a state of definite energy. ...

Example: the cat and mouse

All or part of this article may be confusing or unclear.
Please help clarify the article. Suggestions may be on the talk page. (January 2008)

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. Image File history File links Question_mark. ... In probability theory, a random variable is a quantity whose values are random and to which a probability distribution is assigned. ...

The Markov chain that represents this game contains the following five states: In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ...

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}.$

The initial state of the system at time zero is state 2, which we represent by the probability vector v: In mathematics and statistics, a probability vector or stochastic vector is a vector with non-negative entries that add up to one. ...

$mathbf{v} = begin{bmatrix} 0 & 1 & 0 & 0 & 0 end{bmatrix}.$

The probability distribution of the states at time k is then given by

$mathbf{p}_k = mathbf{v}P^k , .$

As the game has an absorbing state 5 the distribution of K, the time to absorption, is discrete phase-type distributed. Therefore by letting The discrete phase-type distribution is a probability distribution that results from a system of one or more inter-related geometric distributions occurring in sequence, or phases. ...

$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}$ .

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

Categories: Matrices | Stochastic processes

Hidden categories: Cleanup from January 2008 | Wikipedia articles needing clarification

Results from FactBites:

PlanetMath: permutation matrix (125 words)
	Since they have a single 1 in each row and each column, they are doubly stochastic.
	They are the extreme points of the convex set of doubly stochastic matrices.
	This is version 13 of permutation matrix, born on 2002-01-04, modified 2007-08-23.

Stochastic matrix - Wikipedia, the free encyclopedia (217 words)
	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.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Definition and properties var ACE_AR = {Site: '756743', Size: '300250'};

Example: the cat and mouse

See also

References

Definition and properties