If we have a system with N states and for each state, a set of N probabilities from transitioning from that state to another state (including itself) we end up with an $N\times N$ matrix $P$ where the entry $P_{jk},j,k\in \{1,\dots ,N\}$ represents the probability of transitioning from state $j$ to state $k$.

Starting with some state, we can transition to another state, then another, with the probability of picking the next state dependent only on the existing state and the matrix $P.$ We call this sequence of random events a Markov Chain.

More formally, the sequence or random variables $X_1,X_2,\dots ,X_n$ is called a Markov Chain if

$$P(X_{n+1}=k|X_n=j,X_{n-1}=j_{n-1},\dots ,X_0=j_0)=P(X_{n+1}=k|X_n=j).$$

We write

$$p_{jk}=P(X_{n+1}=k|X_n=j),$$

and note that

$$p_{jk}\ge 0$$

and

$$\sum _{k=1}^N{p}_{jk}=1$$

for $j=1,2,\dots ,N.$ We call the $p_{jk}$ values the transition probabilities of the Markov chain.

Alternatively, we can say the sequence or random variables $X,Y,Z$ is said to form a Markov Chain (denoted $X\to Y\to Z$) if and only if $X$ and $Z$ are conditionally independent given $Y.$ Specifically, $X,Y$ and $Z$ form a Markov Chain $X\to Y\to Z$ if the joint probability mass function can be written as

$$p(x,y,z)=p(x)p(y|x)p(z|y).$$

If for some positive integer $m$ we have that for all $j,k=1,2,\dots ,N,$ then the Markov chain is said to be ergodic.

A vector whose entries are non-negative and sum to 1 is called a probability vector.

A stochastic matrix (actually, a right stochastic matrix) is a @square-matrix $A=(a_{ij})\in {\mathbb{R}}^{n\times n}$ with non-negative entries whose rows each sum to one:

$$a_{ij}\ge 0\text{for all }i,j,\sum _j{a}_{ij}=1\text{for all }i.$$

Equivalently, $A\mathbf{1}=\mathbf{1}$ with $A\ge 0$ entrywise, where $\mathbf{1}$ is the all-ones vector.

A left stochastic matrix is a @square-matrix $A=(a_{ij})\in {\mathbb{R}}^{n\times n}$ with non-negative entries whose columns each sum to one: $$a_{ij}\ge 0\text{for all }i,j,\sum _i{a}_{ij}=1\text{for all }j.$$ Equivalently, ${\mathbf{1}}^{\mathrm{\top }}A={\mathbf{1}}^{\mathrm{\top }}$ with $A\ge 0$ entrywise, where $\mathbf{1}$ is the all-ones vector.

If a matrix is both a row stochastic matrix and a column stochastic matrix, it is said to be a doubly stochastic matrix. That is, both its rows and its columns sum to 1.