Suppose we have a sequence
\((x_n)\) defined by a linear recurrence of length
\(k\text{,}\) as in
Worksheet 2.5:
\begin{equation*}
x_{n+k} = a_0x_k + a_1x_{k+1}+\cdots + a_{k-1}x_{n-k+1}\text{.}
\end{equation*}
We would like to represent this as a matrix equation, and then use eigenvalues to analyze, replacing the recurrence formula with a matrix equation of the form \(\vv_{k+1}=A\vv_k\text{.}\) A sequence of vectors generated in this way is called a linear dynamical system. It is a good model for systems with discrete time evolution (where changes occur in steps, rather than continuously).
To determine the long term evolution of the system, we would like to be able to compute
\begin{equation*}
\vv_n = A^n \vv_0
\end{equation*}
without first finding all the intermediate states, so this is a situation where we would like to be able to efficiently compute powers of a matrix. Fortunately, we know how to do this when \(A\) is diagonalizable: \(A^n = PD^nP^{-1}\text{,}\) where \(D\) is a diagonal matrix whose entries are the eigenvalues of \(A\text{,}\) and \(P\) is the matrix of corresponding eigenvectors of \(A\text{.}\)
5.
A special type of linear dynamical system occurs when the matrix \(A\) is stochastic. A stochastic matrix is one where each entry of the matrix is between \(0\) and \(1\text{,}\) and all of the columns of the matrix sum to \(1\text{.}\)
The reason for these conditions is that the entries of a stochastic matrix represent probabilities; in particular, they are transition probabilities. That is, each number represents the probability of one state changing to another.
If a system can be in one of \(n\) possible states, we represent the system by an \(n\times 1\) vector \(\vv_t\text{,}\) whose entries indicate the probability that the system is in a given state at time \(t\text{.}\) If we know that the system starts out in a particular state, then \(\vv_0\) will have a \(1\) in one of its entries, and \(0\) everywhere else.
A Markov chain is given by such an initial vector, and a stochastic matrix. As an example, we will consider the following scenario, described in the book Shape, by Jordan Ellenberg:
A mosquito is born in a swamp, which we will call Swamp A. There is another nearby swamp, called Swamp B. Observational data suggests that when a mosquito is at Swamp A, there is a 40% chance that it will remain there, and a 60% chance that it will move to Swamp B. When the mosquito is at Swamp B, there is a 70% chance that it will remain, and a 30% chance that it will return to Swamp A.
(a)
Give a stochastic matrix \(M\) and a vector \(\vv_0\) that represent the transition probabilities and initial state given above.
(b)
By diagonalizing the matrix \(M\text{,}\) determine the long-term probability that the mosquito will be found in either swamp.
(c)
You should have found that one of the eigenvalues of \(M\) was \(\lambda=1\text{.}\) The corresponding eigenvector \(\vv\) satisfies \(M\vv=\vv\text{.}\) This is known as a steady-state vector: if our system begins with state \(\vv\text{,}\) it will remain there forever.
Confirm that if the eigenvector \(\vv\) is rescaled so that its entries sum to 1, the resulting values agree with the long-term probabilities found in the previous part.
6.
A stochastic matrix \(M\) is called regular some power \(M^k\) has all positive entries. It is a theorem that every regular stochastic matrix has a steady-state vector.
(a)
Prove that if \(M\) is a \(2\times 2\) stochastic matrix with no entry equal to zero, then \(1\) is an eigenvalue of \(M\text{.}\)
(b)
Prove that the product of two \(2\times 2\) stochastic matrices is stochastic. Conclude that if \(M\) is stochastic, so is \(M^k\) for each \(k=1,2,3,\ldots\text{.}\)
(c)
Also prove that if \(M^k\) has positive entries for some \(k\text{,}\) then \(1\) is an eigenvalue of \(M\text{.}\)
7.
By searching online or in other textbooks, find and state a more interesting/complicated example of a Markov chain problem, and show how to solve it.