View source for Continuous-time Markov chain

{{Short description|Probability concept}}
{{About|the mathematical properties of continuous-time Markov chains|the general field of study|Markov chain}}
{{No footnotes|date=August 2020}}
A '''continuous-time Markov chain''' ('''CTMC''') is a continuous [[stochastic process]] in which, for each state, the process will change state according to an [[exponential random variable]] and then move to a different state as specified by the probabilities of a [[stochastic matrix]]. An equivalent formulation describes the process as changing state according to the least value of a set of exponential random variables, one for each possible state it can move to, with the parameters determined by the current state.

An example of a CTMC with three states <math>\{0,1, 2\}</math> is as follows: the process makes a transition after the amount of time specified by the '''holding time'''—an exponential random variable <math>E_i</math>, where ''i'' is its current state. Each random variable is independent and such that <math>E_0\sim \text{Exp}(6)</math>, <math>E_1\sim \text{Exp}(12)</math> and <math>E_2\sim \text{Exp}(18)</math>. When a transition is to be made, the process moves according to the '''jump chain''', a [[discrete-time Markov chain]] with stochastic matrix:
:<math>\begin{bmatrix}
0 & \frac{1}{2} & \frac{1}{2} \\
\frac{1}{3} & 0 & \frac{2}{3} \\
\frac{5}{6} & \frac{1}{6} & 0
\end{bmatrix}.</math>

Equivalently, by the property of [[competing exponentials]], this CTMC changes state from state ''i'' according to the minimum of two random variables, which are independent and such that <math>E_{i,j}\sim \text{Exp}(q_{i,j})</math> for <math>i\neq j</math> where the parameters are given by the '''Q-matrix''' <math>Q=(q_{i,j})</math>
:<math>\begin{bmatrix}
-6 & 3 & 3 \\
4 & -12 & 8 \\
15 & 3 & -18
\end{bmatrix}.</math>
Each non-diagonal entry <math>q_{i,j}</math> can be computed as the probability that the jump chain moves from state ''i'' to state ''j'', divided by the expected holding time of state ''i''. The diagonal entries are chosen so that each row sums to 0.

A CTMC satisfies the [[Markov property]], that its behavior depends only on its current state and not on its past behavior, due to the memorylessness of the exponential distribution and of discrete-time Markov chains.

==Definition==
Let <math>(\Omega,{\cal A},\Pr)</math> be a probability space, let <math>S</math> be a countable nonempty set, and let <math>T=\mathbb R_{\ge0}</math> (<math>T</math> for "time"). Equip <math>S</math> with the [[discrete metric]], so that we can make sense of [[Right continuous|right continuity]] of functions <math>\mathbb R_{\ge0}\to S</math>. A continuous-time Markov chain is defined by:<ref name=ross>{{cite book|author=Ross, S.M.|year=2010|title=Introduction to Probability Models|publisher=Elsevier|edition=10|isbn=978-0-12-375686-2}}</ref>
* A [[probability vector]] <math>\lambda</math> on <math>S</math> (which below we will interpret as the ''initial distribution'' of the Markov chain), and
* A [[transition-rate matrix|rate matrix]] <math>Q</math> on <math>S</math>, that is, a function <math>Q:S^2\to\mathbb R</math> such that
# for all distinct <math>i,j\in S, 0\le q_{i,j}</math>,
# for all <math>i\in S,</math> <math>\sum_{j\in I:j\ne i}q_{i,j}=-q_{i,i}.</math> (Even if <math>I</math> is infinite, this sum is ''a priori'' well defined (possibly equalling <math>+\infty</math>) because each term appearing in the sum is nonnegative. ''A posteriori'', we know the sum must also be finite (not equal to <math>+\infty</math>), since we're assuming it's equal to <math>-q_{i,i}</math> and we've assumed <math>Q</math> is real valued. Some authors instead use a definition that's word-for-word the same except for a modified stipulation <math>Q:S^2\to\mathbb R\cup\{-\infty\}</math>, and say <math>Q</math> is ''stable'' or ''totally stable'' to mean <math>\operatorname{range}Q\subseteq\mathbb R</math>, i.e., every entry is real valued.){{sfn|Anderson|1991|loc=See definition on page 64}}{{sfn|Chen|Mao|2021|loc=Definition 2.2}}{{sfn|Chen|2004|loc=Definition 0.1(4)}}
Note that the row sums of <math>Q</math> are 0: <math>\forall i\in S~\sum_{j\in I}q_{i,j}=0,</math> or more succinctly, <math>Q\cdot1=0</math>. This situation contrasts with the situation for [[discrete-time Markov chain]]s, where all row sums of the transition matrix equal unity.

