Learntofish's Blog

A blog about math, physics and computer science

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 =   \begin{bmatrix}   p(ss) & p(sr) \\  p(rs) & p(rr)   \end{bmatrix}  =   \begin{bmatrix}   0.8 & 0.2 \\  0.6 & 0.4   \end{bmatrix}

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:

P^2 =   \begin{bmatrix}   p(ss) & p(sr) \\  p(rs) & p(rr)   \end{bmatrix}  \cdot   \begin{bmatrix}   p(ss) & p(sr) \\  p(rs) & p(rr)   \end{bmatrix}

=  \begin{bmatrix}   p(ss)p(ss)+p(sr)p(rs) & p(ss)p(sr)+p(sr)p(rr) \\  p(rs)p(ss)+p(rr)p(rs) & p(rs)p(sr)+p(rr)p(rr)   \end{bmatrix}

=  \begin{bmatrix}   0.8 \cdot 0.8 + 0.2 \cdot 0.6 & 0.8 \cdot 0.2 + 0.2 \cdot 0.4  \\  0.6 \cdot 0.8 + 0.4 \cdot 0.6 & 0.6 \cdot 0.2 + 0.4 \cdot 0.4    \end{bmatrix}

=  \begin{bmatrix}   0.64+0.12  & 0.16+0.08 \\  0.48+0.24  & 0.12+0.16    \end{bmatrix}

=  \begin{bmatrix}   0.76  & 0.24 \\  0.72  & 0.28    \end{bmatrix}

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 P^2 matrix. The probability for rainy(Monday)->sunny(Wednesday) is the P^2(rs) 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 P^4 and look for the P^4(rs) entry.

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

A ( finite) Markov chain is a process with a fi nite 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 P and P^2. 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 P^2(sr)=0.24
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 P^3 and consider the P^3(rr) 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:

C(ij) = \sum_{k=1}^n A(ik)B(kj)

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: