Editing Stochastic matrix

{{Short description|Matrix used to describe the transitions of a Markov chain}}
{{Use dmy dates|date=August 2021}}
{{For|a matrix whose elements are stochastic|Random matrix}}
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]].<ref>{{Cite book | doi = 10.1007/0-387-21525-5_1 | first1 = S. R. | last1 = Asmussen| chapter = Markov Chains | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 3–8 | year = 2003 | isbn = 978-0-387-00211-8 }}</ref><ref name=":1">{{Cite book |last=Lawler |first=Gregory F. |author-link=Greg Lawler |title=Introduction to Stochastic Processes |publisher=CRC Press |year=2006 |isbn=1-58488-651-X |edition=2nd |language=en}}</ref>{{Rp|page=10}} 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 (so it is also called a '''row stochastic matrix''').
*A '''left stochastic matrix''' is a square matrix of nonnegative real numbers, with each column summing to 1 (so it is also called a '''column stochastic matrix''').
*A ''[[doubly stochastic matrix]]'' is a square matrix of nonnegative real numbers with each row and column summing to 1.
*A '''substochastic matrix''' is a real square matrix whose row sums are all <math>\le1.</math>
In the same vein, one may define a [[probability vector]] as a [[Euclidean vector|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 vector]]s of probabilities by multiplication from the right (hence their name) and the matrix entry in the {{mvar|i}}-th row and {{mvar|j}}-th column is the probability of transition from state {{mvar|i}} to state {{mvar|j}}.  Left stochastic matrices act upon [[column vector]]s of probabilities by multiplication from the left (hence their name) and the matrix entry in the {{mvar|i}}-th row and {{mvar|j}}-th column is the probability of transition from state {{mvar|j}} to state {{mvar|i}}. 

This article uses the right/row stochastic matrix convention. 

== History ==
[[File:Andrej Markov.jpg|thumb|[[Andrey Markov]] in 1886]]
The stochastic matrix was developed alongside the Markov chain by [[Andrey Markov]], a [[List of Russian mathematicians|Russian mathematician]] and professor at [[Saint Petersburg State University|St. Petersburg University]] who first published on the topic in 1906.<ref name=":0">{{cite journal | last1 = Hayes | first1 = Brian | year = 2013 | title = First links in the Markov chain | journal = American Scientist | volume = 101 | issue = 2| pages = 92–96 | doi = 10.1511/2013.101.92 }}</ref> His initial intended uses were for linguistic analysis and other mathematical subjects like [[Shuffling|card shuffling]], but both Markov chains and matrices rapidly found use in other fields.<ref name=":0" /><ref>''Charles Miller Grinstead; James Laurie Snell (1997). Introduction to Probability. American Mathematical Soc. pp. 464–466. {{isbn|978-0-8218-0749-1}}.''</ref>