Now, let <math>X:T\to S^\Omega</math> such that <math>\forall t\in T~X(t)</math> is <math>({\cal A},{\cal P}(S))</math>-measurable. There are three equivalent ways to define <math>X</math> being ''Markov with initial distribution <math>\lambda</math> and rate matrix <math>Q</math>'': via transition probabilities or via the jump chain and holding times.{{sfn|Norris|1997|loc=Theorem 2.8.4 and Theorem 2.8.2(b)}}

As a prelude to a transition-probability definition, we first motivate the definition of a ''regular'' [[Transition-rate matrix|rate matrix]]. We will use the transition-rate matrix <math>Q</math> to specify the dynamics of the Markov chain by means of generating a collection of ''transition matrices'' <math>P(t)</math> on <math>S</math> (<math>t\in\mathbb R_{\ge0}</math>), via the following theorem.
{{math theorem
| name = '''Theorem: Existence of solution to [[Kolmogorov backward equations (continuous-time Markov chains)|Kolmogorov backward equations]].'''{{sfn|Anderson|1991|loc=Theorem 2.2.2(1), page 70}}
| math_statement = There exists <math>P\in([0,1]^{S\times S})^T</math> such that for all <math>i,j\in S</math> the entry <math>(P(t)_{i,j})_{t\in T}</math> is differentiable and <math>P</math> satisfies the [[Kolmogorov backward equations (continuous-time Markov chains)|Kolmogorov backward equations]]:
{{NumBlk|:|<math display=block>P(0)=([i=j])_{i,j\in S},~\forall t\in T~\forall i,j\in S~~(P(t)_{i,j})'=\sum_{k\in S}q_{i,k}P(t)_{k,j}.</math>|{{EquationRef|0}}}}
}}
We say <math>Q</math> is ''regular'' to mean that we do have uniqueness for the above system, i.e., that there exists exactly one solution.{{sfn|Anderson|1991|loc=Definition on page 81}}{{sfn|Chen|2004|loc=page 2}} We say <math>Q</math> is ''irregular'' to mean <math>Q</math> is not regular. If <math>S</math> is finite, then there is exactly one solution, namely <math>P=(e^{tQ})_{t\in T},</math> and hence <math>Q</math> is regular. Otherwise, <math>S</math> is infinite, and there exist irregular transition-rate matrices on <math>S</math>.{{efn|For instance, consider the example <math>S=\mathbb Z_{\ge0}</math> and <math>Q</math> being the (unique) transition-rate matrix on <math>S</math> such that <math>\forall i\in\mathbb Z_{\ge0}~~Q_{i,i+1}=i^2,~Q_{i,i}=-i^2</math>. (Then the remaining entries of <math>Q</math> will all be zero. Cf. [[birth process]].) Then <math>Q</math> is irregular. Then, for general infinite <math>S</math>, indexing <math>S</math> by the nonnegative integers <math>\mathbb Z_{\ge0}</math> yields that a suitably modified version of the above matrix <math>Q</math> will be irregular.{{sfn|Anderson|1991|loc=page 20}}}} If <math>Q</math> is regular, then for the unique solution <math>P</math>, for each <math>t\in T</math>, <math>P(t)</math> will be a [[stochastic matrix]].{{sfn|Anderson|1991|loc=Theorem 2.2.2(1), page 70}} We will assume <math>Q</math> is regular from the beginning of the following subsection up through the end of this section, even though it is conventional{{sfn|Suhov|Kelbert|2008|loc=Definition 2.6.3}}{{sfn|Chen|Mao|2021|loc=Definition 2.1}}{{sfn|Chen|2004|loc=Definition 0.1}} to not include this assumption. (Note for the expert: thus we are not defining continuous-time Markov chains in general but only ''non-explosive'' continuous-time Markov chains.)

=== Transition-probability definition ===
Let <math>P</math> be the (unique) solution of the system ({{EquationNote|0}}). (Uniqueness guaranteed by our assumption that <math>Q</math> is regular.) We say <math>X</math> is ''Markov with initial distribution <math>\lambda</math> and rate matrix <math>Q</math>'' to mean: for any nonnegative integer <math>n\ge0</math>, for all <math>t_0,\dots,t_{n+1}\in T</math> such that <math>t_0<\dots<t_{n+1},</math> for all <math>i_0,\dots,i_{n+1}\in I,</math>
{{NumBlk|:|<math>\Pr(X_0=i_0,\dots,X_{t_{n+1}}=i_{n+1})=\lambda_{i_0}\prod_{k\in\mathbb Z:0\le k\le n}P(t_{k+1}-t_k)_{i_k,i_{k+1}}</math>.{{sfn|Suhov|Kelbert|2008|loc=Definition 2.6.3}}|{{EquationRef|1}}}}
Using induction and the fact that <math>\forall A,B\in{\cal A}~~\Pr(B)\ne0\rightarrow\Pr(A\cap B)=\Pr(A\mid B)\Pr(B),</math> we can show the equivalence of the above statement containing ({{EquationNote|1}}) and the following statement: for all <math>i\in I,~\Pr(X_0=i)=\lambda_i</math> and for any nonnegative integer <math>n\ge0</math>, for all <math>t_0,\dots,t_{n+1}\in T</math> such that <math>t_0<\dots<t_{n+1},</math> for all <math>i_0,\dots,i_{n+1}\in I</math> such that <math>0<\Pr(X_0=i_0,\dots,X_{t_n}=i_n)</math> (it follows that <math>0<\Pr(X_{t_n}=i_n)</math>),
{{NumBlk|:|<math>\Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_n}=i_n,\dots,X_{t_0}=i_0)=P(t_{n+1}-t_n)_{i_n,i_{n+1}}.</math>|{{EquationRef|2}}}}

