## Introduction to Markov Chains

Posted by Ed on January 15, 2012

In the following I will give an easy example on Markov Chains. I will assume that you know how to multiply two matrices.

**Example:**

Suppose today it’s Monday and you want to celebrate your birthday on Wednesday with an outdoor party. Of course, you are interested in the weather and you find this data:

If sunny today, then tommorow: 80% probability for sunny 20% probability for rainy If rainy today, then tomorrow: 60% probability for sunny 40% probability for rainy

This data could for example have been collected during summer. Note that the weather tomorrow only depends on the weather from today, so e.g. it does not matter what the weather was a week ago. So today on Monday, you go outside and see that it is a rainy day. Therefore, the probability that it will be sunny tomorrow is 60%. The problem is that your birthday is not tomorrow but in two days on Wednesday. What is the probability then?

A good idea is to visualize the situation as a graph:

These are the ways to get from *rainy(Monday)* to *sunny(Wednesday)*:

a) rainy(Monday) -> sunny(Tuesday) -> sunny(Wednesday)

b) rainy(Monday) -> rainy(Tuesday) -> sunny(Wednesday)

Let’s calculate the probability for a):

Transition rainy(Monday) -> sunny(Tueday): 0.6 Transition sunny(Tuesday) -> sunny(Wednesday): 0.8 => Transition rainy(Monday) -> sunny(Tuesday) -> sunny(Wednesay): 0.6 * 0.8 = 0.48

Let’s calculate the probability for b):

Transition rainy(Monday) -> rainy(Tueday): 0.4 Transition rainy(Tuesday) -> sunny(Wednesday): 0.6 => Transition rainy(Monday) -> rainy(Tuesday) -> sunny(Wednesay): 0.4 * 0.6 = 0.24

The total transition probability is therefore: 0.48 + 0.24 = 0.72

In a more formal notation:

p[rainy(Monday)->sunny(Wednesday)] = p[rainy(Monday)->sunny(Tuesday)->sunny(Wednesday)] + p[rainy(Monday)->rainy(Tuesday)->sunny(Wednesday)] = p[rainy(Monday)->sunny(Tuesday)]*p[sunny(Tuesday)->sunny(Wednesday)] + p[rainy(Monday)->rainy(Tuesday)]*p[rainy(Tuesday)->sunny(Wednesday)] = 0.6*0.8 + 0.4*0.6 = 0.48 + 0.24 = 0.72

We could ask other questions:

– What is the probability if we start with *sunny(Monday)*?

– What is the probability that it will rain on Friday?

It turns out that we can answer these questions easily if we introduce a* transition matrix P*:

p(ij) is the transition probability transition from i to j, e.g. p(sr) is the transition probability from sunny to rainy.

We have calculated the probability for rainy(Monday)->sunny(Wednesday) before. Let’s do this again with the transition matrix. To get the probability we just take the second power of P:

The probability for *rainy(Monday)->sunny(Wednesday)* is in the left bottom corner of the matrix. The value is 72% which is the same as we calculated before.

(Below is a figure of the matrix. The probability for *rainy(Monday)->sunny(Wednesday)* is the entry.)

To answer the other questions:

– What is the probability if we start with *sunny(Monday)*, i.e. what is the probability for *sunny(Monday)->sunny(Wednesday)*?

Answer: Have a look at the top left corner value. The probability is 76%.

– What is the probability that it will rain on Friday, i.e. what is the probability for *rainy(Monday)->sunny(Friday)*

Answer: If we start on Monday we will have to wait four more days: Tuesday, Wednesday, Thursday and Friday. This corresponds to 4 transitions:

(i) Monday -> Tuesday

(ii) Tuesday -> Wednesday

(iii) Wednesday -> Thursday

(iv) Thursday -> Friday

Thus, calculate and look for the entry.

Finally, here is the **definition** of a Markov chain (quoted from reference [3]):

A (finite) Markov chain is a process with a finite number of states (or outcomes, or events) in which

the probability of being in a particular state at step n+1 depends only on the state occupied at

step n.

**Exercises:**

a) What is the probability for *sunny(Monday)->sunny(Tuesday)*

b) What is the probability for *sunny(Monday)->rainy(Wednesday)*?

c) Have a look at and . Where do you recognize that the sum of the probabilities equals 1.

d) How do you calculate the probability for *rainy(Monday)->rainy(Thursday)?*

e) Can you explain why the formalism with the transition matrix works? (Hint: Look at reference [2])

**Answers:**

a) The probability for *sunny(Monday)->sunny(Tuesday)* is P(ss) = 0.8.

b) The probability for *sunny(Monday)->rainy(Wednesday)* is

c) The probabilities in a row add to 1: the final weather is either sunny or rainy.

d) If it is Monday we will have to wait 3 days till Thursday: Tuesday, Wednesday and Thursday.

This corresponds to 3 transitions:

(i) Monday -> Tuesday

(ii) Tuesday -> Wednesday

(iii) Wednesday -> Thursday

Calculate and consider the entry.

e) To see why the formalism with the transition matrix works consider again our first example.

We wanted to know the probability *p[rainy(Monday)->sunny(Wednesday)]* and we found out that there are two paths corresponding to two probabilities:

(i) p[rainy(Monday)->sunny(Tuesday)->sunny(Wednesday)] (ii) p[rainy(Monday)->rainy(Tuesday)->sunny(Wednesday)]

We further found out that (i) and (ii) can be written as:

(i) p[rainy(Monday)->sunny(Tuesday)]*p[sunny(Tuesday)->sunny(Wednesday)] = p(rs)*p(ss) (ii) p[rainy(Monday)->rainy(Tuesday)]*p[rainy(Tuesday)->sunny(Wednesday)] = p(rr)*p(rs)

The sum of both is the probability we are searching for:

p[rainy(Monday)->sunny(Wednesday)] = p(rs)*p(ss) + p(rr)*p(rs)

Now, I will rename the weather states as 1 and 2:

1 stands for sunny

2 stands for rainy

p[2(Monday)->1(Wednesday)] = p(21)*p(11) + p(22)*p(21)

In general, if we have an *initial state i* and a *final state j* we can write:

p[i(Monday)->j(Wednesday)] = p(i1)*p(1j) + p(i2)*p(2j)

This should remind you of a matrix multiplication:

Let C = A*B where A,B and C are matrices. Then the matrix multiplication is:

**References:**

**[1]** Introduction to Markov Chains – Part 1

Introduction to Markov Chains, Part 2

A youtube video by patrickJMT.

**[2]** Introduction to Probability (pdf)

A book on probability theory by Charles GRINSTEAD and J. Laurie SNELL (see Chapter 11).

**[3]** Markov Chains (pdf)

Lecture notes by Warren Weckesser, Colgate University.

## Leave a Reply