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 = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.6 & 0.4 \\ \text{rainy} & 0.15 & 0.85 \end{bmatrix} \]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 \(P^2\). We have \[P^2 = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.42 & 0.58 \\ \text{rainy} & 0.2175 & 0.7825 \end{bmatrix}. \]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 \(P^n\).
After some diligence and hard work, something interesting happens to \(P^n\):\[ P^3 = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.3390 & 0.6610 \\ \text{rainy} & 0.2479 & 0.7521 \end{bmatrix} \]\[ P^{10} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2730 & 0.7270 \\ \text{rainy} & 0.2726 & 0.7274 \end{bmatrix} \]\[ P^{20} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2727 & 0.7273 \\ \text{rainy} & 0.2727 & 0.7273 \end{bmatrix} \]\[ P^{50} = \begin{bmatrix} & \text{sunny} & \text{rainy} \\ \text{sunny} & 0.2727 & 0.7273 \\ \text{rainy} & 0.2727 & 0.7273 \end{bmatrix} \]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\times 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 \(a_{n+1}\) in terms of \(a_{n}\). Given any coloring of the \(1\times 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\times \left(n+1\right)\) board, where the top color of the new square is known.
In other words, given the color of the top segment for the \(\left(n+1\right)\)-th square, there will always be two ways to color the remaining. This means that \(a_{n+1}=2a_{n}\), and so \(a_{n}=3\cdot 2^{n}\).
Going back to the given problem, note that there are \(3^{n}\) ways to color the top edges, and \(3\cdot 2^{n}\) ways to color each successive row. Hence the total number of colorings is \[ 3^{n}\cdot \left( 3\cdot 2^{n}\right) ^{m}=3^{m+n}\cdot 2^{mn}. \]
Solution:
Suppose the three colors are blue, red and green. Let \(a_{n}\) be the number of such colorings of a horizontal \(1\times 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 \(a_{1} = 6\).- 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 \(\left(n+1\right)\)-th square, there will always be two ways to color the remaining. This means that \(a_{n+1}=2a_{n}\), and so \(a_{n}=3\cdot 2^{n}\).
Going back to the given problem, note that there are \(3^{n}\) ways to color the top edges, and \(3\cdot 2^{n}\) ways to color each successive row. Hence the total number of colorings is \[ 3^{n}\cdot \left( 3\cdot 2^{n}\right) ^{m}=3^{m+n}\cdot 2^{mn}. \]
SOLUTIONS
(for November 22, 2014)
- Show that if \(2^{n}-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 have\[ \begin{align*} 2^{n}-1 & = 2^{ab}-1 \\ & = \left(2^{a}\right)^{b}-1 \\ & = \left(2^{a}-1\right)\left(\left(2^{a}\right)^{b} + \left(2^{a}\right)^{b-1} + \cdots + 2^{a}+1\right). \end{align*} \]By our definition of \(n\), we can see that \(2^{a}-1>1\), and also, \(\left(\left(2^{a}\right)^{b} + \left(2^{a}\right)^{b-1} + \cdots + 2^{a}+1\right) > 1\). This means that \(2^{n}-1\) has proper divisors, which means it is not prime, which is a contradiction.
- Given a positive integer \(n\), let \(p\left(n\right)\) be the product of the nonzero digits of \(n\). Determine the value of \( p\left(1\right) + p\left(2\right) + \cdots + p\left(999\right) + p\left(1000\right)\). (AIME 1994)(partial credit for Farrell Eldrian Wu [MGC New Life Academy])SOLUTION:Define a function \(m\) such that \(m\left(0\right)=1\) and \(m\left(x\right)=x\), for \(x\neq0\). Note that if \(x=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{0}\), then \[ p\left(x\right)=m\left(a_{n}\right)m\left(a_{n-1}\right)\cdots\left(m_{1}\right)\left(m_{0}\right). \]Specifically, since we are looking at \(3\)-digit numbers,\[p\left(100h+10t+u\right)=m\left(h\right)m\left(t\right)m\left(u\right). \]This means that\[ \begin{align*} p\left(0\right)+p\left(1\right)+p\left(2\right)+\cdots+p\left(999\right) & = m\left(0\right)m\left(0\right)m\left(0\right)+m\left(0\right)m\left(0\right)m\left(1\right) + \\ &\quad \cdots+ m\left(9\right)m\left(9\right)m\left(8\right)+m\left(9\right)m\left(9\right)m\left(9\right)\\ & = \left(m\left(0\right)+m\left(1\right)+\cdots+m\left(8\right)+m\left(9\right)\right)^{3}\\ & = \left(1+1+2+\cdots+8+9\right)^{3}\\ & = 46^{3}. \end{align*} \]So,\[ \left[p\left(1\right)+p\left(2\right)+\cdots+p\left(999\right)\right]+p\left(1000\right) = \left[46^{3}-1\right]+1\\ = 97336. \]
- In \(\triangle 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 \(\triangle ABC\) is \(1\), find the area of \(\triangle 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, \[ \frac{DN}{NC}=\frac{AE}{EC}=\frac{3}{4}. \]Because of this,\[ \begin{align*} \left[ABE\right] & = \frac{3}{7}\left[ABC\right]\\ & = \frac{3}{7}. \end{align*} \]Consequently,\[ \left[BEC\right]=\frac{4}{7}. \]
Note that \[ \frac{BD}{DN} = \frac{7}{2}, \quad \frac{DN}{NC} = \frac{3}{4}. \]so \(BD:DN:NC=21:6:8\). This means \[ \frac{BN}{NC} = \frac{27}{8}, \quad \frac{BD}{BN} = \frac{7}{9}. \]Moreover,\[ \frac{BN}{BC} = \frac{27}{35} \]and\[ \begin{align*} \left[BEN\right] & = \frac{27}{35}\left[BEC\right]\\ & = \frac{27}{35}\cdot\frac{4}{7}. \end{align*} \]Finally, by Triangle Similarity,\[ \begin{align*} \frac{\left[BMD\right]}{\left[BEN\right]} & = \left(\frac{7}{9}\right)^{2} \\ \left[BMD\right] & = \frac{7^{2}}{9^{2}}\left(\frac{27}{35}\cdot\frac{4}{7}\right)\\ & = \frac{4}{15}. \end{align*} \]
