Calculation of $n$-step transition probabilities and class structure

The $n$-step transition probabilities $p^{(n)}_{ij}$ of a chain with finitely many states can be computed from the eigenvalues of its transition matrix. The states of a chain split into communicating classes, which break the chain into smaller pieces.

Example: a three-state Markov chain#

Example 2.1. Consider the chain on ${I = \{1, 2, 3\}}$ of Figure 1, with transition matrix

$$P = \begin{pmatrix} 0 & 1 & 0 \\[2pt] 0 & \frac12 & \frac12 \\[2pt] \frac12 & 0 & \frac12 \end{pmatrix}.$$

Figure 1. The chain of Example 2.1. The loops are the probabilities of staying.

The eigenvalues of $P$ are the roots of the characteristic polynomial ${\det(xI - P).}$ Expanding the determinant along its first row, whose third entry is 0, we get

$$\begin{aligned} \det(xI - P) &= \det \begin{pmatrix} x & -1 & 0 \\[2pt] 0 & x - \frac12 & -\frac12 \\[2pt] -\frac12 & 0 & x - \frac12 \end{pmatrix} \\[4pt] &= x \det \begin{pmatrix} x - \frac12 & -\frac12 \\[2pt] 0 & x - \frac12 \end{pmatrix} - (-1) \det \begin{pmatrix} 0 & -\frac12 \\[2pt] -\frac12 & x - \frac12 \end{pmatrix} \\[4pt] &= x \big( x - \tfrac12 \big)^2 - \tfrac14. \end{aligned}$$

Multiplying out and collecting the factor ${x - 1,}$

$$x \big( x - \tfrac12 \big)^2 - \tfrac14 = x^3 - x^2 + \tfrac14 x - \tfrac14 = x^2 (x - 1) + \tfrac14 (x - 1) = \tfrac14 (x - 1)(4x^2 + 1).$$

Hence ${0 = \det(xI - P)}$ exactly when ${x = 1}$ or ${x^2 = -1/4,}$ and the eigenvalues are 1 and ${\pm i/2.}$ They are distinct, so, as in Example 1.4, there is an invertible complex matrix $U$ with ${P = U D U^{-1},}$ where $D$ is the diagonal matrix with diagonal entries ${1, i/2, -i/2.}$ In ${P^n = (U D U^{-1})^n}$ each product $U^{-1} U$ between two factors is the identity, so ${P^n = U D^n U^{-1}}$ for every ${n \ge 0.}$ Write $u_{jk}$ and $v_{jk}$ for the entries of $U$ and $U^{-1}.$ Since $D^n$ is diagonal with entries ${1, (i/2)^n, (-i/2)^n,}$ this means that

$$p^{(n)}_{11} = (U D^n U^{-1})_{11} = \sum_{k=1}^{3} u_{1k} (D^n)_{kk} v_{k1} = A + B (i/2)^n + C (-i/2)^n,$$

with the constants ${A = u_{11} v_{11},}$ ${B = u_{12} v_{21}}$ and ${C = u_{13} v_{31}.}$ By Euler’s formula ${e^{i\theta} = \cos\theta + i \sin\theta,}$ we have ${\pm i/2 = (1/2) e^{\pm i\pi/2},}$ and we make the substitution

$$(\pm i/2)^n = (1/2)^n e^{\pm i n \pi / 2} = (1/2)^n \big( \cos(n\pi/2) \pm i \sin(n\pi/2) \big).$$

Substituting it into $p^{(n)}_{11}$ and collecting the terms in the cosine and in the sine, we get, for the constants ${B' = B + C}$ and ${C' = i (B - C),}$

$$\begin{aligned} p^{(n)}_{11} &= A + (1/2)^n \big( (B + C) \cos(n\pi/2) + i (B - C) \sin(n\pi/2) \big) \\ &= A + (1/2)^n \big( B' \cos(n\pi/2) + C' \sin(n\pi/2) \big). \end{aligned}$$

We then use the values of $p^{(n)}_{11}$ at ${n = 0, 1, 2}$ to fix $A,$ $B'$ and $C'.$ First, ${p^{(0)}_{11} = 1}$ because ${P^0 = I,}$ and ${p^{(1)}_{11} = p_{11} = 0.}$ By the Chapman–Kolmogorov equations,

$$p^{(2)}_{11} = p_{11} p_{11} + p_{12} p_{21} + p_{13} p_{31} = 0 \cdot 0 + 1 \cdot 0 + 0 \cdot \tfrac12 = 0.$$