Stochastic matrices were further developed by scholars such as [[Andrey Kolmogorov]], who expanded their possibilities by allowing for continuous-time Markov processes.<ref>{{cite journal | last1 = Kendall | first1 = D. G. | last2 = Batchelor | first2 = G. K. | last3 = Bingham | first3 = N. H. | last4 = Hayman | first4 = W. K. | last5 = Hyland | first5 = J. M. E. | last6 = Lorentz | first6 = G. G. | last7 = Moffatt | first7 = H. K. | last8 = Parry | first8 = W. | last9 = Razborov | first9 = A. A. | last10 = Robinson | first10 = C. A. | last11 = Whittle | first11 = P. | year = 1990 | title = Andrei Nikolaevich Kolmogorov (1903–1987) | journal = Bulletin of the London Mathematical Society | volume = 22 | issue = 1| page = 33 | doi = 10.1112/blms/22.1.31 }}</ref> By the 1950s, articles using stochastic matrices had appeared in the fields of [[econometrics]]<ref>{{Cite journal|last=Solow|first=Robert|date=1 January 1952|title=On the Structure of Linear Models|journal=Econometrica|volume=20|issue=1|pages=29–46|doi=10.2307/1907805|jstor=1907805}}</ref> and [[Network analysis (electrical circuits)|circuit theory]].<ref>{{Cite journal|last=Sittler|first=R.|date=1 December 1956|title=Systems Analysis of Discrete Markov Processes|journal=IRE Transactions on Circuit Theory|volume=3|issue=4|pages=257–266|doi=10.1109/TCT.1956.1086324|issn=0096-2007}}</ref> In the 1960s, stochastic matrices appeared in an even wider variety of scientific works, from [[Behavioural sciences|behavioral science]]<ref>{{Cite journal|last=Evans|first=Selby|date=1 July 1967|title=Vargus 7: Computed patterns from markov processes|journal=Behavioral Science|language=en|volume=12|issue=4|pages=323–328|doi=10.1002/bs.3830120407|issn=1099-1743}}</ref> to geology<ref>{{Cite journal|last=Gingerich|first=P. D.|date=1 January 1969|title=Markov analysis of cyclic alluvial sediments|journal=Journal of Sedimentary Research|language=en-US|volume=39|issue=1|pages=330–332|doi=10.1306/74d71c4e-2b21-11d7-8648000102c1865d|issn=1527-1404|bibcode=1969JSedR..39..330G}}</ref><ref>{{Cite journal|last1=Krumbein|first1=W. C.|last2=Dacey|first2=Michael F.|date=1 March 1969|title=Markov chains and embedded Markov chains in geology|journal=Journal of the International Association for Mathematical Geology|language=en|volume=1|issue=1|pages=79–96|doi=10.1007/BF02047072|bibcode=1969MatG....1...79K |issn=0020-5958}}</ref> to [[Residential area|residential planning]].<ref>{{Cite journal|last=Wolfe|first=Harry B.|date=1 May 1967|title=Models for Conditioning Aging of Residential Structures|journal=Journal of the American Institute of Planners|volume=33|issue=3|pages=192–196|doi=10.1080/01944366708977915|issn=0002-8991}}</ref> In addition, much mathematical work was also done through these decades to improve the range of uses and functionality of the stochastic matrix and [[Markov chain|Markovian processes]] more generally.

From the 1970s to present, stochastic matrices have found use in almost every field that requires formal analysis, from [[Structural engineering|structural science]]<ref>{{Cite journal|title=A Markov matrix for fatigue load simulation and rainflow range evaluation |language=en|doi=10.1016/0167-4730(89)90025-8|volume=6|issue=2–4|journal=Structural Safety|pages=247–258 | last1 = Krenk | first1 = S.|date=November 1989 }}</ref> to [[medical diagnosis]]<ref>{{Cite journal|last1=Beck|first1=J.Robert|last2=Pauker|first2=Stephen G.|date=1 December 1983|title=The Markov Process in Medical Prognosis|journal=Medical Decision Making|language=en|volume=3|issue=4|pages=419–458|doi=10.1177/0272989X8300300403|pmid=6668990|issn=0272-989X}}</ref> to [[Human resource management|personnel management]].<ref>{{Cite journal|last1=Gotz|first1=Glenn A.|last2=McCall|first2=John J.|date=1 March 1983|title=Sequential Analysis of the Stay/Leave Decision: U.S. Air Force Officers|journal=Management Science|volume=29|issue=3|pages=335–351|doi=10.1287/mnsc.29.3.335|issn=0025-1909}}</ref> In addition, stochastic matrices have found wide use in [[land change modeling]], usually under the term Markov matrix.<ref>{{Cite journal|last1=Kamusoko|first1=Courage|last2=Aniya|first2=Masamu|last3=Adi|first3=Bongo|last4=Manjoro|first4=Munyaradzi|date=1 July 2009|title=Rural sustainability under threat in Zimbabwe – Simulation of future land use/cover changes in the Bindura district based on the Markov-cellular automata model|journal=Applied Geography|volume=29|issue=3|pages=435–447|doi=10.1016/j.apgeog.2008.10.002|bibcode=2009AppGe..29..435K }}</ref>

