From BoykinWiki

EEL6507 Spring 2009, Lecture 04, Wednesday 2009/01/09 (Notes created by Robert Karwacki)

Described the discrete Markov chain
Introduced terms to describe Markov chains
Described solving for the equilibrium solution of a Markov chain

Example of an Inhomogeneous Markov Chain

Imagine a system that possesses the Markovian Property and having two possible states, 0 and 1. If the system is in state $i$ at time $n$ (i.e. $X n = i$ ), then the probability that it will shift to state $j$ at time $n + 1$ (i.e $X n + 1 = j$ ) is denoted by:

$p_{ij}\ =\ P[X_{n+1} = j|X_n = i]$

In this example the four possible transition probabilities are:

$p_{00}=\frac{1}{2},\;p_{01}=\frac{1}{2},\;p_{10}=\frac{n}{n+1},\;p_{11}=\frac{1}{n+1}$

Using these probabilities we can construct a Markov chain transition matrix. The $i j t h$ element of that matrix is $p i j$ . Remember that the first index number indicates the row number and the second index number indicates the column number. Thus the Markov chain transition matrix is:

$P(n) = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{n}{n+1} & \frac{1}{n+1} \end{bmatrix}$

This is an example of an inhomogeneous Markov chain because some of the transition probabilities depend on time $n$ .

Example of a Homogeneous Markov Chain

Imagine a system with three possible states, 0, 1 and 2. The transition probabilities are given by:

$p_{00}=0,\;p_{01}=\frac{3}{4},\;p_{02}=\frac{1}{4},\;p_{10}=\frac{1}{4},\;p_{11}=0,\;p_{12}=\frac{3}{4},\;p_{20}=\frac{1}{4},\;p_{21}=\frac{1}{4},\;p_{22}=\frac{1}{2}$

The Markov chain transition matrix of this system is:

$P\ =\ \begin{bmatrix} 0 & \frac{3}{4} & \frac{1}{4} \\ \frac{1}{4} & 0 & \frac{3}{4}\\ \frac{1}{4} & \frac{1}{4} &\frac{1}{2} \end{bmatrix}$

State Vector

Let $\scriptstyle \pi_i(n)\, = P[X_n=i]$ , that is let $\scriptstyle \pi_i(n)\,$ be the probability that at time $n$ the system is in state $i$ . Combining all the states into one vector yields:

$\vec \pi(n) \ = [\pi_0(n),\;\pi_1(n),\;\ldots]$

Since each element of $\scriptstyle\vec \pi(n)$ represents the probability that the system will be in a particular state at a particular time, the sum of those probabilities equals 1 since the system must be in a certain state at any time. Written mathematically it means that:

$\sum_i \pi_i(n) = 1 \,\!$ ,

or equivalently

$\vec \pi(n) \circ \vec 1 \ = 1$ ,

where " $\circ$ " is the dot product operator and $\scriptstyle\vec 1$ is a column vector of height equal to the length of $\scriptstyle\vec \pi(n)\$ and filled with ones.

Solving for the Equilibrium Solution of a Markov Chain

We want to know what is the probability that at time $n + 1$ the system will be in state $i$ . This is readily calculated as follows:

$\pi_i(n+1) = \pi_0(n) P_{0i}(n) + \pi_1(n) P_{1i}(n) + \pi_2(n) P_{2i}(n) + \ldots$

$= \sum_k P[X_n=k] P[X_{n+1}=1|X_n=k] \,\!$

In other words, the $i t h$ element of the vector $\scriptstyle \vec \pi(n+1)$ is the dot product of the vector $\scriptstyle \vec \pi(n)$ and the $i t h$ column of the transition matrix $P (n)$ . This is the definition of vector-matrix multiplication and therefore the vector $\scriptstyle \vec \pi(n)$ can be calculated as:

$\vec \pi(n+1) = \vec \pi(n) P(n)$

Solving for the equilibrium solution of a Markov chain is to determine what is the probability that the system will be in a particular state "in the long run." Since $\scriptstyle \vec \pi(n)$ tells us the probability of all states at time $n$ the equilibrium solution is the vector $\scriptstyle \vec \pi$ which is obtained by taking the limit as time goes to infinity, i.e.

$\vec \pi = \lim_{n \to \infty}\vec \pi(n)$ .

Since we know that $\scriptstyle \vec \pi(n+1) = \vec \pi(n) P(n)$ or equivalently $\scriptstyle \vec \pi(n) = \vec \pi(n-1) P(n-1)$ it follows that:

$\lim_{n \to \infty}\vec \pi(n) = \lim_{n \to \infty}\vec \pi(n-1) P(n-1)$

$\lim_{n \to \infty}\vec \pi(n) = \lim_{n \to \infty}\vec \pi(n-1) \lim_{n \to \infty}P(n-1)$

$\vec \pi = \vec \pi P$

Thus the equilibrium solution, provided we know the transition matrix P, can be found by solving the last equation with the additional constraint that $\textstyle \sum_i \pi_i = 1 \,\!$ .

Note that since $\scriptstyle \vec \pi(n)$ and $P (n)$ both depend on $n$ , in general we cannot separate the limit the way it is done in the second line above. However the transition matrix $P (n)$ is a result of the Markov property and therefore it contains certain properties that make it behave nicely and makes the separation possible.

Example of Solving for the Equilibrium Solution of a Homogeneous Markov Chain

Let $P = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ 1 & 0 \end{bmatrix}$ .

We know that $[\pi_0 \pi_1] = [\pi_0 \pi_1] \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ 1 & 0 \end{bmatrix}$ which, along with the aforementioned constraint on $\scriptstyle \vec \pi$ , leads to the simultaneous equations:

$\begin{cases} \pi_0 = \frac{1}{2}\pi_0 + \pi_1 \\ \pi_1 = \frac{1}{2}\pi_0 \\ \pi_0 + \pi_1 = 1 \end{cases}$

This set of equations can be easily solved and yields $\textstyle \pi_0 = \frac{2}{3}$ and $\textstyle \pi_1 = \frac{1}{3}$ and therefore the equilibrium solution is: