11  Markov chains

Author

Affiliation

Aditya Mahajan

McGill University

Let \(\ALPHABET X\) be a finite set. A stochastic process \(\{X_n\}_{n \ge 0}\), \(X_n \in \ALPHABET X\), is called a Markov chain if it satisfies the Markov property: for any \(n \in \integers_{\ge 0}\) and any \(x_{0:n+1} \in \ALPHABET X^{n+2}\) such that \(\PR(X_{0:n}=x_{0:n})>0\), we have \[\begin{equation}\tag{Markov property}\label{eq:Markov} \PR(X_{n+1} = x_{n+1} \mid X_{0:n} = x_{0:n}) = \PR(X_{n+1} = x_{n+1} \mid X_n = x_n). \end{equation}\]

The variable \(X_n\) is called the state of the Markov chain at time \(n\); the set \(\ALPHABET X\) is called state space. The \(\eqref{eq:Markov}\) implies that the current state captures all the information from the past that is relevant for the future. Stated differently, conditioned on the present, the past is independent of the future.

The Markov property also holds when a chain is viewed backward over a finite time horizon; Exercise 11.1 asks you to prove this. However, even if the forward chain is time-homogeneous, its backward transition probabilities may depend on time. If the chain is initialized with an invariant distribution, then the reversed chain is also time-homogeneous.

A common way to construct a Markov chain is through a state recursion \[ X_{n+1}=f_n(X_n,W_n), \] where \(W_0,W_1,\ldots\) are independent random variables and are independent of \(X_0\). Since \(W_n\) is independent of the history up to time \(n\), \[ \PR(X_{n+1}=j\mid X_{0:n}=x_{0:n}) =\PR(f_n(x_n,W_n)=j), \] which depends on the past only through the current state \(x_n\). If \(f_n=f\) for all \(n\) and the random variables \(W_n\) are identically distributed, then the resulting Markov chain is time-homogeneous. This construction will reappear when we study stochastic state-space models.

We now present some examples of Markov chains arising in different applications.

Example 11.1 (Gilbert Elliot channel model for burst erasures) The Gilbert-Elliot channel model is used to model communication channels with burst errors. The channel can be in one of two states: a “good” state (state 0) with low error probability, or a “bad” state (state 1) with high error probability. The channel state evolves as a Markov chain, and the error probability depends on the current state. This is essentially the same as the on-off Markov chain described in Example 11.4.

Example 11.2 (Ehrenfest urn model) The following urn model was introduced by @Ehrenfest1907 to illustrate the probabilistic behavior underlying Boltzmann’s \(H\)-theorem.

There are \(K\) labelled particles, each of which is in either compartment \(A\) or compartment \(B\). At each time, one particle is chosen uniformly at random and moved to the other compartment. Thus, if there are \(X_n=i\) particles in compartment \(A\) at time \(n\), then \(X_{n+1}=i-1\) with probability \(i/K\) and \(X_{n+1}=i+1\) with probability \((K-i)/K\).

Example 11.3 (Gambler’s ruin) Consider a gambler who is playing in a casino. The gambler starts with an initial fortune of $\(x_0\). At each time, the gambler places a bet where he wins $\(1\) with probability \(p\) and loses $\(1\) with probability \(1-p\). Thus, his fortune evolves as \[ X_{n+1} = X_n + Z_n \] where \(\{Z_n\}_{n \ge 0}\) is an i.i.d. sequence which takes values \(+1\) with probability \(p\) and \(-1\) with probability \(1-p\).

The gambler stops when his fortune is ruined, i.e., \(X_n = 0\). In some variations, the gambler may also stop when his fortune reaches a pre-specified amount of $\(K\).

See the following video from Veritasium for an excellent history of Markov chains and its applications

11.1 Time-homogeneous Markov chains

In this course, we will focus on time-homogeneous Markov chains. The Markov chain is called time-homogeneous if the right hand side of \(\eqref{eq:Markov}\) does not depend on \(n\). In this case, we describe the Markov chain by a state transition matrix \(P\), where \[ P_{ij}=\PR(X_{n+1}=j\mid X_n=i). \] The matrix \(P\) is row stochastic: \[ P_{ij}\ge0, \qquad \sum_{j\in\ALPHABET X}P_{ij}=1 \quad\text{for every }i\in\ALPHABET X. \]

A time-homogeneous Markov chain is completely specified by its initial distribution \(μ^{(0)}\), where \[ μ^{(0)}_i=\PR(X_0=i), \] and its transition matrix \(P\). Indeed, the chain rule and the Markov property give \[\begin{align*} &\PR(X_0=x_0,X_1=x_1,\ldots,X_n=x_n)\\ &\quad=μ^{(0)}_{x_0} P_{x_0x_1}P_{x_1x_2}\cdots P_{x_{n-1}x_n}. \end{align*}\] Thus, \(μ^{(0)}\) and \(P\) determine all the finite-dimensional distributions of the process. Conversely, any probability distribution \(μ^{(0)}\) and row-stochastic matrix \(P\) define a time-homogeneous Markov chain.

Such Markov chains can also be visualized using state transition diagrams, as illustrated in the examples below.

Example 11.4 (On-Off Markov chain) The On-Off Markov chain discussed earlier can be modelled with \(\ALPHABET X = \{0, 1\}\) and a general transition probability matrix of the form. \[ P = \MATRIX{ 1 - a & a \\ b & 1 - b }. \] The transition matrix can be visualized as follows.

On-Off Markov chain

In spite of its simplicity, such simple on-off Markov chains are used in various applications including telecommunication systems, network traffic modeling, machine failure-repair models, gene activation, and others. Some properties of the on-off Markov chain are as follows:

• If \(a + b = 1\), then both rows of the transition matrix are identical. Therefore, the Markov chain has no memory and is equivalent to a Bernoulli process with success probability \(a = 1-b\).

• When \(a\) or \(b\) are small, the corresponding state is “sticky”, i.e., when the Markov chain enters a sticky state, it stays there for a long time.

Example 11.5 The Ehrenfest urn model presented in Example 11.2 can be modelled as a Markov chain with state space \(\{0, 1, \dots, K\}\) and transition probability \[ P_{ij} = \begin{cases} i/K & j = i-1 \\ (K-i)/K & j = i + 1 \\ 0 & \text{otherwise}. \end{cases} \] The transition matrix can be visualized as follows.

Ehrenfest urn model

Example 11.6 (Random walk in one dimension) Imagine a particle which moves in a straight line in unit steps. Each step is one unit to the right with probability \(p\) or one unit to the left with probability \(q = 1-p\). It moves until it reaches one of two extreme points, which are called boundary points. The behavior of the particle at the boundary determines several different possibilities.

We will consider the case where the state space is \(\ALPHABET X = \{-2, -1, 0, 1, 2\}\) and the process starts in state \(0\).

1. Absorbing random walk: Assume that when the particle reaches a boundary state, it stays there from that time on. We may visualize the Markov chain as follows.

   

   Absorbing random walk

   In this case, the transition matrix is given by \[ P = \MATRIX{ 1 & 0 & 0 & 0 & 0 \\ q & 0 & p & 0 & 0 \\ 0 & q & 0 & p & 0 \\ 0 & 0 & q & 0 & p \\ 0 & 0 & 0 & 0 & 1}. \]

2. Reflected random walk: Assume that when the particle reaches a boundary states, it is reflected and returns to the point it came from. We may visualize the Markov chain as follows.

   

   Reflected random walk

   In this case, the transition matrix is given by \[ P = \MATRIX{ 0 & 1 & 0 & 0 & 0 \\ q & 0 & p & 0 & 0 \\ 0 & q & 0 & p & 0 \\ 0 & 0 & q & 0 & p \\ 0 & 0 & 0 & 1 & 0}. \]

