Stochastic Matrices

A stochastic matrix, $A$, is a square matrices with positive real values as elements, $A \in \mathbb{M}_{nn}(\mathbb{R^{+}})$. Each element represents the probability of some transformation taking place.

They are applied to vectors that contain probabilities of a system being in a given state. For example,

and $p_{i}$ is the probability of they system being in the $i$th state.

• $A$ is left stochastic if each row sums to one.

• $A$ is right stochastic if each column sums to one.

• $A$ is doubly stochastic if each row and column sums to one. This means both $A$ and $A^{t}$ are stochastic matrices.

If

then $a_{11}$ is the probability of initially being in the 1 state and ending up in the 1 state, $a_{12}$ is the probability of initially being in the 1 state and ending up in the 2 state etc..

The total probability that a state starts in a given state and ends up in another must be one, hence

and $A$ is left stochastic.

Fixed Points¶

Let $A$ be a left stochastic matrix and $\bm{p}$ be a probability vector such that

then $\bm{p}$ is the stationary probability vector, or fixed point, of the transformation $A$.

All doubly stochastic matrices have the maximally mixed probability vector as there fixed point, such that

if $A$ is doubly stochastic.

If there exists a stocastic matrix $A$ such that $\bm{p}A = \bm{p'}$, then $\bm{p'}$ can be considered to be more mixed then $\bm{p}$.

Birkhoff-Von Neumann Theorem¶

$A \in \mathbb{M}_{nn}(\mathbb{R^{+}})$ is a doubly stochastic matrix if and only if there exists a set of numbers $\{p_{i}\}$ where $p_i \geq 0~\forall~i$ and $\sum_k p_{k} = 1$ such that

where $V_{i} \in \mathbb{M}_{nn}(\mathbb{R^{+}})$ are the $n \times n$ permutation matrices. Therefore, all doubly stochastic matrices are convex combinations of permutation matrices.