In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability.[1] [2] It is also called a probability matrix, transition matrix, substitution matrix, or Markov matrix. The stochastic matrix was first developed by Andrey Markov at the beginning of the 20th century, and has found use throughout a wide variety of scientific fields, including probability theory, statistics, mathematical finance and linear algebra, as well as computer science and population genetics. There are several different definitions and types of stochastic matrices:
A right stochastic matrix is a square matrix of nonnegative real numbers, with each row summing to 1.
A left stochastic matrix is a square matrix of nonnegative real numbers, with each column summing to 1.
A doubly stochastic matrix is a square matrix of nonnegative real numbers with each row and column summing to 1.
In the same vein, one may define a probability vector as a vector whose elements are nonnegative real numbers which sum to 1. Thus, each row of a right stochastic matrix (or column of a left stochastic matrix) is a probability vector. Right stochastic matrices act upon row vectors of probabilities by multiplication from the right, and left stochastic matrices act upon column vectors of probabilities by multiplication from the left. This article follows the former convention. In addition, a substochastic matrix is a real square matrix whose row sums are all
\le1.
The stochastic matrix was developed alongside the Markov chain by Andrey Markov, a Russian mathematician and professor at St. Petersburg University who first published on the topic in 1906.[3] His initial intended uses were for linguistic analysis and other mathematical subjects like card shuffling, but both Markov chains and matrices rapidly found use in other fields.[4]
Stochastic matrices were further developed by scholars such as Andrey Kolmogorov, who expanded their possibilities by allowing for continuous-time Markov processes.[5] By the 1950s, articles using stochastic matrices had appeared in the fields of econometrics[6] and circuit theory.[7] In the 1960s, stochastic matrices appeared in an even wider variety of scientific works, from behavioral science[8] to geology[9] [10] to residential planning.[11] In addition, much mathematical work was also done through these decades to improve the range of uses and functionality of the stochastic matrix and Markovian processes more generally.
From the 1970s to present, stochastic matrices have found use in almost every field that requires formal analysis, from structural science[12] to medical diagnosis[13] to personnel management.[14] In addition, stochastic matrices have found wide use in land change modeling, usually under the term Markov matrix.[15]
A stochastic matrix describes a Markov chain over a finite state space with cardinality .
If the probability of moving from to in one time step is, the stochastic matrix is given by using as the -th row and -th column element, e.g.,
P=\left[\begin{matrix} P1,1&P1,2&...&P1,j&...&P1,\alpha\\ P2,1&P2,2&...&P2,j&...&P2,\alpha\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\ Pi,1&Pi,2&...&Pi,j&...&Pi,\alpha\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\ P\alpha,1&P\alpha,2&...&P\alpha,j&...&P\alpha,\alpha\\ \end{matrix}\right].
Since the total of transition probability from a state to all other states must be 1,
| \alpha | |
| \sum | |
| j=1 |
Pi,j=1;
thus this matrix is a right stochastic matrix.
The above elementwise sum across each row of may be more concisely written as, where is the -dimensional column vector of all ones. Using this, it can be seen that the product of two right stochastic matrices and is also right stochastic: . In general, the -th power of a right stochastic matrix is also right stochastic. The probability of transitioning from to in two steps is then given by the -th element of the square of :
\left(P2\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 in steps is given by .
An initial probability distribution of states, specifying where the system might be initially and with what probabilities, is given as a row vector.
A stationary probability vector is defined as a distribution, written as a row vector, that does not change under application of the transition matrix; that is, it is defined as a probability distribution on the set