3. Random walk with restart: Assume that when the particle reaches a boundary state, it restarts in the initial state. We may visualize the Markov chain as follows.

   

   Random walk with restart

   In this case, the transition matrix is given by \[ P = \MATRIX{ 0 & 0 & 1 & 0 & 0 \\ q & 0 & p & 0 & 0 \\ 0 & q & 0 & p & 0 \\ 0 & 0 & q & 0 & p \\ 0 & 0 & 1 & 0 & 0}. \]

4. Random walk with periodic boundary: Assume that when the particle reaches a boundary state, it moves to the other boundary. We may visualize the Markov chain as follows.

   

   Random walk with periodic boundary

   In this case, the transition matrix is given by \[ P = \MATRIX{ 0 & 0 & 0 & 0 & 1 \\ q & 0 & p & 0 & 0 \\ 0 & q & 0 & p & 0 \\ 0 & 0 & q & 0 & p \\ 1 & 0 & 0 & 0 & 0}. \]

Note that the gambler’s fortune in Example 11.3 is a random walk on non-negative integers \(\{0,1,2, \dots\}\) with absorption at \(0\). In the variation where the gambler stops when his fortune reaches $\(K\), it is a random walk over \(\{0,1,\dots,K\}\) with absorption at both ends: \(0\) and \(K\).

11.1.1 Properties of interest

Depending on the application, we are typically interested in the following properties of a Markov chain:

• If the chain starts in state \(i\), what is the probability that after \(n\) steps it is in state \(j\)?

• If the chain starts in state \(i\), what is the expected number of visits to state \(j\) in \(n\) steps?

• What is the expected number of steps that it takes for a chain starting in state \(i\) to visit state \(j\) for the first time?

• What is the average number of times that the chain is in state \(i\)? How does this depend on the initial state?

In the rest of this section, we will present results in Markov chain theory that answer the above questions.

11.2 State occupancy probabilities

1. Let \(μ^{(n)}\) denote the PMF of the state of the Markov chain at time \(n\). This is also called the state occupancy probabilities. We will think of \(μ^{(n)}\) as a row vector.

2. By the law of total probability, we have \[ \PR(X_n = j) = \sum_{i \in \ALPHABET X} \PR(X_{n-1} = i) \PR(X_n = j | X_{n-1} = i) \] or, equivalently, \[ μ^{(n)}_j = \sum_{i \in \ALPHABET X} μ^{(n-1)}_i P_{ij} \] which can be written in matrix form as \[ μ^{(n)} = μ^{(n-1)} P \] and, by recursively expanding the right hand side, we have \[ μ^{(n)} = μ^{(0)} P^n. \]

3. We will abbreviate \([P^n]_{ij}\) as \(P^{(n)}_{ij}\). Note that \[ P^{(n)}_{ij} = \PR(X_n = j \mid X_0 = i) \] denotes the \(n\)-step transition probability.

4. Chapman-Kolmogorov equations: The multi-step transition probabilities satisfy the following: for any positive integers \(m\) and \(n\) and \(i,j \in \ALPHABET X\), we have \[ P^{(n+m)}_{ij} = \sum_{k \in \ALPHABET X} P^{(n)}_{ik} P^{(m)}_{kj}. \] Thus, the probability of going from \(i\) to \(j\) in \(n+m\) steps equals the probability of going from \(i\) to somewhere in \(n\) steps and then from there to \(j\) in \(m\) steps.

Example 11.7 Numerically compute the state occupancy probabilities for the different examples of random walk presented in Example 11.6 when \(p = q = \tfrac 12\) for \(n \in \{1, \dots, 8\}\). In all cases, the initial probability \[ μ^{(0)} = \MATRIX{0 & 0 & 1 & 0 & 0 }. \]

NoteSolution

1. Absorbing random walk: In this case, we have

   • \(μ^{(0)} = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]\)
   • \(μ^{(1)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(2)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(3)} = \left[ \begin{array}{ccccc} \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(4)} = \left[ \begin{array}{ccccc} \frac{3}{8} & 0 & \frac{1}{4} & 0 & \frac{3}{8} \\ \end{array} \right]\)
   • \(μ^{(5)} = \left[ \begin{array}{ccccc} \frac{3}{8} & \frac{1}{8} & 0 & \frac{1}{8} & \frac{3}{8} \\ \end{array} \right]\)
   • \(μ^{(6)} = \left[ \begin{array}{ccccc} \frac{7}{16} & 0 & \frac{1}{8} & 0 & \frac{7}{16} \\ \end{array} \right]\)
   • \(μ^{(7)} = \left[ \begin{array}{ccccc} \frac{7}{16} & \frac{1}{16} & 0 & \frac{1}{16} & \frac{7}{16} \\ \end{array} \right]\)
   • \(μ^{(8)} = \left[ \begin{array}{ccccc} \frac{15}{32} & 0 & \frac{1}{16} & 0 & \frac{15}{32} \\ \end{array} \right]\)

2. Reflected random walk: In this case, we have

   • \(μ^{(0)} = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]\)
   • \(μ^{(1)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(2)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(3)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(4)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(5)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(6)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(7)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(8)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)

3. Random walk with restart: In this case, we have

   • \(μ^{(0)} = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]\)
   • \(μ^{(1)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(2)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(3)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 \\ \end{array} \right]\)
   • \(μ^{(4)} = \left[ \begin{array}{ccccc} \frac{1}{8} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{8} \\ \end{array} \right]\)
   • \(μ^{(5)} = \left[ \begin{array}{ccccc} \frac{1}{8} & \frac{1}{8} & \frac{1}{2} & \frac{1}{8} & \frac{1}{8} \\ \end{array} \right]\)
   • \(μ^{(6)} = \left[ \begin{array}{ccccc} \frac{1}{16} & \frac{1}{4} & \frac{3}{8} & \frac{1}{4} & \frac{1}{16} \\ \end{array} \right]\)
   • \(μ^{(7)} = \left[ \begin{array}{ccccc} \frac{1}{8} & \frac{3}{16} & \frac{3}{8} & \frac{3}{16} & \frac{1}{8} \\ \end{array} \right]\)
   • \(μ^{(8)} = \left[ \begin{array}{ccccc} \frac{3}{32} & \frac{3}{16} & \frac{7}{16} & \frac{3}{16} & \frac{3}{32} \\ \end{array} \right]\)

4. Random walk with periodic boundary: In this case, we have

   • \(μ^{(0)} = \left[ \begin{array}{ccccc} 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]\)
   • \(μ^{(1)} = \left[ \begin{array}{ccccc} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \end{array} \right]\)
   • \(μ^{(2)} = \left[ \begin{array}{ccccc} \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(3)} = \left[ \begin{array}{ccccc} \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ \end{array} \right]\)
   • \(μ^{(4)} = \left[ \begin{array}{ccccc} \frac{3}{8} & 0 & \frac{1}{4} & 0 & \frac{3}{8} \\ \end{array} \right]\)
   • \(μ^{(5)} = \left[ \begin{array}{ccccc} \frac{3}{8} & \frac{1}{8} & 0 & \frac{1}{8} & \frac{3}{8} \\ \end{array} \right]\)
   • \(μ^{(6)} = \left[ \begin{array}{ccccc} \frac{7}{16} & 0 & \frac{1}{8} & 0 & \frac{7}{16} \\ \end{array} \right]\)
   • \(μ^{(7)} = \left[ \begin{array}{ccccc} \frac{7}{16} & \frac{1}{16} & 0 & \frac{1}{16} & \frac{7}{16} \\ \end{array} \right]\)
   • \(μ^{(8)} = \left[ \begin{array}{ccccc} \frac{15}{32} & 0 & \frac{1}{16} & 0 & \frac{15}{32} \\ \end{array} \right]\)