It follows from continuity of the functions <math>(P(t)_{i,j})_{t\in T}</math> (<math>i,j\in S</math>) that the trajectory <math>(X_t(\omega))_{t\in T}</math> is almost surely [[right continuous]] (with respect to the [[discrete metric]] on <math>S</math>): there exists a <math>\Pr</math>-null set <math>N</math> such that <math>\{\omega\in\Omega:(X_t(\omega))_{t\in T}\text{ is right continuous}\}\subseteq N</math>.{{sfn|Chen|Mao|2021|loc=page 56, just below Definition 2.2}}

=== Jump-chain/holding-time definition ===
==== Sequences associated to a right-continuous function ====
Let <math>f:T\to S</math> be right continuous (when we equip <math>S</math> with the [[discrete metric]]). Define

:<math>h=h(f)=(\inf\{u\in(0,+\infty):f(t+u)\ne f(t)\})_{t\in T})\cup\{+\infty,0\},</math>
let 
:<math>H=H(f)=(h^{\circ n}0)_{n\in\mathbb Z_{\ge0}}</math> 
be the ''holding-time sequence'' associated to <math>f</math>, choose <math>s\in S,</math> and let
:<math>y=y(f)=\left(\begin{cases}f(\sum_{k\in n}H_k)&\text{ if }\sum_{k\in n}H_k<+\infty,\\s&\text{ else}\end{cases}\right)_{n\in\omega}</math>
be "the ''state sequence''" associated to <math>f</math>.

==== Definition of the jump matrix Π ====
The '''jump matrix''' <math>\Pi</math>, alternatively written <math>\Pi(Q)</math> if we wish to emphasize the dependence on <math>Q</math>, is the matrix
<math display=block>\Pi=([i=j])_{i\in Z,j\in S}\cup\bigcup_{i\in S\setminus Z}(\{((i,j),(-Q_{i,i})^{-1}Q_{i,j}):j\in S\setminus\{i\}\}\cup\{((i,i),0)\}),</math>
where <math>Z=Z(Q)=\{k\in S:q_{k,k}=0\}</math> is the ''zero set'' of the function <math>(q_{k,k})_{k\in S}.</math>{{sfn|Norris|1997|loc=page 87}}

==== Jump-chain/holding-time property ====
We say <math>X</math> is ''Markov with initial distribution <math>\lambda</math> and rate matrix <math>Q</math>'' to mean: the trajectories of <math>X</math> are almost surely right continuous, let <math>f</math> be a modification of <math>X</math> to have (everywhere) right-continuous trajectories, <math>\sum_{n\in\mathbb Z_{\ge0}}H(f(\omega))_n=+\infty</math> almost surely (note to experts: this condition says <math>X</math> is non-explosive), the state sequence <math>y(f(\omega))</math> is a discrete-time Markov chain with initial distribution <math>\lambda</math> (jump-chain property) and transition matrix <math>\Pi(Q),</math> and <math>\forall n\in\mathbb Z_{\ge0}~\forall B\in{\cal B}(\mathbb R_{\ge0})~\Pr(H_n(f)\in B)=\operatorname{Exp}(-q_{Y_n,Y_n})(B)</math> (holding-time property).

