Definition of Markov matrix

Definition: A Markov matrix (or stochastic matrix) is a square matrix used to describe transitions in a Markov chain. There are two types:

• Right stochastic: each row sums to 1, entries are non-negative. $P_{ij}$ = probability of transitioning from state $i$ to state $j$.
• Left stochastic: each column sums to 1, entries are non-negative.

$$P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix}$$
(Each row sums to 1.)

Properties:

• 1 is always an eigenvalue
• All eigenvalues satisfy $|\lambda| \leq 1$
• For a regular Markov chain, $P^n$ converges to a rank-1 matrix as $n \to \infty$
• The steady-state vector $\pi$ satisfies $\pi P = \pi$ (left eigenvector with eigenvalue 1)

Markov matrices are fundamental in probability theory, statistics, and applications like PageRank.