Example 11.8 Analytically compute the state occupancy probabilities for the on-off Markov chain of Example 11.4 when it starts from the initial probability distribution \(μ^{(0)}\).

NoteSolution

Since \(μ^{(n+1)} = μ^{(n)} P\), we have \[\begin{align*} μ^{(n+1)}_0 &= μ^{(n)}_0 (1-a) + μ^{(n)}_1 b \\ &= μ^{(n)}_0 (1-a) + (1 - μ^{(n)}_0) b \\ &= μ^{(n)}_0 (1-a-b) + b. \end{align*}\] If \(a = b = 0\), then \(μ^{(n+1)}_0 = μ^{(n)}_0 = \cdots = μ^{(0)}_0\). If not, we exploit the fact that \[ b = \frac{b}{a+b} - \frac{b}{a+b}(1-a-b) \] to recursively write \[\begin{align*} μ^{(1)}_0 &= μ^{(0)}_0 (1-a-b) + b \\ &= \left(μ^{(0)}_0 - \frac{b}{a+b}\right)(1-a-b) + \frac{b}{a+b} \end{align*}\] and \[\begin{align*} μ^{(2)}_0 &= μ^{(1)}_0 (1-a-b) + b \\ &= \left(μ^{(0)}_0 - \frac{b}{a+b}\right)(1-a-b)^2 + \frac{b}{a+b}(1-a-b) + b \\ &= \left(μ^{(0)}_0 - \frac{b}{a+b}\right)(1-a-b)^2 + \frac{b}{a+b} \end{align*}\] and, so on, to get \[\begin{align*} μ^{(n)}_0 &= μ^{(n-1)}_0 (1-a-b) + b \\ &= \left(μ^{(0)}_0 - \frac{b}{a+b}\right)(1-a-b)^n + \frac{b}{a+b}(1-a-b) + b \\ &= \left(μ^{(0)}_0 - \frac{b}{a+b}\right)(1-a-b)^n + \frac{b}{a+b}. \end{align*}\] Therefore, \[ μ^{(n)}_1 = 1 - μ^{(n)}_0 = \left(μ^{(0)}_1 - \frac{a}{a+b}\right)(1-a-b)^n + \frac{a}{a+b}. \]

WarningHow did we figure out the above calculation?

The above analysis appears to be a bit of black magic. To understand what is going on, note that we are interested in computing \(μ^{(0)} P^n\). An efficient way to compute \(P^n\) is through an eigendecomposition. Since \(P\) is a row-stochastic matrix, we have \(P \mathbf{1} = \mathbf{1}\), where \(\mathbf{1}\) is the all-ones vector. Thus, \(λ_1 = 1\) is always an eigenvalue of any transition matrix, with corresponding eigenvector \(\mathbf{1}\).

For Example 11.4, we can explicitly compute all eigenvalues by finding the roots of the characteristic equation \[\begin{align*} \det(λI - P) &= \DET{λ - 1 + a & - a \\ -b & λ - 1 + b} \\ &= (λ-1 +a)(λ-1+b) - ab \\ &= (λ-1)^2 + (a+b)(λ-1) = (λ-1)(λ-1 + a + b). \end{align*}\] Thus, the eigenvalues are \(λ_1 = 1\) and \(λ_2 = 1 - a - b\).

For the special case of \(2 × 2\) transition matrices, we can find the second eigenvalue by observing that \(λ_1 = 1\) is always an eigenvalue and \(\TR(P) = λ_1 + λ_2 = 1 + λ_2\) or \(\det(P) = λ_1 λ_2 = λ_2\).

To find the eigenvector, we find a vector \(v\) such that \((λI - P)v = 0\).

• For \(λ_1 = 1\), we already know that \(v_1 = [1; 1]\) is an eigenvector.
• For \(λ_2 = (1-a-b)\), we have \[ λ_2I - P = \MATRIX{-b & -a \\ -b & -a}. \] Therefore, one possible eigenvector is \([a; -b]\).

Assume that \(a+b>0\). Then, from the eigendecomposition, we have \[ P^n=VΛ^nV^{-1}, \] where \[ V=\MATRIX{1&a\\1&-b}, \qquad Λ=\MATRIX{1&0\\0&1-a-b}, \qquad V^{-1}=\frac1{a+b}\MATRIX{b&a\\1&-1}. \] Let \(μ^{(0)}=\MATRIX{μ^{(0)}_0&1-μ^{(0)}_0}\) and define \[ d=μ^{(0)}_0-\frac{b}{a+b}. \] Then, \[\begin{align*} μ^{(n)} &=μ^{(0)}VΛ^nV^{-1}\\ &=\MATRIX{1&(a+b)d} \MATRIX{1&0\\0&(1-a-b)^n} \frac1{a+b}\MATRIX{b&a\\1&-1}\\ &=\MATRIX{\dfrac1{a+b}&d(1-a-b)^n} \MATRIX{b&a\\1&-1}\\ &=\MATRIX{ \dfrac{b}{a+b}+d(1-a-b)^n & \dfrac{a}{a+b}-d(1-a-b)^n }. \end{align*}\] This gives both components of the occupancy distribution and agrees with the recursion derived above.

11.3 Class structure

1. We say that a state \(j\) is accessible from state \(i\) (abbreviated as \(i \rightsquigarrow j\)) if there exists an \(m \in \integers_{\ge 0}\) (which may depend on \(i\) and \(j\)) such that \([P^m]_{ij} > 0\). The fact that \(P^{(m)}_{ij} > 0\) implies that there exists an ordered sequence of states \((i_0, \dots, i_m)\) such that \(i_0 = i\) and \(i_m = j\) such that \(P_{i_k i_{k+1}} > 0\); thus, there is a path of positive probability from state \(i\) to state \(j\).

   Accessibility is a transitive relationship, i.e., if \(i \rightsquigarrow j\) and \(j \rightsquigarrow k\), then \(i \rightsquigarrow k\).

   Example 11.9 Consider the Markov chain shown below.

   

   1. Identify all states that are accessible from state \(1\).
   2. Identify all states from which state \(1\) is accessible.
   NoteSolution

   1. States accessible from state \(1\) are \(\{1,2,3\}\).
   2. States from which state \(1\) is accessible are \(\{1,2,3,4,5,6\}\).

2. Two distinct states \(i\) and \(j\) are said to communicate (abbreviated to \(i \leftrightsquigarrow j\)) if \(i\) is accessible from \(j\) (i.e., \(j \rightsquigarrow i\)) and \(j\) is accessible from \(i\) (\(i \rightsquigarrow j\)). Alternatively, we say that \(i\) and \(j\) communicate if there exist \(m, m' \in \integers_{\ge 0}\) such that \(P^{(m)}_{ij} > 0\) and \(P^{(m')}_{ji} > 0\).

   For instance, in Example 11.9, state \(1\) communicates with state \(2\) but does not communicate with state \(5\).

   Communication is an equivalence relationship, i.e., it is reflexive (\(i \leftrightsquigarrow i\)), symmetric (\(i \leftrightsquigarrow j\) if and only if \(j \leftrightsquigarrow i\)), and transitive (\(i \leftrightsquigarrow j\) and \(j \leftrightsquigarrow k\) implies \(i \leftrightsquigarrow k\)).

3. The states in a finite-state Markov chain can be partitioned into two sets: recurrent states and transient states. A state is recurrent if it is accessible from all states that are accessible from it (i.e., \(i\) is recurrent if \(i \rightsquigarrow j\) implies that \(j \rightsquigarrow i\)). States that are not recurrent are transient.

