Example 3.64:
200 people are testing two brands of toothpaste, Brand A and Brand B.
Each month they are allowed to switch brands.
The research firm observes the following:
Today we cover Section 3.7. Read Section 4.1 for next class. Work through suggested exercises.
The midterm is tomorrow. It will cover until the end of Section 3.5. Old midterms are on OWL. Practice on 3.5 on WeBWorK.
Room assignments: A‑B NS7, C‑Le NS1, Li‑Mom SSC2036, Mon‑Ri SSC2032, Ro‑Th SSC2028, Ti‑Z SSC2024. (Also on OWL.)
Also, I'll probably have time in class today to take questions.
Math Help Centre: M-F 12:30-5:30 in PAB48/49 and online 6pm-8pm.
My next office hour is today 2:30-3:20 in MC130.
No homework this week.
Last lecture we finished Section 3.6. I won't review it as today we won't use that material.
Example 3.64:
200 people are testing two brands of toothpaste, Brand A and Brand B.
Each month they are allowed to switch brands.
The research firm observes the following:
This is called a Markov chain. There are definite states, and from each state there is a transition probability for moving to another state at each time step. These probabilities are constant and depend only on the current state.
Suppose at the start that 120 people use Brand A and 80 people use Brand B. Then, in the next month, $$ 0.70(120) + 0.20(80) = 100 \qtext{will use Brand A} $$ and $$ 0.30(120) + 0.80(80) = 100 \qtext{will use Brand B} $$ This is a matrix equation: $$ \bmat{ll} 0.70 & 0.20 \\ 0.30 & 0.80 \emat \coll {120} {80} = \coll {100} {100} $$ Write $P$ for the transition matrix and $\vx_k$ for the state vector after $k$ months have gone by. Then $\vx_{k+1} = P \vx_k$. So $$ \vx_2 = P \vx_1 = \bmat{ll} 0.70 & 0.20 \\ 0.30 & 0.80 \emat \coll {100} {100} = \coll {90} {110} $$ and we see that there are 90 people using Brand A and 110 using Brand B after 2 months.
We can also work with the percentage of people using each brand. Then $\vx_0 = \coll {120/200} {80/200} = \coll {0.60} {0.40}$ and $P\vx_0 = \coll {0.50} {0.50}$. Vectors with non-negative components that sum to 1 are called probability vectors
Note that $P$ is a stochastic matrix: this means that it is square and that each column is a probability vector.
The column indices of $P$ correspond to the current state and the row indices correspond to the next state. The entry $P_{ij}$ is the probability that you transition from state $j$ to state $i$ in one time step, where we now label the states with numbers.
Multiple steps:
Can we compute the probability that we go from state $j$ to
state $i$ in two steps?
Well, $x_{k+2} = P x_{k+1} = P^2 x_k$, so the matrix $P^2$
computes this transition:
$$
\kern-9.5ex
P^2 = \bmat{ll} 0.7 & 0.2 \\ 0.3 & 0.8 \emat \bmat{ll} 0.7 & 0.2 \\ 0.3 & 0.8 \emat
= \bmat{ll} 0.55 & 0.30 \\ 0.45 & 0.70 \emat
$$
So the probability of going from Brand A to Brand B after two steps is $(P^2)_{21} = 0.45 = 0.21+0.24$.
More generally, $(P^k)_{ij}$ is the probability of going from state $\red{j}$ to state $\red{i}$ in $k$ steps.
Long-term behaviour: By multiplying by $P$, you can show that the state evolves as follows: $$ \kern-5ex \begin{aligned} &\coll {0.60} {0.40}, \coll {0.50} {0.50}, \coll {0.45} {0.55}, \coll {0.425} {0.575}, \coll {0.412} {0.588}, \coll {0.406} {0.594},\\ &\coll {0.403} {0.597}, \coll {0.402} {0.598}, \coll {0.401} {0.599}, \coll {0.400} {0.600}, \coll {0.400} {0.600}, \dots \end{aligned} $$ with 40% of the people using Brand A in the long run. Since $$ \bmat{ll} 0.70 & 0.20 \\ 0.30 & 0.80 \emat \coll {0.4} {0.6} = \coll {0.4} {0.6} , $$ once we reach this state, we don't leave. A state $\vx$ with $P \vx = \vx$ is called a steady state vector. We'll prove below that every Markov chain has a steady state vector!
Here's how to find it. We want to find $\vx$ such that $(I - P)\vx = \vec 0$. The augmented system is $$ [I - P \mid \vec 0\,] = \bmat{rr|r} 0.30 & -0.20 & 0 \\ -0.30 & 0.20 & 0 \emat $$ which row reduces to $$ \bmat{rr|r} 1 & -2/3 & 0 \\ 0 & 0 & 0 \emat $$ The solution is $$ x_1 = \frac{2}{3} t,\quad x_2 = t $$ We'd like a probability vector, so $\frac{2}{3} t + t = 1$ which means that $t = 3/5$. This gives $\vx = \coll {0.4} {0.6}$ as we found above.
Theorem: Every Markov chain has a non-trivial steady state vector.
This appears in the book as Theorem 4.30 in Section 4.6.
Proof: Let $P$ be the transition matrix. We want to find a non-trivial solution to $(I - P)\vx = \vec 0$. By the fundamental theorem of invertible matrices and the fact that $\rank (I - P) = \rank ((I - P)^T)$, this is equivalent to $(I - P)^T \vx = \vec 0$ having a non-trivial solution. That is, finding a non-trivial $\vx$ such that $$ P^T \vx = \vx \qtext{(since $I^T = I$).} $$ But since $P$ is a stochastic matrix, we always have $$ P^T \ccolll 1 {\vdots} 1 = \ccolll 1 {\vdots} 1 $$ So therefore $P \vx = \vx$ also has a (different) non-trivial solution.$\qquad\Box$
From this, we find the transition matrix $$ P = \bmat{rrr} 0 & 1/3 & 1/3 \\ 1/2 & 0 & 2/3 \\ 1/2 & 2/3 & 0 \\ \emat $$ The $P_{ij}$ entry is the probability of going from room $j$ to room $i$.
A steady state vector is a vector $\vx$ such that $P\vx = \vx$. That is, $\vx - P\vx = \vec 0$, or $(I - P) \vx = \vec 0$. To find a non-trivial steady state vector for this Markov chain, we solve the homogeneous system with coefficient matrix $I-P$: $$ \bmat{rrr|r} 1 & -1/3 & -1/3 & 0 \\ -1/2 & 1 & -2/3 & 0 \\ -1/2 & -2/3 & 1 & 0 \\ \emat $$ In RREF: $$ \bmat{rrr|r} 1 & 0 & -2/3 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 \\ \emat $$ So $x_3 = t$, $x_2 = t$ and $x_1 = \frac{2}{3} t$. If we want a probability vector, then we want $t+t+\frac{2}{3}t = 1$, so $t = 3/8$, so we get $\colll {2/8} {3/8} {3/8}$.
We'll probably study Markov chains again in Section 4.6.