MATH 367, fall 98, CHAPTER 9

Markov Chains

Let 1, 2, 3, …, r, be a numeration of all the states a given system can be in. A Markov Chain is a process that prescribes ahead of time, the probabilities of the process being in state j at time n + 1 given that the process was in state i at time n. To simplify the notation, let X_{n} be the random variable that describes in which state the system is at time n. Then

P (X_{n+1} = j|X_{n} = i) = p_{i,j}

In other words, p_{i,j} is the probability of going from i to j in one step. These are called the transition probabilities.

The transition matrix is the matrix

P = [ \begin{matrix}p_{1,1} & p_{1,2} & … & p_{1,r} \\ p_{2,1} & p_{2,2} & … & p_{2,r} \\ … & … & … & … \\ p_{r,1} & p_{r,2} & … & p_{r,r} \end{matrix} ]

To figure out the probability of going from i to j in exactly k steps, one has to look at the (i, j) entry of the matrix P^{k}. If you haven’t yet, you’ll learn that in Linear Algebra.

Let h_{i,j} = the probability that if we start at i we will go to j at some point in time (in k steps for some k > 0).

Let R_{i} = {jsuch that h_{i,j} > 0} = the states that get visited if we start at i.

Definition: i is recurrent if h_{i,i} = 1 and i is transient if h_{i,i} < 1.

Note that if i is recurrent, the Markov chain keeps coming back to i, so the expected number of visits to i (given that you visit i at some point) is infinite. However, it i is transient, there is a positive probability, namely 1 − h_{i,i} > 0, that after visiting i the Markov Chain does not comeback to i. That means that the expected number of visits to i is finite.

Let v_{i,j} = expected number of visits to j if we start at i. Then we have that if i is recurrent v_{i,i} = ∞ and if i is transient, v_{i,i} < ∞. Let’s compute it.

Let p = 1 − h_{i,i} the probability of not comming back to i, if we start at i. If we wait to the first time we don’t come back to i, the average number of trials is 1/p because is like a geometric random variable. So, the average number of returns is then 1/p − 1. That is

v_{i,i} = \frac{1}{p} − 1 = \frac{1 − h_{i,i}}{h_{i,i}} .

Then,

v_{i,j}  = P (visiting j once)E(1 + visits to j|start at j)

+P (never visiting j)E(visits to j|start at i, never get toj)

= h_{i,j}(1 + v_{j,j}) + (1 − h_{i,j})0 = h_{i,j}(1 + \frac{h_{j,j}}{1−h_{j,j}}) = \frac{h_{i,j}}{1−h_{j,j}}

That is

v_{i,j} = \frac{h_{i,j}}{1 − h_{j,j}}

How long does it take?

The question is how long does it take, on average, to go from i to j. If ,h_{i,j} < 1, there is a chance we’ll never get there, so the question doesn’t make sense. So, we are interested in only those cases where h_{i,j} = 1, because in this case you know for sure you are going to get there. Let r_{i,j} = average number of steps needed to reach j for if we start at i. We have

r_{i,j} = 1 + ∑_{k≠j} p_{i,k} r_{k,j}

What happens in the long run? Let m = (m_{1}, m_{2}, m_{3}, …, m_{4}) be a probability vector. This vector indicates the “mass” distribution at each state through 1 to r. We call this vector fixed if the mass distribution doesn’t change in one step of the Markov chain, and hence in any step of the Markov Chain: mP = m.

How much mass do we have at state j after one step of the markov chain? well, we start with mass m_{i} at each state i, and we have probability p_{i,j} of going from i to j, so we get

∑_{i} m_{i}p_{i,j}

this is the jth entry of the vector mP. (Recall P is the transition matrix). So, m is fixed if

∑_{i} m_{i}p_{i,j} = m_{i}. (*)

m is called the equilibrium distribution (the system is in equilibrium, it doesn’t change in time). To find m we need to solve the equation (*).

Also, if you know the r_{k,k}’s you can find the m or viceversa. Two cases:

• if every recurrent state can be reached from every recurrent state, then there is a unique fixed probability vector, m = (m_{1}, m_{2}, …, m_{k}) where m_{k} = 1/r_{k,k}.

• if we are not in the case above, then there are many fixed probability vectors. We can decompose the states into cycles where every recurrent state gets visited by ever other recurrent state in the cycle, and apply the above to that case.

Homework: read chapter 9 and do problems 1–8, 9, 10, 22–25, 57–59, 61, 62, 65.