Markov Chain 2

Irreducible Markov chains and regular Markov chains

Definition. A Markov chain is called an **irreducible chain** if it is possible to go from every state to every state (not necessarily in one move).

Remark. Note that absorbing chains are NOT irreducible chains.

Definition. A Markov chain is called a **regular chain** if some power of the transition matrix has only positive elements.

Remark. Note that regular chains are irreducible chains. But the converse is NOT true as the following example shows.

Example. Let the transition matrix of a Markov chain be defined by $P = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] .$ If we start from state 1, then next step we jump to state 2. If we start from state 2, then we jump to state 1. In other words, we are flipping between two states after each step. So the chain is irreducible. But $P^{2 n} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}], P^{2 n + 1} = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] .$ So the chain is not regular.

Remark. Any transition matrix that has no zeros determines a regular Markov chain. However, it is possible for a regular Markov chain to have a transition matrix that has zeros.

We shall discuss two important theorems relating to regular chains. But before, we will use the following two lemmas.

Lemma. \label{lemma:8.1} Suppose $X$ is a random variable with finite number of outcomes, with the greatest being $x_{m a x}$ and the least being $x_{m i n}$ . Then we have $E (X) \leq x_{m a x}, E (X) \geq x_{m i n} .$

Proof ▸

Assume $X$ has $n$ outcomes, and let $f (x_{i}) = P (X = x_{i})$ , then we have $\begin{matrix} E (X) = \sum_{i = 1}^{n} x_{i} f (x_{i}) \geq \sum_{i = 1}^{n} x_{m i n} f (x_{i}) = x_{m i n}, \\ E (X) = \sum_{i = 1}^{n} x_{i} f (x_{i}) \leq \sum_{i = 1}^{n} x_{m a x} f (x_{i}) = x_{m a x} . \end{matrix}$ ◼

Lemma. \label{lemma:8.2} Suppose a transition matrix $P$ only has positive entries and the smallest entry is $d > 0$ . Consider a vector $y$ . Denote its maximum value as $M_{0}$ and its minimum value as $m_{0}$ . Now consider the product $P y$ . Denote its maximum value as $M_{1}$ and its minimum value as $m_{1}$ . Then we have $M_{1} - m_{1} \leq (1 - 2 d) (M_{0} - m_{0}) .$

Proof ▸

Note that $P$ is a transition matrix. So each row of $P$ sums up to $1$ . From lemma $???$ , we note that each entry in the vector $P y$ is a weighted average of the entries in $y$ , therefore, we have $\begin{matrix} (8-1) & M_{1} \leq M_{0}, m_{1} \geq m_{0} . \end{matrix}$ The largest weighted average that could be obtained in the present case would occur if all but one of the entries of $y$ have value $M_{0}$ and one entry has value $m_{0}$ , and this one small entry is weightedby the smallest possible weight, namely $d$ . In this case, the weighted average would equal $m_{0} d + M_{0} (1 - d)$ . % $\begin{equation} % m_0 d + M_0(1-d). %\end{equation}$ Similarly, the smallest possible weighted average equals $M_{0} d + m_{0} (1 - d)$ . % $\begin{equation} % M_0 d + m_0(1-d). %\end{equation}$ Therefore, we have %Since $(8-1)$ is true for any $y$ , we can take some particular form of $y$ to find the best and worst outcome of $P y$ . First let $y = [\begin{matrix} M_{0} & \dots & m_{0} & \dots & M_{0} \end{matrix}]$ such that $y$ only one entry being $m_{0}$ and such entry captures the minimum entry $d$ of $P$ . Then we can show that $\begin{matrix} (8-2) & M_{1} \leq m_{0} d + M_{0} (1 - d), \end{matrix}$ %Similarly, by letting $y = [\begin{matrix} m_{0} & \dots & M_{0} & \dots & m_{0} \end{matrix}]$ such that $y$ only one entry being $M_{0}$ and such entry captures the minimum entry $d$ of $P$ , we can obtain $\begin{matrix} (8-3) & m_{1} \geq M_{0} d + m_{0} (1 - d) . \end{matrix}$ $(8-2)$ - $(8-3)$ yields $M_{1} - m_{1} \leq (1 - 2 d) (M_{0} - m_{0}) .$ ◼

