Markov Chain

Most of our study of probability has dealt with independent trials processes, in which we have i.i.d. random variables $X_{i}$ . This is useful for modeling and sampling situations. But when study random dynamical systems, they are less useful. In these cases, $X_{i}$ are no longer independent because they are all part of the system, and they have to interact with each other. So one way to modeling this is to use conditional probability.

Markov chains: basic definitions

Consider a countable sequence $X_{1}, X_{2}, \dots, X_{n}, \dots$ which

the subscript represents time, thus we have discrete time sequence;
each $X_{i}$ has finite outcomes.

In other words, each $X_{i}$ is a discrete random variable that takes one of $N$ possible values, where $N = card (S)$ and $S$ is the outcome space; it may be the case that $N = \infty$ .

Definition. The process $X$ is a Markov chain if it satisfies the Markov condition: $P (X_{n} = s | X_{1} = x_{1}, X_{2} = x_{2}, \dots, X_{n - 1} = x_{n - 1}) = P (X_{n} = s | X_{n - 1} = x_{n - 1})$ for all $n \geq 1$ ans all $s, x_{1}, \dots, x_{n - 1} \in S$ .

Since $S$ is assumed countable, it can be put in one-to-one correspondence with some subset $S^{'}$ of the integers, and without loss of generality we can assume that $S$ is this set $S^{'}$ of integers. Then the evolution of a chain is described by its transition probabilities $\begin{matrix} (7-1) & P (X_{n} = j | X_{n - 1} = i) := p_{i j} (n - 1) . \end{matrix}$

Theorem. The transition matrix $P$ is a **stochastic matrix**, which is to say that:

$P$ has non-negative entries, or $p_{i j} \geq 0$ for all $i, j$ ,
$P$ has row sums equal to one, or $\sum_{j} p_{i j} = 1$ for all $i$ .

%Note that the Markov property is equivalent to the following stipulation, which is also called $k$ -step transition probabilities.

Definition. The ** $k$ -step transition probabilities** is defined as $\begin{matrix} (7-2) & P (X_{n + k - 1} = j | X_{n - 1} = i) := p_{i j}^{(k)} (n - 1) for any n, k \geq 1. \end{matrix}$

%Based on this, we can define

Definition. The **transition matrix** $P (n - 1) = (p_{i j} (n - 1))$ is the $| S | \times | S |$ matrix of **transition probabilities** $p_{i j} (n - 1)$ . The ** $k$ -step transition matrix** $P^{(k)} (n - 1) = (p_{i j}^{(k)} (n - 1))$ is the matrix of ** $k$ -step transition probabilities** $p_{i j}^{(k)} (n - 1)$ .

Remark. We can check that the Markov property is equivalent to each of the following two stipulations: for each $s \in S$ and for every sequence ${x_{i} | i \geq 0}$ in $S$ , $\begin{matrix} (7-3a) & \begin{array}{r} P (X_{n + 1} = s | X_{n_{1}} = x_{n_{1}}, X_{n_{2}} = x_{n_{2}}, X_{n_{k}} = x_{n_{k}}) = P (X_{n + 1} = s | X_{n_{k}} = x_{n_{k}}) \\ for all n_{1} < n_{2} < \dots < n_{k} \leq n . \end{array} \end{matrix}$ $\begin{matrix} (7-3b) & \begin{array}{r} P (X_{m + n} = s | X_{0} = x_{0}, X_{1} = x_{1}, \dots, X_{m} = x_{m}) = P (X_{m + n} = s | X_{m} = x_{m}) \\ for any m, n \geq 0. \end{array} \end{matrix}$

Next we introduce another assumption:

Definition. The chain $X$ is called **homogeneous** if $P (X_{n} = j | X_{n - 1} = i) = P (X_{2} = j | X_{1} = i), for all n, i, j .$

Remark. Note the following two remarks.

Markov property and homogeneity property are **independent**. There are also Markov chains which are not homogeneous.
If a Markov chain $X$ is homogeneous, then $p_{i j} (n - 1)$ doesn't depends on the time $(n - 1)$ , i.e., the probability transition matrix $P$ is **fixed** at each step.

Properties of Markov chains

By the assumption of homogeneity, we know $P (n - 1) = P$ . That $P^{(k)} (n - 1)$ doesn’t depend on $(n - 1)$ is a consequence of the following important fact.

Theorem. [Chapman-Kolmogorov equations] $p_{i j}^{(n + r)} (m) = \sum_{k} p_{i k}^{(n)} (m) p_{k j}^{(r)} (m + n) .$ Therefore, $P^{(n + r)} (m) = P^{(n)} (m) P^{(r)} (m + n) .$ Furthermore, if we have homogeneity, then $P^{n} (m) = P^{n},$ the $n$ th power of $P$ .