=== Infinitesimal definition ===
[[File:Intensities_vs_transition_probabilities.svg|thumb|The continuous time Markov chain is characterized by the transition rates, the derivatives with respect to time of the transition probabilities between states i and j.]]
We say <math>X</math> is ''Markov with initial distribution <math>\lambda</math> and rate matrix <math>Q</math>'' to mean: for all <math>i\in S,</math> <math>\Pr(X(0)=i)=\lambda_i</math> and for all <math>i,j</math>, for all <math>t</math> and for small strictly positive values of <math>h</math>, the following holds for all <math>t\in T</math> such that <math>0<\Pr(X(t)=i)</math>:
:<math>\Pr(X(t+h) = j \mid X(t) = i) = [i=j] + q_{i,j}h + o(h)</math>,
where the term <math>[i=j]</math> is <math>1</math> if <math>i=j</math> and otherwise <math>0</math>, and the [[little-o notation|little-o term]] <math>o(h)</math> depends in a certain way on <math>i,j,h</math>.{{sfn|Suhov|Kelbert|2008|loc=Theorem 2.6.6}}{{sfn|Norris|1997|loc=Theorem 2.8.2(c)}}

The above equation shows that <math>q_{i,j}</math> can be seen as measuring how quickly the transition from <math>i</math> to <math>j</math> happens for <math>i\neq j</math>, and how quickly the transition away from <math>i</math> happens for <math>i= j</math>.

==Properties==

===Communicating classes===
Communicating classes, transience, recurrence and positive and null recurrence are defined identically as for [[discrete-time Markov chain]]s.

===Transient behaviour===
Write P(''t'') for the matrix with entries ''p''<sub>''ij''</sub> = P(''X''<sub>''t''</sub>&nbsp;=&nbsp;''j''&nbsp;|&nbsp;''X''<sub>0</sub>&nbsp;=&nbsp;''i''). Then the matrix P(''t'') satisfies the forward equation, a [[first-order differential equation]]
:<math>P'(t) = P(t) Q</math>,
where the prime denotes differentiation with respect to ''t''. The solution to this equation is given by a [[matrix exponential]]
:<math>P(t) = e^{tQ}</math>.

In a simple case such as a CTMC on the state space {1,2}. The general ''Q'' matrix for such a process is the following 2&nbsp;×&nbsp;2 matrix with ''α'',''β''&nbsp;>&nbsp;0
:<math>Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}.</math>

The above relation for forward matrix can be solved explicitly in this case to give
:<math>P(t) = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} + \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} - \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} \\
\frac{\beta}{\alpha+\beta} - \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} + \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t}
\end{pmatrix}</math>.

Computing direct solutions is complicated in larger matrices. The fact that ''Q'' is the generator for a [[semigroup]] of matrices
:<math>P(t+s) = e^{(t+s)Q} = e^{tQ} e^{sQ} = P(t) P(s)</math>
is used.

===Stationary distribution===
The stationary distribution for an irreducible recurrent CTMC is the probability distribution to which the process converges for large values of ''t''. Observe that for the two-state process considered earlier with P(''t'') given by
:<math>P(t) = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} + \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} - \frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t} \\
\frac{\beta}{\alpha+\beta} - \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t} &
\frac{\alpha}{\alpha+\beta} + \frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t}
\end{pmatrix}</math>,
as ''t''&nbsp;→&nbsp;∞ the distribution tends to
:<math>P_\pi = \begin{pmatrix}
\frac{\beta}{\alpha+\beta} &
\frac{\alpha}{\alpha+\beta} \\
\frac{\beta}{\alpha+\beta} &
\frac{\alpha}{\alpha+\beta}
\end{pmatrix}</math>.
Observe that each row has the same distribution as this does not depend on starting state. The row vector ''{{pi}}'' may be found by solving
:<math>\pi Q = 0</math>
with the constraint
:<math>\sum_{i \in S} \pi_i = 1</math>.