Now we give two important theorems.

Theorem. [Fundamental limit theorem for regular chains] \label{thm:8.1} Let $P$ be the transition matrix for a regular chain. Then, as $n \to \infty$ , the powers $P^{n}$ approach a limiting matrix $W$ with all rows the **same** vector $w$ . The vector $w$ is a strictly positive probability vector (i.e.., the components are all **positive** and they sum to one).

Proof ▸

We consider an arbitrary vector $y$ , and denote the maximum entry of $P^{n} y$ as $M_{n}$ and the minimum entry of $P^{n} y$ as $m_{n}$ . From lemma 1, we must have $M_{n} \leq M_{n - 1}, m_{n} \geq m_{n + 1} .$ Writing all these inequality from 1 to $n$ gives $M_{0} \geq M_{1} \geq \dots \geq M_{n} \geq m_{n} \geq \dots \geq m_{1} \geq m_{0} .$ Therefore ${M_{n}}$ is a decreasing sequence bounded below and ${m_{n}}$ is an increasing sequence bounded above. From sequence theory we know that ${M_{n}}$ and ${m_{n}}$ must converge. Let $M = lim_{n \to \infty} M_{n}, m = lim_{n \to \infty} m_{n} .$ From Lemma $???$ we have $\begin{matrix} (8-4) & M_{n} - m_{n} \leq (1 - 2 d)^{n} (M_{0} - m_{0}) . \end{matrix}$ On the other hand, since $d$ is the minimum entry of $P$ , we must have $0 < d \leq \frac{1}{2}$ , which gives $0 \leq 1 - 2 d < 1$ . Thus from $(8-4)$ we have $\begin{matrix} (8-5) & lim_{n \to \infty} (M_{n} - m_{n}) = 0 \Rightarrow M = m \forall y . \end{matrix}$ We choose a particular form of $y$ such that $y = e_{j}$ with $j$ th entry being 1 and others being 0. Then $P^{n} y$ gives the $j$ th column of $P^{n}$ . Using $(8-5)$ , we have $lim_{n \to \infty} P^{n} y = α 1 for some α > 0,$ which shows the $j$ th column has the same entries. Thus, by letting $y = e_{j}$ , $1 \leq j \leq n$ , we conclude that each column of $P^{n}$ has the same entries. This finishes the proof. ◼

The $i j$ th entry of $P^{n}$ , $p_{i j}^{(n)}$ , is the probability that the process will be in state $s_{j}$ after $n$ steps if it starts in state $s_{i}$ . If we denote the common row of $W$ by $w$ , then Theorem $???$ states that the probability of being in $s_{j}$ in the long run is approximately $w_{j}$ , the $j$ th entry of $w$ , and is independent of the starting state.

Theorem. \label{thm:8.2} Let $P$ be a regular transition matrix, let $W = lim_{n \to \infty} P^{n},$ and let $w$ be the common row of $W$ . Then

$w P = w$ , which means $w$ is a left eigenvector of $P$ with eigenvalue 1, and any row vector $v$ such that $v P = v$ is a constant multiple of $w$ .
$P 1 = 1$ , which means $1$ is an eigenvector of $P$ with eigenvalue 1, and any column vector $x$ such that $P x = x$ is a multiple of $1$ .

Proof ▸

To prove part (a), we note that from Theorem $???$ , $lim_{n \to \infty} P^{n} = W .$ Thus $lim_{n \to \infty} P^{n + 1} = P^{n} P = W P .$ But $lim_{n \to \infty} P^{n + 1} = W$ , and so $W = W P$ and $w = w P$ . Let $v$ be any vector with $v P = v$ . Then $v = v P^{n}$ , and passing to the limit, $v = v W$ . Let $r$ be the sum of the components of $v$ , i.e., $r = \sum_{i = 1}^{n} v_{i}$ . Then it is easily checked that $v W = r w$ . So, $v = r w$ . To prove part (b), assume that $x = P x$ . Then $x = P^{n} x$ , and again passing to the limit, $x = W x$ . Since all rows of $W$ are the same, the components of $W x$ are all equal, so $x$ is a multiple of $1$ . ◼