4. It can be shown that a state \(i\) is recurrent if and only if \[ \sum_{m=1}^{∞}P^{(m)}_{ii}=∞. \] This follows from the strong Markov property, which is stated in Theorem 11.1.

5. States \(i\) and \(j\) are said to belong to the same communicating class if \(i\) and \(j\) communicate. Communicating classes form a partition of the state space. Within a communicating class, all states are of the same type, i.e., either all states are recurrent (in which case the class is called a recurrent class) or all states are transient (in which case the class is called a transient class).

   For example, in Example 11.9, there are two communication classes: \(\{1,2,3\}\) and \(\{4,5,6\}\). The communication class \(\{4,5,6\}\) is transient while the communication class \(\{1,2,3\}\) is recurrent.

6. A communicating class \(C\) is said to be closed if \[ i \in C \text{ and } i \rightsquigarrow j \implies j \in C. \] Thus, there is no escape from a closed class. For finite state spaces, a recurrent class is always closed and a transient class is never closed. But this is not the case for countable state Markov chains.

7. A state \(i\) is called absorbing if \(\{i\}\) is a closed class, i.e., if \(P_{ii} = 1\).

8. A Markov chain with a single communicating class (thus, all states communicate with each other and are, therefore, recurrent) is called irreducible.

9. If \(C\) is a finite irreducible closed set of states, then every state in \(C\) is recurrent. This is an important result for finite-state Markov chains: any finite closed communicating class must be recurrent.

10. The period of a state \(i\), denoted by \(d(i)\), is defined as \[d(i) = \gcd\{ t \in \integers_{\ge 1} : [P^t]_{ii} > 0 \}.\] If the period is \(1\), the state is aperiodic, and if the period is \(2\) or more, the state is periodic. It can be shown that all states in the same class have the same period.

11. A Markov chain is aperiodic if all states are aperiodic. A simple sufficient (but not necessary) condition for an irreducible Markov chain to be aperiodic is that there exists a state \(i\) such that \(P_{ii}>0\). For a finite, irreducible, and aperiodic Markov chain, there exists a positive integer \(M\) such that \[ P^{(m)}_{ij}>0, \qquad \forall m\ge M,\quad i,j\in\ALPHABET X. \]

11.4 Hitting times and absorption probabilities

1. We use the following notation:

   • For any event \(E\), \(\PR_i(E)\) denotes \(\PR(E \mid X_0 = i)\)
   • For any random variable \(Y\), \(\EXP_i[Y]\) denotes \(\EXP[Y \mid X_0 = i]\).

2. Let \(A\) be a subset of \(\ALPHABET X\). The hitting time \(H^A\) of \(A\) is the extended-valued random variable \(H^A \colon Ω \to \{0,1,\ldots\}\cup\{∞\}\) given by \[ H^A(ω)=\inf\{n\ge0:X_n(ω)\in A\}. \] The standard convention is that the infimum of the empty set is \(∞\). Thus, \(H^A(ω)=∞\) if the sample path never enters \(A\). For a state \(j \in \ALPHABET X\), we use the shorthand \(H^j\) to denote \(H^{\{j\}}\).

   To formalize the special role of hitting times, let \[ \mathcal F_n=\sigma(X_0,\ldots,X_n) \] denote the information available up to time \(n\). A random time \(τ\) is called a stopping time if \[ \{τ\le n\}\in\mathcal F_n, \qquad n\ge0. \] In other words, by time \(n\) we can determine whether \(τ\) has occurred. A hitting time is a stopping time because \[ \{H^A\le n\}=\bigcup_{k=0}^n\{X_k\in A\}\in\mathcal F_n. \]

   Theorem 11.1 (Strong Markov property) Let \(τ\) be a stopping time. On the event \(\{τ<∞\}\), for every \(k\ge0\) and \(j\in\ALPHABET X\), \[ \PR(X_{τ+k}=j\mid\mathcal F_τ) =P^{(k)}_{X_τj}, \] where \(\mathcal F_τ\) denotes the information available up to time \(τ\). Thus, conditional on the state \(X_τ\), the process after \(τ\) evolves like a fresh copy of the Markov chain started from \(X_τ\).

3. The probability that starting from state \(i\) the Markov chain ever hits \(A\) is then given by \[ h^A_i = \PR_i(H^A < ∞). \] This is called hitting probability. When \(A\) is a closed class, \(h^A_i\) is called the absorption probability.

4. The mean time taken for the Markov chain to reach \(A\) is given by \[ m^A_i=\EXP_i[H^A] =\sum_{n=0}^{∞}\PR_i(H^A>n), \] where the expectation and the sum are allowed to be infinite. This is called the mean hitting time.

5. A remarkable property of Markov chain is that these quantities can be computed by solving a system of linear equations associated with the transition probability matrix \(P\). We start with some examples to illustrate the main idea.

   Example 11.10 Suppose we toss a coin multiple times. What is the probability of getting a head before getting a tail?

   We model this using a Markov chain where the state represents the outcome we’re waiting for. Let \(p\) denote the probability of heads and \(q = 1-p\) denote the probability of tails. The Markov chain has three states:

   • State \(-1\): tail has occurred (absorbing state, we lose)
   • State \(0\): initial state (no outcome yet)
   • State \(1\): head has occurred (absorbing state, we win)

   

   Markov chain for coin tossing until head or tail

   Let \(h^1_i\) denote the probability of hitting state \(1\) (i.e., getting a head) when starting at state \(i\). Then, we have \[\begin{align*} h^1_{-1} &= 0, \\ h^1_0 &= p h^1_1 + q h^1_{-1} = p \cdot 1 + q \cdot 0 = p, \\ h^1_1 &= 1. \end{align*}\] Therefore, starting from state \(0\), the probability of getting a head before a tail is \(h^1_0 = p\).

6. Example 11.11 Two players are playing a game. They repeatedly toss a coin. Player 1 wins if two consecutive heads occur before two consecutive tails. Player 2 wins if two consecutive tails occur before two consecutive heads. What is the probability that Player 1 wins?

   Let \(p\) denote the probability of heads and \(q = 1-p\) denote the probability of tails. We initialize the Markov chain in state \(0\), immediately before the first toss. After the first toss and until the game ends, the state records the most recent toss; once two identical tosses occur consecutively, the chain enters the corresponding absorbing state. Thus, state \(0\) is visited only at time \(0\). For example, after \(HT\) the state is \(-1\), and after \(TH\) the state is \(1\); the chain does not return to state \(0\).

   The Markov chain has five states:

   • State \(-2\): two consecutive tails (Player 2 wins, absorbing state)
   • State \(-1\): the last toss was a tail, but two consecutive tails have not occurred
   • State \(0\): the pre-toss state, occupied only at time \(0\)
   • State \(1\): the last toss was a head, but two consecutive heads have not occurred
   • State \(2\): two consecutive heads (Player 1 wins, absorbing state)

   

   Markov chain for two heads before two tails

   Let \(h^2_i\) denote the probability of hitting state \(2\) (i.e., Player 1 wins) when starting at state \(i\). Then, we have \[\begin{align*} h^2_{-2} &= 0, \\ h^2_{-1} &= p h^2_1 + q h^2_{-2} = p h^2_1, \\ h^2_0 &= p h^2_1 + q h^2_{-1}, \\ h^2_1 &= p h^2_2 + q h^2_{-1} = p + q h^2_{-1}, \\ h^2_2 &= 1. \end{align*}\] From \(h^2_{-1}=p h^2_1\) and \(h^2_1=p+q h^2_{-1}\), we obtain \[ h^2_1=p+pq h^2_1, \qquad h^2_1=\frac{p}{1-pq}, \qquad h^2_{-1}=\frac{p^2}{1-pq}. \] Therefore, \[ h^2_0=p h^2_1+q h^2_{-1} =\frac{p^2(1+q)}{1-pq}. \] For a fair coin, \(p=q=\tfrac12\), and hence \(h^2_0=\tfrac12\).