==Definition and properties==
A stochastic matrix describes a [[Markov chain]] {{math|'''''X'''''<sub>''t''</sub>}} over a [[finite set|finite]] [[Probability space|state space]] {{mvar|S}} with [[cardinality]] {{mvar|α}}.

If the [[probability]] of moving from {{mvar|i}} to {{mvar|j}} in one time step is {{math|1=Pr(''j''{{!}}''i'') = ''P''<sub>''i'',''j''</sub>}}, the stochastic matrix {{mvar|P}} is given by using {{math|''P''<sub>''i'',''j''</sub>}} as the {{mvar|i}}-th row and {{mvar|j}}-th column element, e.g.,

<math display="block">P=\left[\begin{matrix}
P_{1,1}&P_{1,2}&\dots&P_{1,j}&\dots&P_{1,\alpha}\\
P_{2,1}&P_{2,2}&\dots&P_{2,j}&\dots&P_{2,\alpha}\\
\vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\
P_{i,1}&P_{i,2}&\dots&P_{i,j}&\dots&P_{i,\alpha}\\
\vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\
P_{\alpha,1}&P_{\alpha,2}&\dots&P_{\alpha,j}&\dots&P_{\alpha,\alpha}\\
\end{matrix}\right].</math>

Since the total of transition probability from a state {{mvar|i}} to all other states must be 1,
<math display="block">\forall i \in \{1, \ldots, \alpha\},\quad \sum_{j=1}^\alpha P_{i,j}=1;\,</math>
thus this matrix is a right stochastic matrix.

The above elementwise sum across each row {{mvar|i}} of {{mvar|P}} may be more concisely written as {{math|1=''P'''''1''' = '''1'''}}, where {{math|'''1'''}} is the {{mvar|α}}-dimensional column vector of all ones. Using this, it can be seen that the product of two right stochastic matrices {{math|''P''′}} and {{math|''P''′′}} is also right stochastic: {{math|1=''P''′ ''P''′′ '''1''' = ''P''′ (''P''′′ '''1''') = ''P''′ '''1''' = '''1'''}}. In general, the {{mvar|k}}-th power {{math|''P<sup>k</sup>''}} of a right stochastic matrix {{mvar|P}} is also right stochastic.  The probability of transitioning from {{mvar|i}} to {{mvar|j}} in two steps is then given by the {{math|(''i'', ''j'')}}-th element of the square of {{mvar|P}}:

<math display="block">\left(P ^{2}\right)_{i,j}.</math>

In general, the probability transition of going from any state to another state in a finite Markov chain given by the matrix {{mvar|P}} in {{mvar|k}} steps is given by {{math|''P<sup>k</sup>''}}.

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]] {{mvar|'''π'''}} 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 {{math|{1, …, ''n''{{)}}}} which is also a [[left eigenvector]] of the probability matrix, associated with [[eigenvalue]] 1:

<math display="block">\boldsymbol{\pi}P=\boldsymbol{\pi}.</math>

[[File:Karpelevich regions.svg|thumb|right|Karpelevič regions for ''n'' = 3 and ''n'' = 4.]]
It can be shown that the [[spectral radius]] of any stochastic matrix is one. By the [[Gershgorin circle theorem]], all of the eigenvalues of a stochastic matrix have absolute values less than or equal to one. More precisely, the eigenvalues of <math>n</math>-by-<math>n</math> stochastic matrices are restricted to lie within a subset of the complex unit disk, known as Karpelevič regions.<ref>{{cite journal |last1=Munger |first1=Devon |last2=Nickerson |first2=Andrew |last3=Paparella |first3=Pietro |title=Demystifying the Karpelevič theorem |journal=Linear Algebra and Its Applications |date=2024 |volume=702 |pages=46–62|doi=10.1016/j.laa.2024.08.006 |arxiv=2309.03849 }}</ref> This result was originally obtained by [[Fridrikh Karpelevich]],<ref>{{cite journal |last1=Karpelevič. |first1=Fridrikh |title=On the characteristic roots of matrices with nonnegative elements. |journal=Izv. Math. |date=1951 |volume=15 |issue=4}}</ref> following a question originally posed by Kolmogorov<ref>{{cite journal |last1=Kolmogorov |first1=Andrei |title=Markov chains with a countable number of possible states |journal=Bull. Mosk. Gos. Univ. Math. Mekh |date=1937 |volume=1 |issue=3 |pages=1–15}}</ref> and partially addressed by [[Nikolay Dmitriyev]] and [[Eugene Dynkin]].<ref>{{cite journal |last1=Dmitriev |first1=Nikolai |last2=Dynkin |first2=Eugene |title=On characteristic roots of stochastic matrices |journal=Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya |date=1946 |volume=10 |issue=2 |pages=167–184}}</ref>