====Example 1====
[[File:Financial_Markov_process.svg|right|thumb|250x250px|Directed graph representation of a continuous-time Markov chain describing the state of financial markets (note: numbers are made-up).]]
The image to the right describes a continuous-time Markov chain with state-space {Bull market, Bear market, Stagnant market} and [[transition-rate matrix]]
:: <math>Q=\begin{pmatrix}
-0.025 & 0.02 & 0.005 \\
0.3 & -0.5 & 0.2 \\
0.02 & 0.4 & -0.42
\end{pmatrix}.</math>
The stationary distribution of this chain can be found by solving <math>\pi Q=0</math>, subject to the constraint that elements must sum to 1 to obtain
:<math>\pi = \begin{pmatrix}0.885 & 0.071 & 0.044 \end{pmatrix}.</math> <!-- That is, <math>\pi = \begin{pmatrix}100/113 & 8/113 & 5/113 \end{pmatrix}.</math> -->

====Example 2====
[[File:Transition graph pac-man.png|thumb|Transition graph with transition probabilities, exemplary for the states 1, 5, 6 and 8. There is a bidirectional secret passage between states 2 and 8.]]
The image to the right describes a discrete-time Markov chain modeling [[Pac-Man]] with state-space {1,2,3,4,5,6,7,8,9}. The player controls Pac-Man through a maze, eating pac-dots. Meanwhile, he is being hunted by ghosts. For convenience, the maze shall be a small 3x3-grid and the ghosts move randomly in horizontal and vertical directions. A secret passageway between states 2 and 8 can be used in both directions. Entries with probability zero are removed in the following transition-rate matrix:

<math>Q=\begin{pmatrix} 
-1 & \frac{1}{2} & & \frac{1}{2}\\
\frac{1}{4} & -1 & \frac{1}{4} & & \frac{1}{4}&&&\frac{1}{4}\\
& \frac{1}{2} & -1 & & & \frac{1}{2}\\
\frac{1}{3} & & & -1 & \frac{1}{3} & & \frac{1}{3}\\
& \frac{1}{4} & & \frac{1}{4} & -1 & \frac{1}{4} & & \frac{1}{4}\\
& & \frac{1}{3} & & \frac{1}{3} & -1& & & \frac{1}{3}\\
& & & \frac{1}{2} & & & -1 & \frac{1}{2}\\
& \frac{1}{4} & && \frac{1}{4} & & \frac{1}{4} & -1 & \frac{1}{4}\\
& & & & & \frac{1}{2} & & \frac{1}{2} & -1\end{pmatrix}</math>

This Markov chain is irreducible, because the ghosts can fly from every state to every state in a finite amount of time. Due to the secret passageway, the Markov chain is also aperiodic, because the ghosts can move from any state to any state both in an even and in an uneven number of state transitions. Therefore, a unique stationary distribution exists and can be found by solving <math>\pi Q=0</math>, subject to the constraint that elements must sum to 1. The solution of this linear equation subject to the constraint is <math>\pi=(7.7,15.4,7.7,11.5,15.4,11.5,7.7,15.4,7.7)\%.</math>
The central state and the border states 2 and 8 of the adjacent secret passageway are visited most and the corner states are visited least.

