Description
Background:
A Markov chain is a process where future outcomes can be predicted by a current state. These
future outcomes are based on probabilities. The probability of moving on to a certain state depends
on the previous state; this probability does not change with time. (Please note that this is a VERY
oversimplified explanation. There’s so much more to this concept.)
We can express these probabilities as a transition matrix that looks like below:
� = T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y
Where �$% is the probability of moving from state i to state j.
An example of a Markov chain is the weather of one day based on the previous day where the states
are (1) sunny, (2) cloudy, (3) rainy.
Weather Weather of next day
Sunny (j=0) Cloudy (j=1) Rainy (j=2)
Sunny (i=0) 80% 18% 2%
Cloudy (i=1) 40% 50% 10%
Rainy (i=2) 20% 60% 20%
This table represents the probabilities of some day’s weather based on the previous day’s weather.
For example, the probability of it being sunny the day after a cloudy day (�#!) is 40%.
We can get �” (nth power of P) by matrix multiplication. �” would represent the probability of
passing from state i to state j in n stages.
�# = T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y would represent the probabilities after 1 stage
�& = T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y × T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y would represent the probabilities after 2 stages
�’ = T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y × T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y × T
�!!
⋮
�”!
�!#
⋮
�”#
…
⋱
…
�!”
⋮
�””
Y 3 stages
In our weather example, (your input matrix will be a percentage, you must change it to decimals
using per_to_dec())
�# = T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y after 1 stage (next day’s weather)
�& = T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y × T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y = T
0.716 0.246 0.038
0.54 0.382 0.078
0.44 0.456 0.104
Y after 2 stage (after 2 days)
Thus, the probability of it being sunny two days after a cloudy day (�#!
& ) is 54%
If you continue to calculate �#, �&, �’, �(, �) … , you will find the matrix stops changing (changes
negligibly). This is called the long-run distribution.
Notice that all values from �## to �#& have a difference of less than 0.0001. This is where we will
stop for this lab to find our “long-run-distribution”
Instructions:
1. Take a close look at the Markov.py file. There are four empty functions:
per_to_dec(mat): Converts percentages in matrix into a decimals
sig_change(oldmat, newmat):
Checks if there are any “significant”
changes between spatially corresponding elements in a matrix. (use this function
in long_run_dist) You are not allowed to use the isclose() or any() or all()
function. You will not get any points if you do.
prob_x(mat, x): Returns the transition probability matrix after x stages. You
are not allowed to use the matrix_power() function. You will not get any points if
you do.
long_run_dist(probs): Returns the long-run-distribution. You are not
allowed to use the matrix_power() or isclose() or any() or all() function. You will
not get any points if you do.
Read through both of their descriptions carefully. Remember, you will lose points if
you do not follow the instructions. We are using a grading script
2. Your job is to implement all of the listed functions so that it passes any test case.
There are sample test cases provided for you, but these are not the only cases that
we will test. Remember, we will be testing each function separately and collectively.
They should be able to work by themselves and harmoniously with other functions.
3. After completing these functions, comment out the test cases (or delete them) or
else the grading script will pick it up and mark your program as incorrect. Also,
MAKE SURE THAT YOUR PROGRAM DOES NOT PRINT ANYTHING!!! The grading
script may pick up any printed text and misinterpret it as a test case or input
causing you to lose points.
4. Convert your Markov.py file to a .txt file. Submit your Markov.py file and
your .txt file on BeachBoard. Do NOT submit it in compressed folder.
5. Do not email us your code asking us to verify it. We will answer general questions,
but we will not debug your code over email.
Grading rubric:
To achieve any points, your submission must have the following. Anything missing from
this list will result in an automatic zero. NO EXCEPTIONS!
• Submit both py and txt files
• Files named correctly
• Program has no errors (infinite loops, syntax errors, logical errors, etc.) that
terminates the program
Please note that if you change the function headers or if you do not return the proper
outputs according to the function requirements, you risk losing all points for those test
cases.
Points Requirement
5 Correct submission: py and txt file
5 Implemented per_to_dec() correctly. (5 test cases)
15 Implemented sig_change() correctly. (5 test cases)
10 Implemented prob_x() correctly. (5 test cases)
15 Implemented long_run_dist() correctly. (5 test cases)
5 Passes 5 original test cases (also commented out or deleted the test
cases)
*** NOTHING should be rounded. You may lose points if your values are rounded
CECS 229 Lab 5