Additionally, every right stochastic matrix has an "obvious" column eigenvector associated to the eigenvalue 1: the vector {{math|'''1'''}} used above, whose coordinates are all equal to 1. As left and right eigenvalues of a square matrix are the same, every stochastic matrix has, at least, a [[left eigenvector]] associated to the [[eigenvalue]] 1 and the largest absolute value of all its eigenvalues is also 1. Finally, the [[Brouwer Fixed Point Theorem]] (applied to the compact convex set of all probability distributions of the finite set {{math|{1, ..., ''n''{{)}}}}) implies that there is some left eigenvector which is also a stationary probability vector.

On the other hand, the [[Perron–Frobenius theorem]] also ensures that every [[Irreducibility (mathematics)|irreducible]] stochastic matrix has such a stationary vector, and that the largest absolute value of an eigenvalue is always 1. However, this theorem cannot be applied directly to such matrices because they need not be irreducible. In general, there may be several such vectors.  However, for a matrix with strictly positive entries (or, more generally, for an irreducible aperiodic stochastic matrix), this vector is unique and can be computed by observing that for any {{mvar|i}} we have the following limit,

<math display="block">\lim_{k\rightarrow\infty}\left(P^k \right)_{i,j}=\boldsymbol{\pi}_j,</math>

where {{math|'' '''π'''<sub>j</sub>''}} is the {{mvar|j}}-th element of the row vector {{mvar|'''π'''}}. Among other things, this says that the long-term probability of being in a state {{mvar|j}} is independent of the initial state {{mvar|i}}. That both of these computations give the same stationary vector is a form of an [[ergodic theorem]], which is generally true in a wide variety of [[dissipative dynamical system]]s: the system evolves, over time, to a [[stationary state]].


Intuitively, a stochastic matrix represents a Markov chain; the application of the stochastic matrix to a probability distribution redistributes the probability mass of the original distribution while preserving its total mass. If this process is applied repeatedly, the distribution converges to a stationary distribution for the Markov chain.<ref name=":1" />{{Rp|pages=14-17}}<ref name="Kardar2007">{{cite book|first=Mehran |last=Kardar |author-link=Mehran Kardar |title=Statistical Physics of Fields |title-link=Statistical Physics of Particles |year=2007 |publisher=[[Cambridge University Press]] |isbn=978-0-521-87341-3 |oclc=920137477}}</ref>{{Rp|page=116}}

Stochastic matrices and their product form a [[category (mathematics)|category]], which is both a subcategory of the [[category of matrices]] and of the one of [[Markov kernel]]s.

== Example: Cat and mouse ==

Suppose there is a timer and a row of five adjacent boxes. At time zero, a cat is in the first box, and a mouse is in the fifth box. The cat and the mouse both jump to a random '''adjacent''' box when the timer advances. For example, if the cat is in the second box and the mouse is in the fourth, the probability that ''the cat will be in the first box '''and''' the mouse in the fifth after the timer advances'' is one fourth. If the cat is in the first box and the mouse is in the fifth, the probability that ''the cat will be in box two and the mouse will be in box four after the timer advances'' is one. The cat eats the mouse if both end up in the same box, at which time the game ends. Let the [[random variable]] ''K'' be the time the mouse stays in the game.