At ${n = 0, 1, 2}$ the factor $(1/2)^n$ equals $1,$ $1/2$ and $1/4,$ the cosine $\cos(n\pi/2)$ equals $1,$ $0$ and $-1,$ and the sine $\sin(n\pi/2)$ equals $0,$ $1$ and $0.$ The three values therefore give

$$A + B' = 1, \qquad A + \tfrac12 C' = 0, \qquad A - \tfrac14 B' = 0.$$

The first equation gives ${B' = 1 - A,}$ and the third then becomes ${A - (1 - A)/4 = 0,}$ that is ${5A = 1.}$ Hence ${A = 1/5}$ and ${B' = 4/5,}$ and the second equation gives ${C' = -2A = -2/5.}$ We get

$$p^{(n)}_{11} = \frac15 + \Big( \frac12 \Big)^n \Big[ \frac45 \cos \frac{n\pi}{2} - \frac25 \sin \frac{n\pi}{2} \Big].$$

For an integer $n$ the pair ${(\cos(n\pi/2), \sin(n\pi/2))}$ depends only on the remainder of $n$ modulo 4: it is $(1, 0),$ $(0, 1),$ $(-1, 0)$ and $(0, -1)$ for the remainders 0, 1, 2 and 3. The bracket therefore takes four values,

$$\frac45 \cos \frac{n\pi}{2} - \frac25 \sin \frac{n\pi}{2} = \begin{cases} \phantom{-}4/5 & \text{if } n \equiv 0 \pmod 4, \\ -2/5 & \text{if } n \equiv 1 \pmod 4, \\ -4/5 & \text{if } n \equiv 2 \pmod 4, \\ \phantom{-}2/5 & \text{if } n \equiv 3 \pmod 4, \end{cases}$$

and the second term of $p^{(n)}_{11}$ has absolute value at most ${(4/5) 2^{-n}{:}}$ it is exponentially decaying. Since ${5 \equiv 1}$ and ${10 \equiv 2}$ modulo 4, we have

$$p^{(5)}_{11} = \frac15 - \frac25 \cdot \frac{1}{32} = \frac15 - \frac{1}{80} = \frac{3}{16}, \qquad p^{(10)}_{11} = \frac15 - \frac45 \cdot \frac{1}{1024} = \frac15 - \frac{1}{1280} = \frac{51}{256},$$

and ${|p^{(n)}_{11} - 1/5| \le (4/5) 2^{-n} < 2^{-n}}$ for every ${n \ge 0.}$ Figure 2 draws these values.

Figure 2. $p^{(n)}_{11}$ for Example 2.1 and ${n = 0, 1, \dots, 16,}$ with the level $1/5$ and the band ${1/5 \pm 2^{-n}.}$ The values at ${n = 5}$ and ${n = 10}$ are marked.

More generally, consider a chain with $m$ states, and states $i$ and $j.$
(i) Compute the eigenvalues ${\mu_1, \dots, \mu_m}$ of the ${m \times m}$ matrix $P.$
(ii) If the eigenvalues are distinct, then $p^{(n)}_{ij}$ has the form ${p^{(n)}_{ij} = a_1 + a_2 \mu_2^n + \dots + a_m \mu_m^n}$ for some constants ${a_1, \dots, a_m,}$ remembering that ${\mu_1 = 1.}$ If an eigenvalue $\mu$ is repeated $k$ times, then there is a term ${(b_0 + b_1 n + \dots + b_{k-1} n^{k-1}) \mu^n.}$
(iii) Complex eigenvalues come in conjugate pairs, and their terms can be written using sines and cosines, as in Example 2.1.

Sometimes there is a quicker way, as the next example shows.

Example: use of symmetry#

Example 2.2 (Random walk on the vertices of a complete graph). Consider a random walk on the complete graph $K_4,$ the vertices of a tetrahedron, with

$$P = \frac13 \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}.$$

The eigenvalues are ${1, -1/3, -1/3, -1/3,}$ so the general solution is ${p^{(n)}_{11} = A + (-1/3)^n (a + bn + cn^2).}$ However, symmetry can be used: for ${i \neq j,}$ ${p^{(n)}_{ij} = (1/3)(1 - p^{(n)}_{ii}).}$ Indeed, by symmetry the three entries $p^{(n)}_{ij}$ with ${j \neq i}$ are equal, and the row $i$ of $P^n$ sums to 1. So