7. We now provide a general formula for computing hitting probabilities.

   Theorem 11.2 (Hitting probabilities) The hitting probabilities \(\{h^A_i\}_{i \in \ALPHABET X}\) satisfies the following system of linear equations: \[ h^A_i = \begin{cases} 1, & i \in A \\ \sum_{j \in \ALPHABET X} P_{ij} h^A_j, & i \not\in A \end{cases} \] When \(\ALPHABET X\) is finite, the above system has a unique solution; when \(\ALPHABET X\) is countable, the above system may have multiple solutions and the hitting probabilities correspond to the minimal non-negative solution.

   NoteProof

   When \(X_0 = i \in A\), the hitting time \(H^A = 0\), so \(h^A_i = 1\). This proves the first part of the formula.

   For the second part, consider \(X_0 = i \not\in A\). Then \(H^A_i \ge 1\). By the Markov property, we have \[ \PR_i(H^A < ∞ \mid X_1 = j) = \PR_j(H^A < ∞) = h^A_j. \] Moreover, by the law of total probability, we have \[\begin{align*} h^A_i &= \PR_i(H^A < ∞) = \sum_{j \in \ALPHABET X} \PR_i(H^A < ∞, X_1 = j) \\ &= \sum_{j \in \ALPHABET X} \PR_i(H^A < ∞ \mid X_1 = j) \PR_i(X_1 = j) \\ &= \sum_{j \in \ALPHABET X} P_{ij} h^A_j. \end{align*}\]

8. Example 11.12 Consider a gambler’s ruin problem, where the gambler starts with $\(1\) and stops either when he is ruined or when his fortune reaches $\(K\).

   Find the probability of ruin (i.e., the fortune gets absorbed in state \(0\) rather than state \(K\)).

   NoteSolution

   For the ease of notation, we use \(h_i\) as a short-form for \(h^{\{0\}}_i\). The hitting probabilities satisy the linear system of equations:

   \[\begin{align*} h_0 &= 1 \\ h_i &= ph_{i+1} + q h_{i-1}, \quad i \in \{1,\dots,K-1\} \\ h_K &= 0, \end{align*}\] where \(q = 1-p\).

   The characteristic equation associated with the linear recurrence relationship is \[ λ = p λ^2 + q \] which has two distinct roots, \(λ_1 = 1\) and \(λ_2 = q/p\) if \(p \neq q\) and a double root at \(λ_1 = 1\) if \(p = q = \frac 12\). Therefore, the general solution is of the form \[ h_i = a λ_1^i + b λ_2^i = a + b\Bigl(\tfrac {q}{p} \Bigr)^i \] where we determine the coefficients \(a\) and \(b\) from the boundary conditions \(h_0 = 1\) and \(h_K = 0\). Solving for \(a\) and \(b\), we get that for \(p \neq q\), \[ h_i =\frac{\Bigl(\frac qp\Bigr)^i-\Bigl(\frac qp\Bigr)^K} {1-\Bigl(\frac qp\Bigr)^K}, \] and for \(p = q = \frac 12\), \[ h_i=1-\frac{i}{K}. \]

9. Similarly as above, we can derive a formula for computing mean hitting times. We start with a couple of examples to illustrate the main idea.

   Example 11.13 Suppose we toss a coin multiple times and stop at the first head. What is the expected number of coin tosses until stopping?

   From elementary probability we know that the number of tosses until stopping is a geometric random variable. However, we will model this using a Markov chain where the state denotes the number of consecutive heads so far. Let \(p\) denote the probability of heads and \(q = 1-p\) denote the probability of tails. Then, the Markov chain model is as follows.

   

   Markov chain for coin tossing until one head

   Let \(m^1_i\) denote the expected number of tosses until stopping (i.e., hitting state \(1\)) when starting at state \(i\). Then, we have \[\begin{align*} m^1_0 &= 1 + q m^1_0 + p m^1_1, \\ m^1_1 &= 0. \end{align*}\] Solving this system of equations, we get \(m^1_0 = 1/(1-q) = 1/p\).

10. Example 11.14 Suppose we toss a coin multiple times and stop at two consecutive heads. What is the expected number of coin tosses until stopping?

    We can model this in the same manner as before, where the state denotes the number of consecutive heads so far. The Markov chain is as follows:

    

    Markov chain for coin tossing until two heads

    Let \(m^2_i\) denote the expected number of tosses until stopping (i.e., hitting state \(2\)) when starting at state \(i\). Then, we have \[\begin{align*} m^2_0 &= 1 + q m^2_0 + p m^2_1, \\ m^2_1 &= 1 + q m^2_0 + p m^2_2, \\ m^2_2 &= 0. \end{align*}\] From the second equation, \(m^2_1=1+q m^2_0\). Substituting this into the first equation gives \[ m^2_0=1+q m^2_0+p(1+q m^2_0) =1+p+q(1+p)m^2_0. \] Since \(1-q(1+p)=p^2\), we obtain \[ m^2_0=\frac{1+p}{p^2}. \]

11. We now provide a general formula for computing mean hitting times.

    Theorem 11.3 (Mean hitting times) The mean hitting times \(\{m^A_i\}_{i \in \ALPHABET X}\) satisfies the following system of linear equations: \[ m^A_i = \begin{cases} 0, & i \in A \\ 1 + \sum_{j \not\in A} P_{ij} m^A_j, & i \not\in A \end{cases} \] When \(\ALPHABET X\) is finite, the above system has a unique solution; when \(\ALPHABET X\) is countable, the above system may have multiple solutions and the mean hitting times correspond to the minimal non-negative solution.

    NoteProof

    The proof is similar to the proof of Theorem 11.2. When \(X_0 = i \in A\), the hitting time \(H^A = 0\), so \(m^A_i = 0\). This proves the first part of the formula.

    For the second part, consider \(X_0 = i \not\in A\). Then \(H^A_i \ge 1\). By the Markov property, we have \[ \EXP_i[ H^A \mid X_1 = j] = 1 + \EXP_j[ H^A ] = 1 + m^A_j. \] Moreover, by the law of total probability, we have \[\begin{align*} m^A_i &= \EXP_i[ H^A ] = \sum_{j \in \ALPHABET X} \EXP_i[ H^A \mid X_1 = j ] \PR_i(X_1 = j) \\ &= \sum_{j \in \ALPHABET X} \EXP_i[ H^A \mid X_1 = j ] \PR_i(X_1 = j) \\ &= \sum_{j \in \ALPHABET X} P_{ij} \bigl[ 1 + m^A_j \bigr] \\ &= 1 + \sum_{j \not\in A} P_{ij} m^A_j. \end{align*}\]

12. For absorbing Markov chains, we can use matrix methods to efficiently compute hitting probabilities and mean hitting times. The key idea is to rearrange the transition matrix into a canonical form where absorbing states are grouped together.

    Suppose the state space \(\ALPHABET X\) can be partitioned into transient states \(\ALPHABET T\) and absorbing states \(\ALPHABET C\). By reordering the states so that all transient states come first, followed by all absorbing states, the transition matrix \(P\) can be written in the canonical form: \[ P = \MATRIX{ Q & R \\ 0 & I}. \] where:

    • \(Q\) is a \(|\ALPHABET T| \times |\ALPHABET T|\) matrix containing transition probabilities between transient states,
    • \(R\) is a \(|\ALPHABET T| \times |\ALPHABET C|\) matrix containing transition probabilities from transient states to absorbing states,
    • \(0\) is a \(|\ALPHABET C| \times |\ALPHABET T|\) zero matrix (since absorbing states cannot transition to transient states),
    • \(I\) is a \(|\ALPHABET C| \times |\ALPHABET C|\) identity matrix (since absorbing states stay in themselves).