The [[Markov chain]] that represents this game contains the following five states specified by the combination of positions (cat,mouse).  Note that while a naive enumeration of states would list 25 states, many are impossible either because the mouse can never have a lower index than the cat (as that would mean the mouse occupied the cat's box and survived to move past it), or because the sum of the two indices will always have even [[Parity (mathematics)|parity]].  In addition, the 3 possible states that lead to the mouse's death are combined into one:

* State 1: (1,3)
* State 2: (1,5)
* State 3: (2,4)
* State 4: (3,5)
* State 5: game over: (2,2), (3,3) & (4,4).

We use a stochastic matrix, <math>P</math> (below), to represent the [[transition probabilities]] of this system (rows and columns in this matrix are indexed by the possible states listed above, with the pre-transition state as the row and post-transition state as the column).  For instance, starting from state 1 – 1st row – it is impossible for the system to stay in this state, so <math>P_{11}=0</math>; the system also cannot transition to state 2 – because the cat would have stayed in the same box – so <math>P_{12}=0</math>, and by a similar argument for the mouse, <math>P_{14}=0</math>. Transitions to states 3 or 5 are allowed, and thus <math>P_{13},P_{15}\neq0</math> .

<math display="block"> 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}.</math>

===Long-term averages===

No matter what the initial state, the cat will eventually catch the mouse (with probability 1) and a stationary state '''&pi;''' = (0,0,0,0,1) is approached as a limit. To compute the long-term average or expected value of a stochastic variable <math>Y</math>, for each state <math>S_j</math> and time <math>t_k</math> there is a contribution of <math>Y_{j,k}\cdot P(S=S_j,t=t_k)</math>. Survival can be treated as a binary variable with <math>Y=1</math> for a surviving state and <math>Y=0</math> for the terminated state. The states with <math>Y=0</math> do not contribute to the long-term average.

===Phase-type representation===
[[Image:Mousesurvival.jpg|thumb|right|upright=1.6|The survival function of the mouse. The mouse will survive at least the first time step.]]

As State 5 is an absorbing state, the distribution of time to absorption is [[discrete phase-type distribution|discrete phase-type distributed]]. Suppose the system starts in state 2, represented by the vector <math>[0,1,0,0,0]</math>. The states where the mouse has perished don't contribute to the survival average so state five can be ignored. The initial state and transition matrix can be reduced to,

<math display="block">\boldsymbol{\tau}=[0,1,0,0], \qquad T=\begin{bmatrix}
    0          & 0           & \frac{1}{2}  &   0\\
    0          & 0           & 1            &   0\\
  \frac{1}{4}  & \frac{1}{4} &           0  & \frac{1}{4}\\
    0          & 0           & \frac{1}{2}  &   0
\end{bmatrix},</math> 

and 

<math display="block">(I-T)^{-1}\boldsymbol{1} =\begin{bmatrix}2.75 \\ 4.5 \\ 3.5 \\ 2.75\end{bmatrix},</math>

where <math>I</math> is the [[identity matrix]], and <math>\mathbf{1}</math> represents a column matrix of all ones that acts as a sum over states.

Since each state is occupied for one step of time the expected time of the mouse's survival is just the [[Matrix polynomial#Matrix geometrical series|sum]] of the probability of occupation over all surviving states and steps in time,

<math display="block">E[K]=\boldsymbol{\tau} \left (I+T+T^2+\cdots \right )\boldsymbol{1}=\boldsymbol{\tau}(I-T)^{-1}\boldsymbol{1}=4.5.</math>

Higher order moments are given by

<math display="block">E[K(K-1)\dots(K-n+1)]=n!\boldsymbol{\tau}(I-{T})^{-n}{T}^{n-1}\mathbf{1}\,.</math>

== See also ==
* [[Density matrix]]
* [[Markov kernel]], the equivalent of a stochastic matrix over a continuous state space
* [[Matrix difference equation]]
* [[Models of DNA evolution]]
* [[Muirhead's inequality]]
* [[Probabilistic automaton]]
* [[Transition rate matrix]], used to generalize the stochastic matrix to continuous time

==References==
{{Reflist}}
{{Matrix classes}}
{{Authority control}}
[[zh-yue:轉移矩陣]]
[[Category:Matrices (mathematics)]]
[[Category:Markov models]]