Consider this, your local
weather channel predicts 25% chance of rain today. Given if it rains today, there is a 40% chance
it will not rain tomorrow, and a 60% chance it will. If it does not rain today, there is a 70% chance it will not rain tomorrow, and a 30% chance it will rain tomorrow. Predict the chance of showers tomorrow.
Easy.
/\
/ \
/ \
N R
/ \
/ \
.75 .25
/ \ / \
N R N R
/ \ / \
*.7 *.3 *.4 *.6
| | | |
.525 .225 .100 .150
5/8 chance of no rain tomorrow,
3/8 chance of rain tomorrow.
What about day 2, or 3, or 8? Trees become obsolete, and exponentially useless. For this we employ matricies, and the novelty of
Markov Chains is realized
From day to day, our
probability of rain transitions thru a transition matrix, T. Each row in the matrix is the current rain state for the current day, and each column being the
probability for rain the next day. Note each row adds up to 1, and values for each key must be between 0 and 1 inclusive, and the matrix is a
Square Matrix.
N R
_ _
N | 0.7 0.3 |
T = | |
R |_0.4 0.6_|
For the
tree above, we can express D[0] as
_ N R _
D[0] = |_.75 .25_|
and multiply D[0] by T to get D[1], or the probability of rain tomorrow.
D[1] = D[0]*T
_ N R _
D[1] = |_.625 .375_|
We can then get the probability of rain in 2 days by multiplying D[1] by T
D[2] = D[1]*T
_ N R _
D[2] = |_.5875 .4125_|
Because
matrix multiplication is associative, we can say
D[1] = D[0]*T
D[2] = D[1]*T
D[2] = (D[0]*T)*(T)
D[2] = (D[0])*(T*T)
D[2] = (D[0])*(T^2)
We can get the
probability of rain on any given day (X) by bringing our
transition matrix to a power of X, and multiplying our
initial distribution by this.
D[X] = (D[0])*(T^X)