8.3 Markov chains

So far we have mostly studied sequences of independent trials (binomial, Poisson, geometric, and so on). Consider an experiment with a finite or countable set of outcomes which is repeated, and let \(X_n\) denote the outcome of the \(n\)th trial. Let \(\{0, 1, 2, \dots , m\}\) be the possible values of \(X_n\). We interpret \(X_n\) as the state of some system at time \(n\), and say that the system is in state \(i\) at time \(n\) if \(X_n = i\).

Definition 8.3.1. The sequence \(\{X_n : n \ge 0\}\) is a Markov chain if, each time the system is in state \(i\), there is a fixed probability \(P_{ij}\) that it will next be in state \(j\) (at time \(n + 1\)), whatever happened before: \begin {align*} &P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots , X_1 = i_1, X_0 = i_0) \\ &\qquad = P(X_{n+1} = j \mid X_n = i) = P_{ij} . \end {align*}

Remark.

(i): The conditional probabilities \(P_{ij} = P(X_{n+1} = j \mid X_n = i)\) are called the transition probabilities of the chain.
(ii): The transition probabilities are stationary: \(P(X_{n+1} = j \mid X_n = i) = P_{ij}\) does not depend on \(n\).
(iii): The first equality in the definition is the Markov property: given the present state, the past states have no further influence on the future. To say that \(\{X_n\}\) is a Markov chain is to say that it has the Markov property and stationary transition probabilities.
(iv): Markov chains have a rich theory, and a large number of systems arising in practice can be modelled by them.

If the possible states are \(0, 1, 2, \dots , m\), then \[ P_{ij} \ge 0 \qquad \text {and}\qquad \sum _{j=0}^mP_{ij} = 1 \quad \text {for each } i . \] It is convenient to arrange the transition probabilities in a square matrix, the transition probability matrix \[ P = \begin {bmatrix} P_{00} & P_{01} & \cdots & P_{0m} \\ P_{10} & P_{11} & \cdots & P_{1m} \\ \vdots & \vdots & \ddots & \vdots \\ P_{m0} & P_{m1} & \cdots & P_{mm} \end {bmatrix} , \] each of whose rows sums to \(1\). By the multiplication rule and the Markov property, the joint probability mass function of \(X_0, X_1, \dots , X_n\) is \begin {align*} &P(X_n = i_n, X_{n-1} = i_{n-1}, \dots , X_0 = i_0) \\ &\quad = P(X_n = i_n \mid X_{n-1} = i_{n-1}, \dots , X_0 = i_0)\,P(X_{n-1} = i_{n-1}, \dots , X_0 = i_0) \\ &\quad = P(X_n = i_n \mid X_{n-1} = i_{n-1})\,P(X_{n-1} = i_{n-1}, \dots , X_0 = i_0) \\ &\quad = \cdots = P_{i_{n-1}i_n}P_{i_{n-2}i_{n-1}}\cdots P_{i_0i_1}\,P(X_0 = i_0) . \end {align*}

