Example setup
Consider the discrete-time Markov chain on
$$ S=\{1,2,3,4,5\} $$with transition matrix
$$ P= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ \frac14 & 0 & \frac12 & 0 & \frac14 \\ 0 & \frac12 & 0 & \frac12 & 0 \\ 0 & 0 & 0 & \frac12 & \frac12 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}. $$What the transition matrix means
For each $i,j\in S$,
$$ p_{ij}=\mathbb P(X_{n+1}=j\mid X_n=i). $$Each row is a probability distribution, so
$$ p_{ij}\in[0,1],\qquad \sum_{j\in S}p_{ij}=1. $$The matrix describes all one-step transition probabilities.
Markov property in this example
If the chain is currently at state $2$, then the next-step distribution is determined only by row $2$:
$$ \mathbb P(X_{n+1}=1\mid X_n=2)=\frac14,\qquad \mathbb P(X_{n+1}=3\mid X_n=2)=\frac12,\qquad \mathbb P(X_{n+1}=5\mid X_n=2)=\frac14. $$All other one-step probabilities from state $2$ are $0$.
So the future depends only on the present state, not on the past history.
Accessibility
State $j$ is accessible from state $i$ if there exists some $n\ge 0$ such that
$$ p_{ij}^{(n)}>0. $$Examples in this chain:
- $3\to 4$
- $2\to 1$
- $2\to 3$
- $2\to 5$
- $4\to 5$
- $1\to 1$
- $5\to 5$
Accessibility is one-way and does not imply communication.
Communication
States $i$ and $j$ communicate if
$$ i\leftrightarrow j, $$meaning $i\to j$ and $j\to i$ both hold.
In this chain:
- $2\leftrightarrow 3$
- $3\not\leftrightarrow 4$
- $2\not\leftrightarrow 4$
- $2\not\leftrightarrow 1$
- $4\not\leftrightarrow 5$
In particular, although $3\to 4$, state $4$ cannot return to $3$, so $3$ and $4$ are not in the same communicating class.
Communicating classes
The correct communication classes are
$$ C_1=\{1\},\qquad C_2=\{2,3\},\qquad C_3=\{4\},\qquad C_4=\{5\}. $$So the chain is reducible, since the state space does not form a single communicating class.
Why the chain is reducible
A discrete-time Markov chain is irreducible iff every pair of states communicates, equivalently iff there is exactly one communicating class.
Here there are four distinct classes:
$$ \{1\},\{2,3\},\{4\},\{5\}, $$so the chain is reducible.
Structural role of each class
Class \(\{1\}\)
State $1$ is absorbing because
$$ p_{11}=1. $$Once the chain enters $1$, it stays there forever.
Class \(\{5\}\)
State $5$ is also absorbing because
$$ p_{55}=1. $$Once the chain enters $5$, it stays there forever.
Class \(\{2,3\}\)
States $2$ and $3$ communicate with each other:
$$ 2\to 3,\qquad 3\to 2. $$But this class is not closed, because
- from $2$ the chain can jump to $1$ or $5$
- from $3$ the chain can jump to $4$
So $\{2,3\}$ is not absorbing as a class.
Class \(\{4\}\)
State $4$ forms a singleton class because it can reach itself, but cannot return to $2$ or $3$.
Its outgoing moves are
$$ 4\to 4,\qquad 4\to 5. $$So $\{4\}$ is also not closed.
Aperiodicity and periodicity
State 1
Since
$$ p_{11}=1>0, $$state $1$ has period $1$, hence is aperiodic.
State 5
Since
$$ p_{55}=1>0, $$state $5$ has period $1$, hence is aperiodic.
State 4
Since
$$ p_{44}=\frac12>0, $$state $4$ can return to itself in one step, so it is aperiodic.
States 2 and 3
Returns to state $2$ occur only at even times:
- $2$ steps possible
- $4$ steps possible
- in general $\{2,4,6,\dots\}$
Hence
$$ d(2)=\gcd\{2,4,6,\dots\}=2. $$Because period is a class property, state $3$ has the same period:
$$ d(3)=2. $$So the class $\{2,3\}$ has period $2$.
n-step transition probability
The $n$-step transition probability is
$$ p_{ij}^{(n)}=\mathbb P(X_n=j\mid X_0=i). $$For example,
$$ p_{24}^{(2)} $$means the probability of starting from state $2$ and being at state $4$ exactly two steps later.
Chapman–Kolmogorov equation
For all $n,m\ge 0$,
$$ p_{ij}^{(n+m)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}^{(m)}. $$In matrix form,
$$ P^{n+m}=P^nP^m. $$This allows long-step probabilities to be decomposed through intermediate states.
Computing \(p_{24}^{(2)}\)
Using Chapman–Kolmogorov,
$$ p_{24}^{(2)}=\sum_{k=1}^5 p_{2k}p_{k4}. $$From row $2$, the only nonzero one-step moves are to $1,3,5$:
$$ p_{21}=\frac14,\qquad p_{23}=\frac12,\qquad p_{25}=\frac14. $$So
$$ p_{24}^{(2)}=p_{21}p_{14}+p_{23}p_{34}+p_{25}p_{54}. $$Now
$$ p_{14}=0,\qquad p_{34}=\frac12,\qquad p_{54}=0, $$hence
$$ p_{24}^{(2)}=\frac14\cdot 0+\frac12\cdot\frac12+\frac14\cdot 0=\frac14. $$Therefore
$$ \boxed{p_{24}^{(2)}=\frac14.} $$Computing \(p_{24}^{(3)}\) using Chapman–Kolmogorov
Using the decomposition
$$ p_{24}^{(3)}=\sum_{k=1}^5 p_{2k}p_{k4}^{(2)}, $$and again only $k=1,3,5$ matter, we get
$$ p_{24}^{(3)}
\frac14,p_{14}^{(2)} +\frac12,p_{34}^{(2)} +\frac14,p_{54}^{(2)}. $$
Because states $1$ and $5$ are absorbing,
$$ p_{14}^{(2)}=0,\qquad p_{54}^{(2)}=0, $$so
$$ p_{24}^{(3)}=\frac12\,p_{34}^{(2)}. $$Now compute
$$ p_{34}^{(2)}=\sum_{k=1}^5 p_{3k}p_{k4}. $$From row $3$, the only nonzero one-step moves are
$$ p_{32}=\frac12,\qquad p_{34}=\frac12. $$So
$$ p_{34}^{(2)}=p_{32}p_{24}+p_{34}p_{44}. $$Since
$$ p_{24}=0,\qquad p_{44}=\frac12, $$we obtain
$$ p_{34}^{(2)}=\frac12\cdot 0+\frac12\cdot\frac12=\frac14. $$Therefore
$$ p_{24}^{(3)}=\frac12\cdot\frac14=\frac18. $$So
$$ \boxed{p_{24}^{(3)}=\frac18.} $$Why Chapman–Kolmogorov reduces computation
A direct 3-step expansion would require summing over all intermediate paths.
Chapman–Kolmogorov compresses the computation into
and the many zero entries in the transition matrix eliminate most terms automatically.
So the structure of the matrix itself makes the calculation small.
Absorbing vs aperiodic
If
$$ p_{ii}=1, $$then state $i$ is absorbing, and therefore also aperiodic.
If
$$ 0So:
- absorbing $\Rightarrow$ aperiodic
- aperiodic $\nRightarrow$ absorbing
In this example:
- state $1$ is absorbing and aperiodic
- state $5$ is absorbing and aperiodic
- state $4$ is not absorbing, but is still aperiodic because $p_{44}=\frac12>0$
Summary of structural facts
- The chain is reducible.
- The communicating classes are
- States $1$ and $5$ are absorbing.
- State $4$ is a singleton class and is aperiodic.
- The class $\{2,3\}$ has period $2$.
- Accessibility is not the same as communication.
- Chapman–Kolmogorov gives
ORIGINAL HANDWRITTEN NOTE