13. Multi-step transitions: For the canonical form, we can show by induction that \[ P^n = \MATRIX{ Q^n & (I + Q + Q^2 + \cdots + Q^{n-1}) R \\ 0 & I}. \] This follows from the fact that matrix multiplication preserves the block structure, and the lower-left block remains zero while the lower-right block remains \(I\) for all powers.

14. Fundamental matrix: Suppose that, starting from any state in \(\ALPHABET T\), the chain is eventually absorbed in \(\ALPHABET C\) with probability \(1\). Then \(Q^n \to 0\), or equivalently the spectral radius of \(Q\) is less than \(1\). Therefore, the fundamental matrix \[ N = (I - Q)^{-1} = I + Q + Q^2 + Q^3 + \cdots \] is well-defined. Merely having an absorbing state is not sufficient: that absorbing state must be reached with probability \(1\) from every state included in \(\ALPHABET T\).

15. Interpretation of \(N_{ij}\): The entry \(N_{ij}\) represents the expected number of visits to transient state \(j\) before absorption, starting from transient state \(i\). This can be seen from the series expansion. Let \(H^{\ALPHABET C}\) denote the time of absorption. Then \[\begin{align*} N_{ij} &= \sum_{n=0}^∞ [Q^n]_{ij} = \sum_{n=0}^∞ \PR_i(X_n=j,\ n<H^{\ALPHABET C}) \\ &= \EXP_i\left[\sum_{n=0}^{H^{\ALPHABET C}-1}\IND{X_n=j}\right]. \end{align*}\] Thus, the count includes the visit at time \(0\); in particular, a chain starting in state \(i\) contributes one visit to state \(i\) immediately.

16. Mean hitting times: Let \(\ONES\) denote a column vector of ones with dimension \(|\ALPHABET T|\). Then the mean hitting times (expected time until absorption) starting from each transient state are given by \[ m = N \ONES, \] where \(m_i\) is the mean time until absorption starting from transient state \(i\).

    NoteProof

    The mean hitting time \(m_i\) equals the expected number of steps spent in transient states before absorption. Since \(N_{ij}\) represents the expected number of visits to transient state \(j\) starting from transient state \(i\), we have \[ m_i = \sum_{j \in \ALPHABET T} N_{ij} = [N \ONES]_i, \] which gives the desired result in matrix form.

17. Hitting probabilities: The hitting probabilities (absorption probabilities) are given by \[ h = N R, \] where \(h_{ij}\) is the probability of being absorbed in absorbing state \(j\) when starting from transient state \(i\).

    NoteProof

    Starting from transient state \(i\), the chain is absorbed in absorbing state \(j\) if and only if it takes some number \(n \ge 0\) of steps within transient states, and then transitions to \(j\) in step \(n+1\). The probability of being in transient state \(k\) after \(n\) steps (without being absorbed) is \([Q^n]_{ik}\), and the probability of transitioning from \(k\) to \(j\) is \(R_{kj}\). Therefore, \[ h_{ij} = \sum_{n=0}^∞ \sum_{k \in \ALPHABET T} [Q^n]_{ik} R_{kj} = \sum_{n=0}^∞ [Q^n R]_{ij} = [N R]_{ij}, \] where the last equality follows from \(N = I + Q + Q^2 + \cdots\).

18. Example 11.15 Consider the gambler’s ruin problem from Example 11.12 with \(K = 3\) (i.e., the gambler starts with $\(1\) and stops at either $\(0\) or $\(3\)). Write the transition matrix in canonical form and use the fundamental matrix to compute the probability of ruin and the expected duration of play.

    NoteSolution

    The state space is \(\{0, 1, 2, 3\}\) where states \(0\) and \(3\) are absorbing. In the natural ordering \((0, 1, 2, 3)\), the transition matrix is: \[ P = \MATRIX{ 1 & 0 & 0 & 0 \\ q & 0 & p & 0 \\ 0 & q & 0 & p \\ 0 & 0 & 0 & 1 } \] where \(q = 1-p\). Reordering to put transient states first, we use the ordering \((1, 2, 0, 3)\): \[ P = \MATRIX{ 0 & p & q & 0 \\ q & 0 & 0 & p \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 } = \MATRIX{ Q & R \\ 0 & I } \] where \[ Q = \MATRIX{ 0 & p \\ q & 0 }, \quad R = \MATRIX{ q & 0 \\ 0 & p }. \]

    The fundamental matrix is: \[ N = (I - Q)^{-1} = \MATRIX{ 1 & -p \\ -q & 1 }^{-1} = \frac{1}{1-pq} \MATRIX{ 1 & p \\ q & 1 }. \]

    The hitting probabilities are: \[ h = N R = \frac{1}{1-pq} \MATRIX{ 1 & p \\ q & 1 } \MATRIX{ q & 0 \\ 0 & p } = \frac{1}{1-pq} \MATRIX{ q & p^2 \\ q^2 & p }. \]

    Thus, starting from state \(1\), the probability of ruin (absorption in state \(0\)) is \(h_{1,0} = q/(1-pq)\) and the probability of winning (absorption in state \(3\)) is \(h_{1,3} = p^2/(1-pq)\).

    The mean hitting times are: \[ m = N \ONES = \frac{1}{1-pq} \MATRIX{ 1 & p \\ q & 1 } \MATRIX{ 1 \\ 1 } = \frac{1}{1-pq} \MATRIX{ 1+p \\ q+1 }. \]

    Thus, starting from state \(1\), the expected duration is \(m_1 = (1+p)/(1-pq)\).

11.5 Invariant Distribution

1. A probability distribution \(π\) on the state space \(\ALPHABET X\) is called an invariant distribution if it satisfies the equation \[ π = π P. \]

2. An invariant distribution is also called a stationary distribution. If the initial distribution of the Markov chain is \(π\), then the distribution remains \(π\) at all future times. In other words, if \(μ^{(0)} = π\) then \(μ^{(n)} = π\) for all \(n \ge 0\).

3. Consider the on-off Markov chain from Example 11.4 with transition matrix \[ P = \MATRIX{ 1 - a & a \\ b & 1 - b }. \] This chain has an invariant distribution given by \(π = [b/(a+b), a/(a+b)]\) (assuming \(a+b > 0\)). One can verify that \(π = π P\), which shows that an invariant distribution exists for this chain.

4. A finite Markov chain with only one communication class has a unique invariant distribution. Thus, irreducible Markov chains have a unique invariant distribution. Note that aperiodicity is not required. For instance, consider on-off Markov chain from Example 11.4 with \(a = b = 1\). This chain is periodic, but has a unique invariant distribution \(π = [\frac 12, \frac 12]\).

5. A Markov chain with more than one closed communicating class has multiple invariant distributions. For example, consider a Markov chain with two absorbing states \(0\) and \(1\). The transition matrix is \[ P = \MATRIX{ 1 & 0 \\ 0 & 1 }. \]

   

   Markov chain with two absorbing states

   In this case, any distribution of the form \(π = [α, 1-α]\) with \(α \in [0,1]\) is an invariant distribution, since \[ π P = [α, 1-α] \MATRIX{ 1 & 0 \\ 0 & 1 } = [α, 1-α] = π. \] Thus, there are uncountably many invariant distributions. This happens because the chain consists of two disjoint recurrent classes (the absorbing states \(0\) and \(1\)), and any probability mass can be put on either class and be preserved.

   More generally, if a Markov chain has multiple irreducible communicating (closed) classes, each class can have its own invariant distribution (supported only on that class). Any convex combination of these distributions is also an invariant distribution for the whole chain.