Note that an immediate consequence of Theorem $???$ is the fact that there is only one probability vector $v$ such that $v P = v$ , which is $v = w$ . The probability vector $v$ is the vector such that $\sum_{i = 1}^{n} = 1$ .

Remark. Computing $W$ is equivalent to computing the left eigenvector of $P$ with eigenvalue 1. It is equivalent to compute the right eigenvector of $P^{T}$ with eigenvalue 1.

Example. Let $P$ be a transition matrix such that $P = [\begin{matrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{4} & \frac{3}{4} \end{matrix}] .$ Compute $W = lim_{n \to \infty} P^{n}$ . This is equivalent to compute $P^{T} x = x$ . Note that $x$ is a probability vector, so $1^{T} x = 1$ . $P^{T} x = x \Rightarrow {\begin{cases} \frac{1}{2} x_{1} + \frac{1}{4} x_{2} = x_{1} \\ x_{1} + x_{2} = 1 \end{cases} \Rightarrow {\begin{cases} x_{1} = \frac{1}{3} \\ x_{2} = \frac{2}{3} \end{cases}$ Therefore $w = [\frac{1}{3} \frac{2}{3}]$ , and $W = [\begin{matrix} w \\ w \end{matrix}] = [\begin{matrix} \frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{2}{3} \end{matrix}]$ .

Fixed vectors

Definition. A row vector $w$ with the property $w P = w$ is called a **fixed row vector** for $P$ . Similarly, a column vector $x$ such that $P x = x$ is called a **fixed column vector** for $P$ .

Thus, the common row of $W$ is the unique vector $w$ which is both a fixed row vector for $P$ and a probability vector. Theorem $???$ shows that any fixed row vector for $P$ is a multiple of $w$ and any fixed column vector for $P$ is a constant vector. One can also state the above definition in terms of eigenvalues and eigenvectors. A fixed row vector is a left eigenvector of the matrix $P$ corresponding to the eigenvalue 1. A similar statement can be made about fixed column vectors.

The following theorem generalizes Theorem $???$ to the case where the starting state is itself determined by a probability vector.

Theorem 8.3. Let $P$ be the transition matrix for a regular chain and $v$ an arbitrary probability vector. Then $lim_{n \to \infty} v P^{n} = w,$ where $w$ is the unique fixed probability vector for $P$ .

Proof ▸

By Theorem $???$ , $lim_{n \to \infty} P^{n} = W .$ Hence $lim_{n \to \infty} v P^{n} = v W .$ But the entries in $v$ sum to 1, and each row of $W$ equals $w$ . From these statements, it is easy to check that $v W = w .$ ◼

Remark. If we start a Markov chain with initial probabilities given by $v$ , then the probability vector $v P^{n}$ gives the probabilities of being in the various states after $n$ steps. Theorem $???$ then establishes the fact that, even in this more general class of processes, the probability of being in $s_{j}$ approaches $w_{j}$ .

Remark. Theorem 8.3 tells that regular chains always equilibriate to $w$ .

Does the result holds for irreducible chains?

NOT true for irreducible chains. The following is a counterexample.

Example. Let $P = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] .$ If we calculate the left eigenvector, we can obtain $w = [\begin{matrix} \frac{1}{2} & \frac{1}{2} \end{matrix}] .$ But if we start from $(1, 0)$ or $(0, 1)$ , we will never goes to this equilibrium.

Definition. The period $d (i)$ of a state $i$ is defined by $d (i) = gcd {n : P_{i i} (n) > 0}$ , the greatest common divisor of the epochs at which return is possible. We call state $i$ periodic if $d (i) > 1$ and aperiodic if $d (i) = 1$ .

Remark. Aperiodic + irreducible $\Leftrightarrow$ regular for finite outcome Markov chains.