Stochastic matrix
From Wikipedia, the free encyclopedia
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 stochastic vector. Stochastic vectors are also sometimes called probability vectors.
Contents[hide] |
[edit] Definition and properties
A stochastic matrix describes a Markov chain over a finite state space S.
If the probability of moving from i to j in one time step is Pr(j | i) = Pi,j, the stochastic matrix P is given by using Pi,j as the ith row and jth column element, e.g.,
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
The probability of transitioning from i to j in two steps is then given by the (i,j)th element of the square of P:
- .
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 Pk.
An initial distribution is given as a row vector.
The stationary probability vector 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:
- .
The Perron-Frobenius theorem ensures that this vector exists, and that the largest eigenvalue associated with a stochastic matrix is always 1.
The stationary probability vector may be computed by taking the limit
- ,
where is the jth element of the row vector . 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.
[edit] 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,
[edit] Long term averages
As state five is an absorbing state the long term average vector . Regardless of the initial conditions the cat will eventually catch the mouse.
[edit] Phase-type representation
As the game has an absorbing state 5 the distribution of time to absorption is discrete phase-type distributed. Therefore by letting
and by removing state five to make a sub-stochastic matrix,
then the expected time of the mouse's survival is,
- .
Higher order moments are given by,
- .
[edit] See also
- Muirhead's inequality
- Perron-Frobenius theorem
- Doubly stochastic matrix
- Discrete phase-type distribution
- Probabilistic automaton
[edit] 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