Markov Chains Reference Cheat Sheet

Key Facts

• A Markov chain has the memoryless property $P(X_{n+1}=j\mid X_n=i, X_{n-1},\ldots,X_0)=P(X_{n+1}=j\mid X_n=i)$.
• A transition matrix $P$ is stochastic, so every entry satisfies $0\le p_{ij}\le 1$ and each row sum is $\sum_j p_{ij}=1$.
• If $\mathbf{x}_n$ is a row state vector, then the next state vector is $\mathbf{x}_{n+1}=\mathbf{x}_nP$.
• The state vector after $n$ steps is $\mathbf{x}_n=\mathbf{x}_0P^n$ when using row vectors.
• A steady-state distribution $\boldsymbol{\pi}$ satisfies $\boldsymbol{\pi}P=\boldsymbol{\pi}$ and $\sum_i \pi_i=1$.
• For many regular chains, the rows of $P^n$ approach the same steady-state vector $\boldsymbol{\pi}$ as $n\to\infty$.
• In an absorbing chain written as $P=\begin{bmatrix}Q&R\\0&I\end{bmatrix}$, the fundamental matrix is $N=(I-Q)^{-1}$.
• For an absorbing chain, absorption probabilities are given by $B=NR$ and expected steps to absorption are given by $\mathbf{t}=N\mathbf{1}$.

Vocabulary

State

A state is one possible condition or category that the system can occupy at a given step.

Transition Probability

A transition probability $p_{ij}$ is the probability of moving from state $i$ to state $j$ in one step.

Transition Matrix

A transition matrix $P$ stores all one-step transition probabilities for a Markov chain.

State Vector

A state vector $\mathbf{x}_n$ lists the probabilities of being in each state after $n$ steps.

Steady-State Distribution

A steady-state distribution $\boldsymbol{\pi}$ is a probability vector that does not change after multiplying by $P$.

Absorbing State

An absorbing state is a state that cannot be left once entered, so its self-transition probability is $1$.