Proof ▸

$\begin{aligned} p_{i j}^{n + r} (m) & = P (X_{m + n + r} = j | X_{m} = i) \\ = \sum_{k} P (X_{m + n + r} = j, X_{m + n} = k | X_{m} = i) \\ = \sum_{k} P (X_{m + n + r} = j | X_{m + n} = k, X_{m} = i) P (X_{m + n} = k | X_{m} = i) (marginalization) \\ = \sum_{k} P (X_{m + n + r} = j | X_{m + n} = k) P (X_{m + n} = k | X_{m} = i) (Markov property) \\ = \sum_{k} p_{k j}^{(r)} (m + n) p_{i k}^{(n)} (m) . \end{aligned}$ The marginalization step uses the fact that $P (A \cap B | C) = P (A | B \cap C) P (B | C) .$ The Markov property step uses $(7-3a)$ . The $n$ th power is obtained by iteration. ◼

One consequence of the preceding theorem is that $P^{(n)} (m) = P^{(n)} (0)$ . Note that this consequence is obtained with homogeneous assumption. We write $P_{n}$ for $P^{(n)} (m)$ and $p_{i j} (n)$ for $p_{i j}^{(n)} (m)$ . This theorem relates long-term development to short-term development, and tells us how $X_{n}$ depends on the initial variable $X_{0}$ . Let $μ_{i}^{(n)} = P (X_{n} = i)$ be the mass function of $X_{n}$ , and write $μ^{(n)}$ for the row vector with entries $(μ_{i}^{(n)} : i \in S)$ . Then we have the following lemma.

Lemma. $μ^{(m + n)} = μ^{(m)} P_{n}$ , and hence $μ^{(n)} = μ^{(0)} P^{n}$ .

Proof ▸

We have that $\begin{aligned} μ_{j}^{(m + n)} & = P (X_{m + n} = j) \\ = \sum_{i} P (X_{m + n} = j | X_{m} = i) P (X_{m} = i) \\ = \sum_{i} μ_{i}^{(m)} p_{i j} (n) \\ = (μ^{(m)} P_{n})_{j} \end{aligned}$ and the result follows from the preceding theorem. ◼

The random evolution of the chain is determined by the transition matrix $P$ and the initial mass function $μ^{(0)}$ .

Absorbing Markov chains

An absorbing Markov chain is a special type of Markov chains.

Definition. A state $s_{i}$ of a Markov chain is called **absorbing** if it is impossible to leave it (i.e., $p_{i i} = 1$ ). A Markov chain is **absorbing** if it has at least one absorbing state, and if from every state it is possible to go to an absorbing state (not necessarily in one step).

Definition. In an absorbing Markov chain, a state which is not absorbing is called **transient**.

Canonical form of absorbing Markov chains

Consider an arbitrary absorbing Markov chain. Renumber the states so that the transient states come first. If there are $r$ absorbing states and $t$ transient states, the transition matrix will have the following canonical form $\begin{equation} P = \begin{blockarray}{rcc} & TR. & ABS. \begin{block}{r[cc]} TR. & Q & R ABS. & 0 & I \end{block} \end{blockarray} \end{equation}$ Here $I$ is an $r \times r$ identity matrix, $0$ is an $r \times t$ zero matrix, $R$ is a nonzero $t \times r$ matrix, and $Q$ is an $t \times t$ matrix. The first $t$ states are transient and the last $r$ states are absorbing.

A standard matrix algebra argument shows that $P^{n}$ is of the form $\begin{equation} P^n = \begin{blockarray}{rcc} & TR. & ABS. \begin{block}{r[cc]} TR. & Q^n & * ABS. & 0 & I \end{block} \end{blockarray} \end{equation}$ where the asterisk $*$ stands for the $t \times r$ matrix in the upper right-hand corner of $P^{n}$ .

The entries of $Q_{n}$ give the probabilities for being in each of the transient states after $n$ steps for each possible transient starting state. The following theorem will show that every entry of $Q_{n}$ will approach zero as $n$ approaches infinity (i.e., $Q_{n} \to 0$ ).

Theorem. In an absorbing Markov chain, the probability that the process will be absorbed is 1 (i.e., $Q_{n} \to 0$ as $n \to \infty$ ).

Proof ▸

