Markov chain transitions (finite-state)
A Markov chain is a stochastic process \(\{X_k\}_{k\ge 0}\) taking values in a set of states
\(\{S_1,\dots,S_m\}\) with the Markov property:
the next state depends only on the current state, not on the full past.
\[
P(X_{k+1}=S_j \mid X_k=S_i,\ X_{k-1},\dots,X_0)
=P(X_{k+1}=S_j \mid X_k=S_i).
\]
1) Transition matrix \(P\)
For a finite Markov chain, transitions are encoded in a matrix \(P\) where:
\[
P_{ij} = P(X_{k+1}=S_j \mid X_k=S_i).
\]
Each row of \(P\) is a probability distribution, so:
\[
P_{ij}\ge 0,\qquad \sum_{j=1}^{m} P_{ij}=1 \quad \text{for every } i.
\]
2) State distribution vectors \(p^{(k)}\)
Let \(p^{(k)}\) be the row vector of probabilities at time \(k\):
\[
p^{(k)}=\bigl[P(X_k=S_1),\dots,P(X_k=S_m)\bigr].
\]
The fundamental update rule is:
\[
p^{(k+1)} = p^{(k)}P.
\]
Repeating this update gives the n-step distribution:
\[
p^{(n)} = p^{(0)}P^n.
\]
3) n-step transition probabilities and matrix powers
The entries of \(P^n\) have a direct probabilistic meaning:
\((P^n)_{ij}\) is the probability of being in state \(S_j\) after \(n\) steps,
starting from state \(S_i\).
\[
(P^n)_{ij} = P(X_n=S_j \mid X_0=S_i).
\]
Efficient computation of \(P^n\) uses fast exponentiation (repeated squaring), which is much faster than multiplying \(P\) by itself \(n\) times.
4) Stationary distribution \(\pi\)
A stationary distribution is a probability vector \(\pi\) that remains unchanged after a transition:
\[
\pi = \pi P,\qquad \sum_{i=1}^{m}\pi_i = 1,\quad \pi_i\ge 0.
\]
Intuitively, if \(X_0\sim \pi\), then \(X_k\sim \pi\) for all \(k\).
Many “well-behaved” chains (irreducible + aperiodic) have a unique stationary distribution,
and \(p^{(k)}\) converges to \(\pi\) as \(k\to\infty\).
For reducible chains (multiple closed classes), stationary distributions may not be unique. A solver can still produce a valid \(\pi\), but the long-run behavior may depend on the initial state.
5) Absorbing, recurrent, and transient states
Markov chains are often analyzed via their state graph:
draw a directed edge \(S_i\to S_j\) whenever \(P_{ij}>0\).
-
Absorbing state: once entered, the chain never leaves:
\(P_{ii}=1\) and \(P_{ij}=0\) for \(j\ne i\).
-
Recurrent state: starting from that state, the chain returns to it with probability 1.
In finite chains, states in a closed communicating class are recurrent.
-
Transient state: there is a nonzero chance the chain will leave and never return.
A useful computational idea is to find strongly connected components (SCCs) in the directed graph.
An SCC is closed if it has no outgoing edges to states outside the SCC. In a finite chain:
states in closed SCCs are recurrent; states outside are transient; a singleton closed SCC with \(P_{ii}=1\) is absorbing.
6) Worked example: a 2-state “weather” chain
Consider:
\[
P=
\begin{bmatrix}
0.7 & 0.3\\
0.4 & 0.6
\end{bmatrix},
\qquad
p^{(0)}=[1,0].
\]
After one step:
\[
p^{(1)} = p^{(0)}P = [1,0]
\begin{bmatrix}
0.7 & 0.3\\
0.4 & 0.6
\end{bmatrix}
= [0.7, 0.3].
\]
After two steps:
\[
p^{(2)} = p^{(1)}P = [0.7,0.3]
\begin{bmatrix}
0.7 & 0.3\\
0.4 & 0.6
\end{bmatrix}
= [0.61, 0.39].
\]
Stationary distribution solves \(\pi=\pi P\). For this chain, you can solve the linear system to obtain a unique \(\pi\),
and long-run probabilities converge to it.
7) What the calculator shows
-
The matrix \(P\) and the computed matrix power \(P^n\).
-
The step distributions \(p^{(k)}\) (or an animated view for larger problems).
-
A state-flow diagram with arrows labeled by \(P_{ij}\) and an animated “flow” proportional to \(p^{(k)}_iP_{ij}\).
-
(Optional) a stationary distribution \(\pi\) estimate and a classification of absorbing/recurrent/transient states.
8) University extensions
Advanced topics build on the same ideas:
- Continuous-time Markov chains (CTMCs) use a generator matrix \(Q\) and matrix exponentials \(e^{tQ}\).
- Hitting/absorption probabilities and expected hitting times solve linear systems derived from \(P\).
- Mixing times quantify how fast \(p^{(k)}\) approaches \(\pi\) for ergodic chains.