6. A Markov chain that is irreducible and aperiodic has a special prorperty: for any initial distribution \(μ^{(0)}\), we have \[\lim_{n \to ∞} μ^{(n)}_j = π_j, \quad \forall j \in \ALPHABET X.\]

   Irreducible and aperiodic Markov chains are also called ergodic. Thus, an ergodic Markov chain converges to its invariant distribution. For this reason, the invariant distribution is also called the limiting distribution or the steady-state distribution.

7. Computing invariant distributions. The equation \(π = π P\) can be written component-wise as \[ π_j = \sum_{i \in \ALPHABET X} π_i P_{ij}, \quad \forall j \in \ALPHABET X. \] These equations are called balance equations and can be used to find invariant distributions. Together with the constraint that \(π\) is a probability distribution (i.e., \(\sum_{j \in \ALPHABET X} π_j = 1\) and \(π_j \ge 0\) for all \(j\)), they form a system of linear equations that can be solved to determine the invariant distribution.

8. As an example, let’s compute the invariant distribution of the on-off Markov chain from Example 11.4. The transition matrix is \[ P = \MATRIX{ 1 - a & a \\ b & 1 - b }. \] To find the invariant distribution \(π = [π_0, π_1]\), we solve the balance equations \(π = π P\): \[\begin{align*} π_0 &= π_0 (1-a) + π_1 b, \\ π_1 &= π_0 a + π_1 (1-b). \end{align*}\] From the first equation, we get \(π_0 = π_0 (1-a) + π_1 b\), which simplifies to \(π_0 a = π_1 b\), or equivalently \(π_1 = (a/b) π_0\) (assuming \(b > 0\)). Using the normalization constraint \(π_0 + π_1 = 1\), we have \[ π_0 + \frac{a}{b} π_0 = 1 \quad \Rightarrow \quad π_0 \left(1 + \frac{a}{b}\right) = 1 \quad \Rightarrow \quad π_0 = \frac{b}{a+b}. \] Therefore, \(π_1 = 1 - π_0 = \frac{a}{a+b}\). The invariant distribution is \(π = [b/(a+b), a/(a+b)]\), which matches the result mentioned in point 3.

9. We can write balance equations directly from the state transition diagram. For each state \(j\), the balance equation states that the probability flow into state \(j\) equals the probability flow out of state \(j\). Consider the three-state Markov chain with transition matrix \[ P = \MATRIX{ 0.3 & 0.7 & 0 \\ 0 & 0.3 & 0.7 \\ 0.7 & 0 & 0.3 }. \]

   

   Three-state aperiodic Markov chain

   The balance equations, equating the flow into and out of each state, can be written as:

   • State 0:
     \[\begin{align*} \text{Inflow} &= \pi_2 \cdot 0.7 \\ \text{Outflow} &= \pi_0 \cdot 0.7 \end{align*}\]

   • State 1:
     \[\begin{align*} \text{Inflow} &= \pi_0 \cdot 0.7 \\ \text{Outflow} &= \pi_1 \cdot 0.7 \end{align*}\]

   • State 2:
     \[\begin{align*} \text{Inflow} &= \pi_1 \cdot 0.7 \\ \text{Outflow} &= \pi_2 \cdot 0.7 \end{align*}\]

   Thus, the balance equations are given by \[\begin{align*} \pi_0 \cdot 0.7 = \pi_2 \cdot 0.7 \\ \pi_1 \cdot 0.7 = \pi_0 \cdot 0.7 \\ \pi_2 \cdot 0.7 = \pi_1 \cdot 0.7 \end{align*}\] Together with the normalization constraint \(π_0 + π_1 + π_2 = 1\), we get \(π_0 = π_1 = π_2 = 1/3\). This illustrates how balance equations can be derived directly from the state diagram by considering probability flows.

10. The above example is an illustration of a more general principle. If \(P\) is doubly stochastic (i.e., both row sum and column sums are \(1\)), then the invariant distribution is a uniform distribution.

11. Exercises: Computing Invariant Distributions

    Example 11.16 Consider the Markov chain with transition matrix
    \[ P = \MATRIX{ 0.6 & 0.4 & 0 & 0 \\ 0.3 & 0.7 & 0 & 0 \\ 0.2 & 0.3 & 0.3 & 0.2 \\ 0.1 & 0.4 & 0.1 & 0.4 }. \]

    

    Markov chain with transient states and closed class

    This chain has states \(\{0, 1, 2, 3\}\) where states \(\{0, 1\}\) form a closed communicating class and states \(\{2, 3\}\) are transient. Find all invariant distributions for this chain.

    Example 11.17 Consider the Markov chain with transition matrix
    \[ P = \MATRIX{ 1 & 0 & 0 \\ 0.2 & 0.4 & 0.4 \\ 0 & 0 & 1 }. \]

    

    Markov chain with absorbing states

    Note that this chain is not irreducible (it has two absorbing states). Compute all possible invariant distributions.

11.6 Limiting Distribution

1. Suppose a finite Markov chain has the property that starting from any initial distribution, the distribution of \(X_n\) converges to some distribution \(\pi\) as \(n \to \infty\): \[ \lim_{n \to \infty} P^{(n)}_{i, j} = \pi_j \qquad \text{for all } i, j \in \ALPHABET X. \] Then, \(\pi\) is an invariant distribution.

   NoteProof

   We start by showing that \(π\) must be a valid probability distribution. In particular, \[ \sum_{j \in \ALPHABET X} π_j = \sum_{j \in \ALPHABET X} \lim_{n \to ∞} P^{(n)}_{ij} = \lim_{n \to ∞} \sum_{j \in \ALPHABET X} P^{(n)}_{ij} = 1 \]

   We now show that \(π\) is an invariant distribution. \[ π_j = \lim_{n \to ∞} P^{(n)}_{ij} = \lim_{n \to ∞} \sum_{k \in \ALPHABET X} P^{(n-1)}_{ik} P_{kj} = \sum_{k \in \ALPHABET X} \lim_{n \to ∞} P^{(n-1)}_{ik} P_{kj} = \sum_{k \in \ALPHABET X} π_k P_{kj} \] Thus, \(π\) is an invariant distribution.

2. As discussed above, limiting distributions exist for ergodic Markov chains (i.e., irreducible and aperiodic Markov chains): for any initial distribution \(μ^{(0)}\), we have \[\lim_{n \to ∞} μ^{(n)}_j = π_j, \quad \forall j \in \ALPHABET X.\]

   This is equivalent to the statement that for all \(i, j \in \ALPHABET X\), \[\lim_{n \to \infty} P^{(n)}_{ij} = π_j.\] This is an consequence of :Perron Frobenius Theorem. In matrix form, we have \[ \lim_{n \to \infty} P^n = \MATRIX{ \pi \\ \pi \\ \vdots \\ \pi } \] where each row of the limiting matrix is the invariant distribution \(π\). That is, for large \(n\), every row of \(P^n\) approaches \(π\).

3. In fact, we have a stronger result: the Strong Law of Large Numbers (SLLN) for (finite) Markov chains. Let \(\{X_n\}_{n \ge 0}\) be an irreducible and aperiodic (i.e., ergodic) Markov chain. Then, for any initial distribution, \[ \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \IND\{X_n = j\} \xrightarrow{a.s.} \pi_j, \quad \forall j \in \ALPHABET X. \] This is known as ergodic property: sample average equals ensemble average.