From each non-absorbing state $s_{j}$ it is possible to reach an absorbing state. Let $m_{j}$ be the minimum number of steps required to reach an absorbing state, starting from $s_{j}$ . Let $p_{j}$ be the probability that, starting from $s_{j}$ , the process will not reach an absorbing state in $m_{j}$ steps. Then $p_{j} < 1$ . Let $m$ be the largest of the $m_{j}$ and let $p$ be the largest of $p_{j}$ . The probability of not being absorbed in $m$ steps is less than or equal to $p$ , in $2 m$ steps less than or equal to $p^{2}$ , etc. Since $p < 1$ , these probabilities tend to 0. Since the probability of not being absorbed in $n$ steps is monotone decreasing, these probabilities also tend to 0, hence $lim_{n \to \infty} Q_{n} = 0$ . ◼

The fundamental matrix

Definition. For an absorbing Markov chain $P$ , the matrix $N = (I - Q)^{- 1}$ is called the **fundamental matrix** for $P$ . The entry $n_{i j}$ of $N$ gives the expected number of times that the process is in the transient state $s_{j}$ if it is started in the transient state $s_{i}$ .

Theorem. For an absorbing Markov chain the matrix $I - Q$ has an inverse $N$ and $N = I + Q + Q^{2} + \dots$ . The $i j$ -entry $n_{i j}$ of the matrix $N$ is the expected number of times the chain is in state $s_{j}$ , given that it starts in state $s_{i}$ . The initial state is counted if $i = j$ .

Proof ▸

Let $(I - Q) x = 0$ ; that is $x = Q x$ . Then, iterating this we see that $x = Q^{n} x$ . Since $Q_{n} \to 0$ , we have $Q_{n} x \to 0$ , so $x = 0$ . Thus $(I - Q)^{- 1} = N$ exists. Note next that $(I - Q) (I + Q + Q^{2} + \dots + Q^{n}) = I - Q^{n + 1} .$ Thus multiplying both sides by $N$ gives $I + Q + Q^{2} + \dots + Q^{n} = N (I - Q^{n + 1}) .$ Letting $n$ tend to infinity we have $N = I + Q + Q^{2} + \dots .$ Let $s_{i}$ and $s_{j}$ be two transient states, and assume throughout the remainder of the proof that $i$ and $j$ are fixed. Let $X^{(k)}$ be a random variable which equals 1 if the chain is in state $s_{j}$ after $k$ steps, and equals 0 otherwise. For each $k$ , this random variable depends upon both $i$ and $j$ ; we choose not to explicitly show this dependence in the interest of clarity. We have $P (X^{(k)} = 1) = q_{i j}^{(k)},$ and $P (X^{(k)} = 0) = 1 - q_{i j}^{(k)},$ where $q_{i j}^{(k)}$ is the $i j$ th entry of $Q^{k}$ . These equations hold for $k = 0$ since $Q^{0} = I$ . Therefore, since $X^{(k)}$ is a 0-1 random variable, $E (X^{(k)}) = q_{i j}^{(k)}$ . The expected number of times the chain is in state $s_{j}$ in the first $n$ steps, given that it starts in state $s_{i}$ , is clearly $E (X^{(0)} + X^{(1)} + \dots + X^{(n)}) = q_{i j}^{(0)} + q_{i j}^{(1)} + \dots + q_{i j}^{(n)} .$ Letting $n$ tend to infinity we have $E (X^{(0)} + X^{(1)} + \dots) = q_{i j}^{(0)} + q_{i j}^{(1)} + \dots = n_{i j} .$ ◼

Time to absorption

Given that the chain starts in state $s_{i}$ , what is the expected number of steps before the chain is absorbed? The following theorem gives the answer.

Theorem. Let $t_{i}$ be the expected number of steps before the chain is absorbed, given that the chain starts in state $s_{i}$ , and let $t$ be the **column vector** whose $i$ th entry is $t_{i}$ . Then $t = N 1$ where $1$ is a column vector all of whose entries are 1.

Proof ▸

If we add all the entries in the $i$ th row of $N$ , we will have the expected number of times in any of the transient states for a given starting state $s_{i}$ , that is, the expected time required before being absorbed. Thus, $t_{i}$ is the sum of the entries in the $i$ th row of $N$ . If we write this statement in matrix form, we obtain the theorem. \end{proof}◼

Absorption probabilities

Theorem. Let $b_{i j}$ be the probability that an absorbing chain will be absorbed in the absorbing state $s_{j}$ if it starts in the transient state $s_{i}$ . Let $B$ be the matrix with entries $b_{i j}$ . Then $B$ is an $t \times r$ matrix, and $B = N R,$ where $N$ is the fundamental matrix and $R$ is as in the canonical form.

Proof ▸

We have $\begin{aligned} B_{i j} & = \sum_{n} \sum_{k} q_{i k}^{(n)} r_{k j} \\ = \sum_{k} \sum_{n} q_{i k}^{(n)} r_{k j} \\ = \sum_{k} n_{i k} r_{k j} \\ = (N R)_{i j} . \end{aligned}$ This completes the proof. ◼