WHERE IS MY UMBRELLA?
Let us talk about the weather. We give an example that always bothers students on a weekday morning. Suppose that in a certain city, there is a 60% chance that when it is sunny today it will also be sunny tomorrow. When it is rainy today, there is an 85% chance that it will also be rainy tomorrow. Of course, we are making simplistic assumptions here to illustrate the case of Markov processes. However, we can also use this example as an excuse when we are too sleepy to get out of bed on a weekday morning!
We can make a nice diagram called a chain, which can look like something below. The terms sunny and rainy are called states. Arrows represent the transition from one state to another with the corresponding probability values. From the problem, when it is rainy today, there is 0.85 chance that it will also be rainy tomorrow. This also means that there is a 0.15 chance of the weather being sunny tomorrow. Also, when it is sunny today, there is 0.6 chance of sun and 0.4 chance of rain tomorrow.
Diagrams like chains are useful in summarizing given data. Of course, mathematicians would prefer a more compact and powerful tool where calculations can be made, so they make use of matrices to describe the problem. A standard matrix representation of the problem would look something like the one below:P=[sunnyrainysunny0.60.4rainy0.150.85]
The matrix P is called a transition probability matrix or simply a transition matrix. Notice that the rows add up to 1. We can also write rainy instead of sunny first and the mathematics will not change. I prefer the order above.
So let us say that it is sunny today. What is the probability that it will be sunny tomorrow? What is the probability it will be sunny two days from now?
For a simple Markov process like this, the transition matrix two time steps from now is given by the product of the matrix P with itself, or P2. We have P2=[sunnyrainysunny0.420.58rainy0.21750.7825].
This means that two days from now, there is a 42% chance of being sunny if it is sunny today, and a 78.25% chance of the weather being rainy if rains today. To get the weather n days from now, you can compute Pn.
After some diligence and hard work, something interesting happens to Pn:P3=[sunnyrainysunny0.33900.6610rainy0.24790.7521]
P10=[sunnyrainysunny0.27300.7270rainy0.27260.7274]
P20=[sunnyrainysunny0.27270.7273rainy0.27270.7273]
P50=[sunnyrainysunny0.27270.7273rainy0.27270.7273]
Any guesses on the probability of rain or shine 70 days from now?
Notice that as the powers go larger and larger, the probabilities do not change anymore. The probability of sunshine 20, 40, 50, and even 100 days from now is about 27% whether or not it is rainy or sunny right now. This Markov process is said to have a limiting distribution or a steady state distribution.
It is important to note that Markov processes have intricate subtleties that are prone to misinterpretation. Our example above involves some simplifications. A more rigorous treatment of Markov processes can be found in college probability textbooks.
Clark Kendrick Go is an Instructor at the Ateneo de Manila University. He is currently taking his graduate studies in the Nara Institute of Science and Technology in Ikoma, Japan.
OLYMPIAD CORNER
from the Colombian Mathematical Olympiad, 1997
Problem: We are given an m×n grid and three colors. We wish to color each segment of the grid with one of the three colors so that each unit square has two sides of one color and two sides of a second color. How many such colorings are possible?
We now find an+1 in terms of an. Given any coloring of the 1×n board, assume WLOG that its rightmost segment is colored blue. We now add a unit square to the right side of the board to make a 1×(n+1) board, where the top color of the new square is known.
In other words, given the color of the top segment for the (n+1)-th square, there will always be two ways to color the remaining. This means that an+1=2an, and so an=3⋅2n.
Going back to the given problem, note that there are 3n ways to color the top edges, and 3⋅2n ways to color each successive row. Hence the total number of colorings is 3n⋅(3⋅2n)m=3m+n⋅2mn.
Solution:
Suppose the three colors are blue, red and green. Let an be the number of such colorings of a horizontal 1×n board given the colors of the top grid segments. For n=1, assume WLOG the top segment grid is given and is colored blue. That means there are three ways to choose the other segment that will be colored with colored blue, and then two ways to choose the colors of the remaining two segments. This gives us a total of 6 colorings, and hence a1=6.We now find an+1 in terms of an. Given any coloring of the 1×n board, assume WLOG that its rightmost segment is colored blue. We now add a unit square to the right side of the board to make a 1×(n+1) board, where the top color of the new square is known.
- If the new top segment is colored blue, then there are two ways to choose the colors of the remaining two segments.
- If the new top segment is not blue, then there are also two ways to choose which of the remaining segments is colored.
In other words, given the color of the top segment for the (n+1)-th square, there will always be two ways to color the remaining. This means that an+1=2an, and so an=3⋅2n.
Going back to the given problem, note that there are 3n ways to color the top edges, and 3⋅2n ways to color each successive row. Hence the total number of colorings is 3n⋅(3⋅2n)m=3m+n⋅2mn.
SOLUTIONS
(for November 22, 2014)
- Show that if 2n−1 is prime, then n must be prime. (Converse of Mersenne Prime Conjecture)(partial credit for Farrell Eldrian Wu [MGC New Life Academy])SOLUTION:Suppose n is not prime. Then n=ab, where a,b>1. So we have2n−1=2ab−1=(2a)b−1=(2a−1)((2a)b+(2a)b−1+⋯+2a+1).By our definition of n, we can see that 2a−1>1, and also, ((2a)b+(2a)b−1+⋯+2a+1)>1. This means that 2n−1 has proper divisors, which means it is not prime, which is a contradiction.
- Given a positive integer n, let p(n) be the product of the nonzero digits of n. Determine the value of p(1)+p(2)+⋯+p(999)+p(1000). (AIME 1994)(partial credit for Farrell Eldrian Wu [MGC New Life Academy])SOLUTION:Define a function m such that m(0)=1 and m(x)=x, for x≠0. Note that if x=an10n+an−110n−1+⋯+a0, then p(x)=m(an)m(an−1)⋯(m1)(m0).Specifically, since we are looking at 3-digit numbers,p(100h+10t+u)=m(h)m(t)m(u).This means thatp(0)+p(1)+p(2)+⋯+p(999)=m(0)m(0)m(0)+m(0)m(0)m(1)+⋯+m(9)m(9)m(8)+m(9)m(9)m(9)=(m(0)+m(1)+⋯+m(8)+m(9))3=(1+1+2+⋯+8+9)3=463.So,[p(1)+p(2)+⋯+p(999)]+p(1000)=[463−1]+1=97336.
- In △ABC, D, E are on BC and CA respectively, and BD:DC=3:2, AE:EC=3:4. AD and BE intersect at M. Given that the area of △ABC is 1, find the area of △BMD.(solved by Farrell Eldrian Wu [MGC New Life Academy])SOLUTION:Define N on BC such that EN is parallel to AD. The complete figure is shown below.
By Triangle Similarity, DNNC=AEEC=34.Because of this,[ABE]=37[ABC]=37.Consequently,[BEC]=47.
Note that BDDN=72,DNNC=34.so BD:DN:NC=21:6:8. This means BNNC=278,BDBN=79.Moreover,BNBC=2735and[BEN]=2735[BEC]=2735⋅47.Finally, by Triangle Similarity,[BMD][BEN]=(79)2[BMD]=7292(2735⋅47)=415.