$$p^{(n)}_{11} = \sum_{j \neq 1} p^{(n-1)}_{1j} p_{j1} = \frac13 \big( 1 - p^{(n-1)}_{11} \big).$$

Thus there is just a first-order recurrence equation, whose general solution is of the form ${p^{(n)}_{11} = A + B(-1/3)^n.}$ Since ${A + B = 1}$ and ${A + (-1/3) B = 0,}$ we have

$$p^{(n)}_{11} = \frac14 + \frac34 \Big( -\frac13 \Big)^n,$$

and ${p^{(n)}_{11} \to 1/4}$ as ${n \to \infty.}$ Do we expect the same for the random walk on the corners of a cube? No: there $p^{(n)}_{11}$ does not tend to a limit, since ${p^{(n)}_{11} = 0}$ when $n$ is odd.

Figure 3. The random walk of Example 2.2, each line a jump in either direction with probability $1/3,$ and ${p^{(n)}_{11} = 1/4 + (3/4)(-1/3)^n}$ for ${n = 0, 1, \dots, 10}$ with the level $1/4.$

Random walks and a queue#

Example (Random walk on a square). The states are the corners of a square, ${I = \{1, 2, 3, 4\},}$ and from each corner the walk moves to each of the two neighbouring corners with probability $1/2,$ as in Figure 4. The transition matrix is the stochastic matrix

$$P = \begin{pmatrix} 0 & \frac12 & 0 & \frac12 \\[2pt] \frac12 & 0 & \frac12 & 0 \\[2pt] 0 & \frac12 & 0 & \frac12 \\[2pt] \frac12 & 0 & \frac12 & 0 \end{pmatrix}.$$

Figure 4. The random walk on a square.

Example (Random walk on $\mathbb{Z}$). Let ${p \in [0, 1].}$ On ${I = \mathbb{Z},}$ the walk moves from each state $i$ to ${i + 1}$ with probability $p$ and to ${i - 1}$ with probability ${1 - p,}$ as in Figure 5. Equivalently,

$$X_{n+1} = X_n + Y_{n+1},$$

where $(Y_n)_{n \ge 1}$ are independent and identically distributed with ${P(Y_n = 1) = p}$ and ${P(Y_n = -1) = 1 - p.}$ Let ${X_0 = 0}$ and ${p > 1/2.}$ By the strong law of large numbers, almost surely

$$\frac{X_n}{n} = \frac{Y_1 + \dots + Y_n}{n} \to E[Y_1] = p - (1 - p) = 2p - 1 > 0,$$

and therefore ${X_n \to +\infty}$ almost surely.

New path

p

0.70

Figure 5. Above, the jumps of the random walk on $\mathbb{Z}.$ Below, $X_n/n$ for one path started at ${X_0 = 0}$ and ${n = 1, \dots, 400,}$ with the level ${2p - 1.}$ The slider sets $p$ and the button draws a new path.

Example (Random queue at a counter). A counter serves one customer per unit of time, and customers arrive at random. Let $A_n$ be the number of customers arriving at time $n,$ with ${P(A_n = k) = a_k}$ for ${k = 0, 1, 2, \dots,}$ where $(A_n)_{n \ge 1}$ are independent and identically distributed. If at time $n$ there are ${X_n > 0}$ customers in the queue, then ${X_{n+1} = (X_n - 1) + A_{n+1};}$ if ${X_n = 0,}$ then ${X_{n+1} = A_{n+1}.}$ In a compact formula,

$$X_{n+1} = (X_n - 1)^+ + A_{n+1},$$

Indeed, ${(X_n - 1)^+ = \max(X_n - 1, 0)}$ is ${X_n - 1}$ when ${X_n > 0}$ and 0 when ${X_n = 0,}$ and, with ${X_0 = i}$ fixed, the recursion is the construction ${X_{n+1} = F(X_n, A_{n+1})}$ of the previous post with ${F(j, a) = (j - 1)^+ + a,}$ so $(X_n)_{n \ge 0}$ is $\mathrm{Markov}(\delta_i, P)$ for a transition matrix $P.$

Class structure#

It is sometimes possible to break a Markov chain into smaller pieces, each of which is relatively easy to understand, and which together give an understanding of the whole. This is done by identifying the communicating classes of the chain. Recall the chain of Example 1.1, drawn in Figure 6.

We say that $i$ leads to $j,$ and write ${i \to j,}$ if

$$P_i(X_n = j \text{ for some } n \ge 0) > 0.$$