===Time reversal===
For a CTMC ''X''<sub>''t''</sub>, the time-reversed process is defined to be <math>\hat X_t = X_{T-t}</math>. By [[Kelly's lemma]] this process has the same stationary distribution as the forward process.

A chain is said to be reversible if the reversed process is the same as the forward process. [[Kolmogorov's criterion]] states that the necessary and sufficient condition for a process to be reversible is that the product of transition rates around a closed loop must be the same in both directions.

=== Embedded Markov chain <!-- Embedded Markov chain redirects here --> ===

One method of finding the [[stationary probability distribution]], {{pi}}, of an [[ergodic]] continuous-time Markov chain, ''Q'', is by first finding its '''embedded Markov chain (EMC)'''. Strictly speaking, the EMC is a regular discrete-time Markov chain. Each element of the one-step transition probability matrix of the EMC, ''S'', is denoted by ''s''<sub>''ij''</sub>, and represents the [[conditional probability]] of transitioning from state ''i'' into state ''j''. These conditional probabilities may be found by

:<math>
s_{ij} = \begin{cases}
\frac{q_{ij}}{\sum_{k \neq i} q_{ik}} & \text{if } i \neq j,\\
0 & \text{otherwise}.
\end{cases}
</math>

From this, ''S'' may be written as
:<math>S = I - \left( \operatorname{diag}(Q) \right)^{-1} Q</math>
where ''I'' is the [[identity matrix]] and diag(''Q'') is the [[diagonal matrix]] formed by selecting the [[main diagonal]] from the matrix ''Q'' and setting all other elements to zero.

To find the stationary probability distribution vector, we must next find <math>\varphi</math> such that
:<math>\varphi S = \varphi, </math>

with <math>\varphi</math> being a row vector, such that all elements in <math>\varphi</math> are greater than 0 and [[norm (mathematics)|<math>\|\varphi\|_1</math>]] = 1. From this, {{pi}} may be found as
:<math>\pi = {-\varphi (\operatorname{diag}(Q))^{-1} \over \left\| \varphi (\operatorname{diag}(Q))^{-1} \right\|_1}.</math>

(''S'' may be periodic, even if ''Q'' is not. Once {{pi}} is found, it must be normalized to a [[unit vector]].)

Another discrete-time process that may be derived from a continuous-time Markov chain is a δ-skeleton&mdash;the (discrete-time) Markov chain formed by observing ''X''(''t'') at intervals of δ units of time. The random variables ''X''(0),&nbsp;''X''(δ),&nbsp;''X''(2δ),&nbsp;... give the sequence of states visited by the δ-skeleton.

==See also==

* [[Kolmogorov equations (Markov jump process)]]

==Notes==
{{reflist}}

==References==
{{refbegin}}
* {{cite book |last1=Anderson |first1=William J. |title=Continuous-time Markov chains: an applications-oriented approach |date=1991 |publisher=Springer}}
* Leo Breiman (1992) [1968] ''Probability''. Original edition published by Addison-Wesley; reprinted by [[Society for Industrial and Applied Mathematics]] {{ISBN|0-89871-296-3}}. (See Chapter 7)
* {{cite book |last1=Chen |first1=Mu-Fa |title=From Markov chains to non-equilibrium particle systems |date=2004 |publisher=World Scientific |edition=Second}}
* {{cite book |last1=Chen |first1=Mu-Fa |last2=Mao |first2=Yong-Hua |title=Introduction to stochastic processes |date=2021| publisher=World Scientific}}
* [[J. L. Doob]] (1953) ''Stochastic Processes''. New York: John Wiley and Sons {{ISBN|0-471-52369-0}}.
* A. A. Markov (1971). "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. ''Dynamic Probabilistic Systems, volume 1: Markov Chains''. John Wiley and Sons.
* {{cite journal |last = Markov |first = A. A. |year = 2006 |title = An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains |translator-first = David |translator-last = Link |journal = Science in Context |volume = 19 |issue = 4 |pages = 591–600 |doi = 10.1017/s0269889706001074 |s2cid = 144854176 }}
* S. P. Meyn and R. L. Tweedie (1993) ''Markov Chains and Stochastic Stability''. London: Springer-Verlag {{ISBN|0-387-19832-6}}. online: [https://web.archive.org/web/20100619010320/https://netfiles.uiuc.edu/meyn/www/spm_files/book.html MCSS] . Second edition to appear, Cambridge University Press, 2009.
* {{cite book |title=Finite Mathematical Structures |url=https://archive.org/details/finitemathematic0000keme_h5g0 |url-access=registration |last=Kemeny |first=John G. |publisher=Prentice-Hall, Inc. |year=1959 |edition=1st |location=Englewood Cliffs, NJ |id = Library of Congress Card Catalog Number 59-12841 |author2=Hazleton Mirkil |author3=J. Laurie Snell |author4=Gerald L. Thompson }} Classical text. cf Chapter 6 ''Finite Markov Chains'' pp.&nbsp;384ff.
* [[John G. Kemeny]] & [[J. Laurie Snell]] (1960) ''Finite Markov Chains'', D. van Nostrand Company {{ISBN|0-442-04328-7}}
* E. Nummelin. ''General irreducible Markov chains and non-negative operators''. Cambridge University Press, 1984, 2004. {{ISBN|0-521-60494-X}}
* {{cite book|title=Markov Chains|year=1997|isbn=9780511810633|doi=10.1017/CBO9780511810633.005|last1=Norris|first1=J. R.|author-link1=James R. Norris}}
* [[Eugene Seneta|Seneta, E.]] ''Non-negative matrices and Markov chains''. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) {{ISBN|978-0-387-29765-1}}
* {{cite book |last1=Suhov |first1=Yuri |last2=Kelbert |first2=Mark |title=Markov chains: a primer in random processes and their applications |date=2008 |publisher=Cambridge University Press}}
{{refend}}

{{notelist}}

{{Queueing theory}}

[[Category:Markov processes]]