Example 8.3.2 (Gambler’s ruin). A gambler at each play of a game either wins \(1\) unit with probability \(p\) or loses \(1\) unit with probability \(1 - p\). The gambler stops playing when the fortune reaches either \(0\) or \(m\). The gambler’s sequence of fortunes is then a Markov chain with transition probabilities \begin {gather*} P_{i,i+1} = p , \qquad P_{i,i-1} = 1 - p , \qquad i = 1, 2, \dots , m - 1 ; \\ P_{00} = P_{mm} = 1 . \end {gather*} For \(m = 6\) the transition matrix is \[ P = \begin {bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1-p & 0 & p & 0 & 0 & 0 & 0 \\ 0 & 1-p & 0 & p & 0 & 0 & 0 \\ 0 & 0 & 1-p & 0 & p & 0 & 0 \\ 0 & 0 & 0 & 1-p & 0 & p & 0 \\ 0 & 0 & 0 & 0 & 1-p & 0 & p \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end {bmatrix} . \]

The two-step transition probability \(P^{(2)}_{ij} = P(X_{n+2} = j \mid X_n = i)\) is the probability that a system in state \(i\) will be in state \(j\) after two transitions. Conditioning on the intermediate state and using the Markov property, \begin {align*} P^{(2)}_{ij} &= P(X_2 = j \mid X_0 = i) \\ &= \sum _{k=0}^mP(X_2 = j \mid X_1 = k, X_0 = i)\,P(X_1 = k \mid X_0 = i) \\ &= \sum _{k=0}^mP(X_2 = j \mid X_1 = k)\,P(X_1 = k \mid X_0 = i) = \sum _{k=0}^mP_{ik}P_{kj} , \end {align*}

which is the \((i, j)\) entry of the matrix \(P^2\). In the gambler’s ruin chain of Example 8.3.2, \[ P^{(2)}_{35} = \sum _{k=0}^6P_{3k}P_{k5} = P_{34}P_{45} = p^2 , \qquad P^{(2)}_{34} = \sum _{k=0}^6P_{3k}P_{k4} = 0 , \] the second because a fortune of \(3\) cannot become \(4\) in exactly two plays. In general the \(n\)-step transition probabilities are \[ P^{(n)}_{ij} = P(X_{n+l} = j \mid X_l = i) = P(X_n = j \mid X_0 = i) . \]

Theorem 8.3.3 (The Chapman–Kolmogorov equations). For \(0 < r < n\), \[ P^{(n)}_{ij} = \sum _{k=0}^mP^{(r)}_{ik}P^{(n-r)}_{kj} . \]

Proof. Conditioning on the state at time \(r\) and using the Markov property, \begin {align*} P^{(n)}_{ij} &= P(X_n = j \mid X_0 = i) \\ &= \sum _{k=0}^mP(X_n = j \mid X_r = k, X_0 = i)\,P(X_r = k \mid X_0 = i) \\ &= \sum _{k=0}^mP(X_n = j \mid X_r = k)\,P(X_r = k \mid X_0 = i) = \sum _{k=0}^mP^{(r)}_{ik}P^{(n-r)}_{kj} . \end {align*} □

Example 8.3.4 (Random walk). A particle moves along a one-dimensional axis. At each point in time it moves one step to the right with probability \(p\) or one step to the left with probability \(1 - p\). Its position is a Markov chain with transition probabilities \[ P_{i,i+1} = p , \qquad P_{i,i-1} = 1 - p , \qquad i = 0, \pm 1, \pm 2, \dots \] To move from state \(i\) to state \(j\) in \(n\) transitions, the particle must take \((n - i + j)/2\) steps to the right and \(n - (n - i + j)/2 = (n + i - j)/2\) steps to the left. Hence \[ P^{(n)}_{ij} = \binom {n}{\frac {n-i+j}{2}}p^{\frac {n-i+j}{2}}(1 - p)^{\frac {n+i-j}{2}} , \qquad (*) \] where \(\binom nx = 0\) if \(x\) is not a non-negative integer less than or equal to \(n\). Separating even and odd numbers of steps, \((*)\) can be written as \begin {align*} P^{(2n)}_{i,i+2k} &= \binom {2n}{n+k}p^{n+k}(1 - p)^{n-k} , && k = 0, \pm 1, \dots , \pm n , \\ P^{(2n+1)}_{i,i+2k+1} &= \binom {2n+1}{n+k+1}p^{n+k+1}(1 - p)^{n-k} , && k = -n - 1, -n, \dots , n . \end {align*}

The distribution of \(X_n\) follows from the \(n\)-step transition probabilities and the distribution of \(X_0\): \[ P(X_n = j) = \sum _iP(X_n = j \mid X_0 = i)\,P(X_0 = i) = \sum _iP^{(n)}_{ij}P(X_0 = i) . \]

Remark. For many chains \(P^{(n)}_{ij}\) converges, as \(n \to \infty \), to a value \(\pi _j\) that depends only on \(j\). That is, for large \(n\) the probability of being in state \(j\) after \(n\) transitions is approximately \(\pi _j\), whatever the initial state. It can be shown that, for a chain with states \(0, 1, \dots , m\), a sufficient condition for this is that for some \(n > 0\) \[ P^{(n)}_{ij} > 0 \qquad \text {for all } i, j = 0, 1, \dots , m . \qquad (**) \] A chain satisfying \((**)\) is called ergodic. The random walk above is not: a particle can return to its starting point only after an even number of steps.

Remark (Transition functions and initial distributions). Let \(\{X_n : n \ge 0\}\) be a Markov chain with state space \(\mathbf E\).

(i): The function \(P_{ij} = P(X_1 = j \mid X_0 = i)\), \(i, j \in \mathbf E\), is called the transition function of the chain. It satisfies \(P_{ij} \ge 0\) and \(\sum _{j\in \mathbf E}P_{ij} = 1\).
(ii): The function \(\pi _0(i) = P(X_0 = i)\) is called the initial distribution. It satisfies \(\pi _0(i) \ge 0\) and \(\sum _{i\in \mathbf E}\pi _0(i) = 1\).
(iii): It can be shown that, given any transition function and any initial distribution, there is a probability space and random variables \(X_n\), \(n \ge 0\), defined on it such that \[ P(X_n = i_n, \dots , X_1 = i_1, X_0 = i_0) = P_{i_{n-1}i_n}\cdots P_{i_1i_2}P_{i_0i_1}\pi _0(i_0) . \]

We write \(P_i(\cdot ) = P(\cdot \mid X_0 = i)\) for probabilities for the chain started in state \(i\).

Definition 8.3.5. The hitting time \(T_j\) of state \(j\) is \[ T_j = \min \{n \ge 1 : X_n = j\} \] if \(X_n = j\) for some \(n \ge 1\), and \(T_j = \infty \) if \(X_n \ne j\) for all \(n \ge 1\). It is the first positive time at which the chain is in (hits) state \(j\).

Result 8.3.6. For \(n \ge 1\), with \(P^{(0)}_{jj} = 1\), \[ P^{(n)}_{ij} = \sum _{m=1}^nP_i(T_j = m)\,P^{(n-m)}_{jj} . \]

Proof. If \(X_n = j\), the chain has hit \(j\) for the first time at some time \(m\) with \(1 \le m \le n\), so the event \(\{X_n = j\}\) is the union of the disjoint events \(\{T_j = m, X_n = j\}\), \(1 \le m \le n\). Since \(\{T_j = m\} = \{X_1 \ne j, \dots , X_{m-1} \ne j, X_m = j\}\) fixes the state at time \(m\) as \(j\), the Markov property gives \begin {align*} P^{(n)}_{ij} &= P_i(X_n = j) \\ &= \sum _{m=1}^nP_i(T_j = m)\,P(X_n = j \mid X_0 = i, T_j = m) \\ &= \sum _{m=1}^nP_i(T_j = m)\,P(X_n = j \mid X_m = j) \\ &= \sum _{m=1}^nP_i(T_j = m)\,P^{(n-m)}_{jj} . \end {align*} □

[next] [prev] [prev-tail] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.