We say that $i$ communicates with $j,$ and write ${i \leftrightarrow j,}$ if both ${i \to j}$ and ${j \to i.}$ A state $i$ is reachable from a state $j$ when ${p^{(n)}_{ji} > 0}$ for some $n.$

State 4 leads to the states {1, 2, 3, 4, 5, 6, 7} and communicates with the states {4, 5, 6}.

Figure 6. The chain of Example 1.1, an instance. Choosing a pad $i$ marks every pad $j$ with ${i \to j,}$ and shades those with ${i \leftrightarrow j.}$

Closed classes#

For states $i,$ $j$ and $k,$ if ${i \leftrightarrow j}$ and ${j \leftrightarrow k}$ then ${i \leftrightarrow k.}$ From the definition, with ${n = 0,}$ also ${i \leftrightarrow i.}$ So $\leftrightarrow$ satisfies the conditions for an equivalence relation on $I,$ and it partitions $I$ into communicating classes. We say that a class $C$ is closed if

$$i \in C, \ i \to j \implies j \in C.$$

A closed class is one from which there is no escape. A state $i$ is absorbing if $\{i\}$ is a closed class. If $C$ is not closed, then it is open, and there exist ${i \in C}$ and ${j \notin C}$ with ${i \to j{:}}$ the chain can escape from $C.$

Example 2.5. Find the classes of the chain with transition matrix

$$P = \begin{pmatrix} \frac12 & \frac12 & 0 & 0 & 0 & 0 \\[2pt] 0 & 0 & 1 & 0 & 0 & 0 \\[2pt] \frac13 & 0 & 0 & \frac13 & \frac13 & 0 \\[2pt] 0 & 0 & 0 & \frac12 & \frac12 & 0 \\[2pt] 0 & 0 & 0 & 0 & 0 & 1 \\[2pt] 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

and say whether they are open or closed. The classes can be read off the diagram of Figure 7: they are ${\{1, 2, 3\},}$ $\{4\}$ and ${\{5, 6\},}$ with only $\{5, 6\}$ being closed.

Figure 7. The chain of Example 2.5 and its classes.

Example (Gambler’s ruin problem). A gambler wins or loses a coin at each time ${n = 1, 2, \dots{:}}$ the gambler wins with probability $p$ and loses with probability ${1 - p,}$ where ${0 < p < 1,}$ and the single bets are independent. For a fixed number ${N \ge 2,}$ the game ends when the gambler has $N$ coins (win) or 0 coins (ruin). The number of coins is a chain on ${I = \{0, 1, \dots, N\}}$ with transition matrix

$$P = \begin{pmatrix} 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 1 - p & 0 & p & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 - p & 0 & p & \cdots & 0 & 0 & 0 \\ \vdots & & \ddots & \ddots & \ddots & & & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1 - p & 0 & p \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \end{pmatrix},$$

whose rows and columns are indexed by ${0, 1, \dots, N.}$ The classes of states are ${\{0\},}$ $\{N\}$ and ${\{1, \dots, N - 1\}.}$ Indeed, for ${1 \le i \le j \le N - 1,}$

$$p^{(j-i)}_{ij} = p^{\, j-i} > 0, \qquad p^{(j-i)}_{ji} = (1 - p)^{j-i} > 0,$$

because the only sequence of ${j - i}$ steps from $i$ to $j$ moves up at every step, and the only one from $j$ to $i$ moves down at every step. So all the states ${1, \dots, N - 1}$ communicate.

p₂₄⁽²⁾ = p² = 0.3600, p₄₂⁽²⁾ = (1 − p)² = 0.1600

N

6

p

0.60

i

2

j

4

Figure 8. The gambler’s ruin chain with its classes. The sliders set $N,$ $p$ and two states ${1 \le i \le j \le N - 1;}$ the paths of ${j - i}$ steps between them are marked with their probabilities.

Irreducibility#

A chain or transition matrix $P$ in which $I$ is a single class is called irreducible. It is easy to detect: we just have to check that ${i \to j}$ for every $i$ and $j.$

Period of a state#

The last definition uses the entries $p^{(n)}_{ii}$ of the $n$-step transition matrix.

Definition (Period). The period of a state $i$ is

$$d(i) = \gcd \{ n \ge 1 : p^{(n)}_{ii} > 0 \},$$

the greatest common divisor of the set, when this set is nonempty.

Definition (Aperiodic state). A state $i$ is aperiodic if ${d(i) = 1.}$