4. An immediate consequence of the ergodic property is that given an ergodic Markov chain \(\{X_n\}_{n \ge 0}\) and any function \(f \colon \ALPHABET X \to \reals\), we have \[ \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N f(X_n) \xrightarrow{a.s.} \sum_{j\in \ALPHABET X} \pi_j f(j). \]

5. If the chain is periodic with period \(d > 1\) (i.e., not aperiodic), the limiting distribution \(\lim_{n \to \infty} P^n\) does not exist in the usual sense, as the transition probabilities continue to oscillate. However, if the chain is irreducible, it still possesses a unique invariant distribution \(π\). In the periodic case, results like ergodicity and the law of large numbers still hold if we consider time averages over subsequences that are integer multiples of the period \(d\), i.e., convergence happens along these subsequences, not along every \(n\).

11.7 Censored Markov chains

1. Suppose a Markov chain is only observed when the state lies in a subset \(\ALPHABET O \subset \ALPHABET X\). Let \(\{τ_k\}_{k \ge 1}\) denote the when the Markov chain returns to the set \(\ALPHABET O\), i.e., \(τ_1\) is the first time when the Markov chain \(\{X_n\}_{n \ge 1}\) hits \(\ALPHABET O\); \(τ_2\) denotes the second time when the Markov chain hits \(\ALPHABET O\); and so on.

2. Define the process \(\{O_k\}_{k \ge 1}\) by \(O_k = X_{τ_k}\). The strong Markov property implies that \(\{O_k\}_{k \ge 1}\) is a Markov chain. What is the transition probability matrix \(\tilde P\) of this chain?

3. As we did for the absorbing Markov chains, we re-order states so that the unobservable states \(\ALPHABET O^c\) come first, followed by all observable state \(\ALPHABET O\). Then the transition matrix \(P\) can be written as \[ P = \MATRIX{ Q & R \\ S & P_O } \] where:

   • \(Q\) is a \(\ABS{\ALPHABET O^c} × \ABS{\ALPHABET O^c}\) matrix containing the transition probabilities between unobserved states,
   • \(R\) is a \(\ABS{\ALPHABET O^c} × \ABS{\ALPHABET O}\) matrix containing the transition probabilities from unobserved to observed states,
   • \(S\) is the \(\ABS{\ALPHABET O} × \ABS{\ALPHABET O^c}\) matrix containing the transition probabilities from observed to unobserved states
   • \(P_O\) is the \(\ABS{\ALPHABET O} × \ABS{\ALPHABET O}\) matrix containing the transitions from observed to observed states.

4. Suppose we start with a state \(O_1 = X_1 \in \ALPHABET O\). Then the probability of going to each of the states in \(\ALPHABET O\) in one step is given by \(P_O\). To take more than one step, the chain must enter a state in \(\ALPHABET O^c\) with probability \(S\). We will assume that the set \(\ALPHABET O^c\) does not have any obsorbing subsets. Then, as we showed in the analysis for absorbing Markov chains, starting from a given state in \(\ALPHABET O^c\), the Markov chain enters \(\ALPHABET O\) for the first time with probability \(NR = (I - Q)^{-1} R\). Thus, we have that \[ \tilde P = P_O + S(I - Q)^{-1}R. \]

5. If \(P\) has only one communicating class, then \(\{X_n\}_{n \ge 1}\) has a unique invariant distribution, which we denote by \(π\). Then \((π_k)_{k \in \ALPHABET O}\) normalized to have sum \(1\) is the unique invariant distribution of \(\{O_n\}_{n \ge 1}\).

6. As an example, consider the reflected random walk from Example 11.6 (point 2) with state space \(\{-2, -1, 0, 1, 2\}\)

   

   Reflected random walk

   Suppose we only observe the process when \(X_n \in \ALPHABET O = \{0, 1, 2\}\), so the unobservable states are \(\ALPHABET O^c = \{-2, -1\}\).

   Since the states are already ordered in the right order, we can write the transition matrix as: \[ P = \left[\begin{array}{cc|ccc} 0 & 1 & 0 & 0 & 0 \\ q & 0 & p & 0 & 0 \\ \hline 0 & q & 0 & p & 0 \\ 0 & 0 & q & 0 & p \\ 0 & 0 & 0 & 1 & 0\end{array}\right]. \]

   To simplify computations, we will assume \(p = \tfrac{1}{4}\) and \(q = \tfrac{3}{4}\). Then, the transition matrix of the Markov chain \(\{O_k\}_{k \ge 1}\) is given by

   \[\begin{align*} \tilde P &= P_O + S(I - Q)^{-1} R \\ &= \MATRIX{ 0 & \tfrac{1}{4} & 0 \\ \tfrac{3}{4} & 0 & \tfrac{1}{4} \\ 0 & 1 & 0 } + \MATRIX{ 0 & \tfrac{3}{4} \\ 0 & 0 \\ 0 & 0 } \MATRIX{ 1 & -1 \\ -\tfrac{3}{4} & 1 }^{-1} \MATRIX{ 0 & 0 & 0 \\ \tfrac{1}{4} & 0 & 0 } \\ &= \MATRIX{ \tfrac{3}{4} & \tfrac{1}{4} & 0 \\ \tfrac{3}{4} & 0 & \tfrac{1}{4} \\ 0 & 1 & 0 }. \end{align*}\]

   This intuitively makes sense. The chain \(\{X_n\}_{n \ge 1}\) can only go to unobserved states at state \(X_n = 0\). When it does to go \(\ALPHABET O^c\), the first observed state it visits must be \(0\). Then \(\tilde P_{00} = P_{0,-1} = \frac 34\). The rest of the entries of \(\tilde P\) are the same as \(P\).

   The invariant distribution of \(\tilde P\) is \[\MATRIX{ \tfrac{12}{17} & \tfrac{4}{17} & \tfrac{1}{17} }\] while the invariant distribution of \(P\) is \[\MATRIX{ \tfrac{27}{80} & \tfrac{36}{80} & \tfrac{12}{80} & \tfrac{4}{80} & \tfrac{1}{80} }.\]

   Observe that if we take the last three elements of the latter and normalize it, we get the former.

Exercises

Exercise 11.1 (Time reversal of Markov chains) Let \(\{X_n\}_{n \ge 0}\) be a Markov chain. Show that for any \(N > n\), \[ \PR(X_n = x_n \mid X_{n+1:N} = x_{n+1:N}) = \PR(X_n = x_n \mid X_{n+1} = x_{n+1}). \] Thus, a time-reversed Markov chain is also Markov. Explain why the reverse transition probabilities may depend on time even when the forward chain is time-homogeneous.

Exercise 11.2 Suppose \(\{X_n\}_{n \ge 0}\) is a Markov chain with transition matrix \(P\). For a fixed positive integer \(k\), define \(Y_n = X_{kn}\). Show that \(\{Y_n\}_{n \ge 0}\) is a Markov chain with transition matrix \(P^k\).

Exercise 11.3 Suppose a (6-sided) die is ‘fixed’ so that two consecutive rolls cannot have the same outcome. In particular, if the outcome of a roll is \(i\), then the next roll cannot be \(i\); all \(5\) other outcomes are equally likely.

1. Model the above as a Markov chain.
2. If the outcome of the first roll is \(1\), what is the probability that the outcome of the \(n\)th roll is also \(1\)?

Further Reading

1. Gubner, Chapter 12.

2. Grinstead and Snell, Introduction to Probability, Chapter 11 has an excellent treatment of finite Markov chains. Has interesting exercises.

3. Kemeny and Snell, Finite Markov Chains, Chapter 2–4.

4. Kemeny, Snell, and Knapp, Denumerable Markov Chains, a slightly advanced version of the previous book.

5. Doyle and Snell, Random Walks and Electrical Networks shows a facinating relationship between random walks and circuits!

6. Weber’s notes on Markov chains

References