High School
SAT
ACT
University
MCAT
LSAT
DAT
Wize University Linear Algebra Textbook > Eigenvalues and Eigenvectors (Spectral Theory)

Markov Chains (Random Walks)

DiagonalizationPrevious Section
Linear Dynamical SystemsNext Section
Popular Courses
Find My Course
0:00 / 0:00

Markov Chains

A Markov matrix is a square matrix whose columns are numbers in [0,1]\left[0,1\right] which sum to 1.
This is also known as a transition matrix, a stochastic matrix, or a migration matrix.
Examples
Markov matrix
A=[1/3011/31/401/33/40]A = \left[ \begin{array}{ccc} 1/3 & 0 & 1\\ 1/3 & 1/4 & 0\\ 1/3 & 3/4 & 0\\ \end{array} \right]
Not a Markov matrix
B=[−1021/2]B= \left[ \begin{array}{cc} -1 & 0\\ 2 & 1/2 \end{array} \right]
  • First column: contains numbers that are not between 0 and 1.
  • Second column: the sum of the entries is not 1.
PAGE BREAK

Interpretation

The entries in a Markov matrix represent proportions or probabilities.
For example, entry aija_{ij} of a migration matrix is the proportion of the population moving from location jj to location ii.
Example
Fromloc 1loc 2Toloc 1loc 2[1/413/40]\begin{array}{rrc} && \textbf{From}\\ && \text{loc 1} \quad\quad \text{loc 2}\\[0.8em] \textbf{To} & \begin{array}{r} \text{loc 1}\\[0.5em] \text{loc 2} \end{array} & \left[ \begin{array}{rr} \quad 1/4 \quad & \quad 1 \quad\\[0.5em] \quad 3/4 \quad & \quad 0 \quad \end{array} \right] \end{array}
  • 1/41/4 of the population in location 1 stays in location 1
  • 3/43/4 of the population in location 1 moves to location 2
  • All of the population in location 2 moves to location 1
  • None of the population in location 2 stays in location 2
PAGE BREAK

Markov Chain Equation

The state vector at time nn is given by:
x⃗n=[x1n⋮xmn]←amount at location 1 at time n←amount at location m at time n\vec x_n= \begin{bmatrix} x_{\colorTwo{ 1} n}\\ \vdots\\ x_{\colorTwo{ m} n} \end{bmatrix} \begin{array}{l} \leftarrow \text{amount at \textbf{location }} \bm{\colorTwo {1}} \text{ at time } n\\ \\ \leftarrow \text{amount at \textbf{location }} \bm{\colorTwo {m}} \text{ at time } n\\ \end{array}
If AA is a Markov matrix, we can determine the next state vector by computing:
x⃗n+1=Ax⃗n\boxed{\quad \vec{x}_{n+1}=A \vec{x}_n \quad}

Wize Tip
The sum of the entries in each x⃗n\vec x_n must be a constant at all time steps. Use this as a check!

PAGE BREAK

Steady State

If AA is a Markov matrix, then there exists a steady state vector x⃗s\vec x_s such that x⃗s=Ax⃗s\vec x_s=A\vec x_s.
As n\bm {\colorTwo n} increases, the state vectors x⃗n\vec x_{\colorTwo{\bm{ n}}} approach the steady state x⃗s\vec x_{\bm s}:
x⃗0⟶x⃗1⏟Ax⃗0⟶x⃗2⏟Ax⃗1⟶…⟶x⃗n⏟Ax⃗n−1⟶…⟶x⃗s⏟Ax⃗s\vec x_0 \quad \longrightarrow \quad \underbrace{\vec x_1}_{\normalsize A\vec x_0} \quad \longrightarrow \quad \underbrace{\vec x_2}_{\normalsize A\vec x_1} \quad \longrightarrow \quad \dots \quad \longrightarrow \quad \underbrace{\vec x_n}_{\normalsize A\vec x_{n-1}} \quad \longrightarrow \quad \dots \quad \longrightarrow \quad \underbrace{\vec x_s}_{\normalsize A\vec x_{s}}
Finding the Steady State Vector
x⃗s\vec x_s can be found by solving:
(I−A)x⃗s=0⃗ \boxed{\quad (I−A)\vec x_s= \vec0 \quad}
We can solve this homogeneous equation using Gauss-Jordan elimination (just like with eigenvectors!)
0:00 / 0:00

Example: Markov Chains

Consider the migration matrix A=[1/301/22/31/2001/21/2]A=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}.
Suppose there are initially:
  • 180 residents in location 1
  • 180 residents in location 2
  • 180 residents in location 3

Part A)

Find the population of each location after 1 and 2 units of time.
X1=AX0=[1/301/22/31/2001/21/2][180180180]=[150210180]X_1=AX_0=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}\begin{bmatrix}180\\180\\180\end{bmatrix}=\begin{bmatrix}150\\210\\180\end{bmatrix}
Therefore, after one time period, location 1 has 150 residents, location 2 has 210 residents, and location 3 has 180 residents.
X2=AX1=[1/301/22/31/2001/21/2][150210180]=[140205195]X_2=AX_1=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}\begin{bmatrix}150\\210\\180\end{bmatrix}=\begin{bmatrix}140\\205\\195\end{bmatrix}
Therefore, after two time periods, location 1 has 140 residents, location 2 has 205 residents, and location 3 has 195 residents.
PAGE BREAK

Part B)

Find the population of each location after a very long time.
We must find a solution to (I−A)Xs=0(I-A)X_s = 0, so we will reduce the augmented matrix:
[2/30−1/2−2/31/200−1/21/2]R2+R1→R2→[   2/30−1/201/2−1/20−1/21/2]R3+R2→R3→[   2/30−1/20   1/2−1/2000]→2R2→R232R1→R1[       1       0−3/401−1000]\begin{aligned} &\left[\begin{array}{rrr} 2/3&0&-1/2\\ -2/3&1/2&0\\ 0&-1/2&1/2 \end{array}\right]\\[2em] \underrightarrow{R_2+R_1\to R_2} &\left[\begin{array}{rrr} \ \ \ 2/3&0&-1/2\\ 0&1/2&-1/2\\ 0&-1/2&1/2 \end{array}\right]\\[2em] \underrightarrow{R_3+R_2\to R_3} &\left[\begin{array}{rrr} \ \ \ 2/3&0&-1/2\\ 0&\ \ \ 1/2&-1/2\\ 0&0&0 \end{array}\right]\\[2em] \xrightarrow[\normalsize 2R_2 \to R_2]{\normalsize \frac{3}{2}R_1\to R_1} &\left[\begin{array}{rrr} \ \ \ \ \ \ \ 1&\ \ \ \ \ \ \ 0&-3/4\\ 0&1&-1\\ 0&0&0 \end{array}\right] \end{aligned}
Solving for when this system equals the zero vector, we obtain a general solution x⃗s=t[3/411]\vec x_s = t\begin{bmatrix}3/4\\1\\1\end{bmatrix}.
Now we must find a value of tt such that this vector has the same sum as x⃗0\vec x_0 (and every state vector).
t(34+1+1)=180+180+180=540114t=540t=216011\begin{aligned} t\left(\frac{3}{4}+1+1\right)&=180+180+180=540\\[1em] \frac{11}{4}t &= 540\\[1em] t &= \frac{2160}{11} \end{aligned}
Therefore, the population in the long run is:
x⃗s=216011[3/411]=[1620/112160/112160/11]≈[147196196]\vec x_s = \dfrac{2160}{11}\begin{bmatrix}3/4\\1\\1\end{bmatrix}=\begin{bmatrix}1620/11\\2160/11\\2160/11\end{bmatrix}\approx\begin{bmatrix}147\\196\\196\end{bmatrix}

Practice: Markov Chains

Consider the following three temperature scenarios:
  • If it is hot today, it will not be hot tomorrow, and there is a 50% it will be mild tomorrow.
  • If it is mild today, there is a 2/3 chance it will be hot tomorrow, and a 1/3 chance it will be cold tomorrow.
  • If it is cold today, there is a 50% chance it will be hot tomorrow, and it will certainly not be mild tomorrow.
If today is Thursday and it is cold, what temperature scenario is most likely to occur on Saturday? What is its probability?
Extra Practice
Students study for their exams in three libraries at Oxford College. The university has 3 libraries, which are Sylvan (S), Main (M), and Thode (T). When students study at Sylvan, they have a 40% chance of studying at Main library the next day, but they never go to Thode the next day. When students study at Main library, they have a 50% chance of studying at each of the other two libraries the next day. Students that study at Thode tend to study at the same library the next day.
a) Draw a transition diagram for this Markov Chain.
b) Write the transition matrix for the diagram in (a)
Given the absorbing transition matrix T below, find the probability that the Markov process will be absorbed into state B assuming that it begins in state D.
A   B    C    D   ET=ABCDE[10000010000000.670.330.2500.750000.750.2500]\begin{array}{rc} & \begin{array}{ccccc} A\ \ &\ B\ \ \ &\ C\ &\ \ \ D\ &\ \ E \end{array}\\ T=\begin{array}{c} A\\B\\C\\D\\E\end{array} & \begin{bmatrix} 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&0&0.67&0.33\\ 0.25&0&0.75&0&0\\ 0&0.75&0.25&0&0 \end{bmatrix} \end{array}
Use
Concept Clarifier
For each of the following transition matrices:
Draw a transition diagram.
Identify any absorbing states.
Find the value of the first element and of the second element in the distribution vector X2 for stage 2 of a Markov Chain, when the initial distribution vector and transition matrix are:
Given the absorbing transition matrix T below, find the probability that the Markov process will be absorbed into state B assuming that it begins in state D.
Assume for simplicity that every serve in a game of tennis is of one of the following types.
Legal Serve (L), First Fault (F1), Second Fault (F2)\text{Legal Serve (L)},\ \text{First Fault (F1)} ,\ \text{Second Fault (F2)}
After making a First Fault, the server is more careful, so the chance that their next serve is Legal is 0.9. Otherwise, they are less careful, so the chance that their next serve is Legal is only 0.8.
Determine which of the following transition matrices are regular.
P=[0.50.510], Q=[001.4.1.5100], R=[.1.2.7.5.3.2001]P = \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \\ \end{bmatrix} ,\ Q= \begin{bmatrix} 0 & 0 & 1 \\ .4 & .1 & .5 \\ 1 & 0 & 0 \\ \end{bmatrix} ,\ R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}
On any given day this autumn, if it rains today then there is a 0.6 probability that it will rain tomorrow. If it doesn't rain today, there is a 0.3 probability that it will rain tomorrow. If it rains on Sunday, what is the probability that it will rain on Wednesday?
Consider the migration matrix
A=[1/301/22/31/2001/21/2]A=\begin{bmatrix}1/3&0&1/2\\2/3&1/2&0\\0&1/2&1/2\end{bmatrix}
Suppose there are initially 180 residents in location 1, 180 in location 2, and 180 in location 3.
Suppose XnX_n is the state vector at period nn, and AA is a (left) Markov matrix so that Xn+1=AXnX_{n+1}=AX_n. Which of the following matrices is a possible matrix for AA?
Determine which of the following transition matrices are regular.
P=[0.50.510], Q=[001.4.1.5100], R=[.1.2.7.5.3.2001]P = \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \\ \end{bmatrix} ,\ Q= \begin{bmatrix} 0 & 0 & 1 \\ .4 & .1 & .5 \\ 1 & 0 & 0 \\ \end{bmatrix} ,\ R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}
Assume for simplicity that every serve in a game of tennis is of one of the following types.
Legal Serve (L), First Fault (F1), Second Fault (F2)\text{Legal Serve (L)},\ \text{First Fault (F1)} ,\ \text{Second Fault (F2)}
After making a First Fault, the server is more careful, so the chance that their next serve is Legal is 0.9. Otherwise, they are less careful, so the chance that their next serve is Legal is only 0.8.
Concept Clari fier
Student loans have me in a jam, and I'm stuck using second-rate equipment
in most facets of life. My printer, for example, has the following behavior.
If it jams printing a page, then there is a 40% chance it will jam printing the next page.
Is the following transition matrix P regular?
P=[010001.1.6.3]P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \end{bmatrix}
The transition matrix of a certain 3-state Markov chain is
R=[.1.2.7.5.3.2001] R = \begin{bmatrix} .1 & .2 & .7 \\ .5 & .3 & .2 \\ 0 & 0 & 1 \\ \end{bmatrix}
Given that the initial state of the system is S0=[.2.80]S_0 = \begin{bmatrix} .2 & .8 & 0 \end{bmatrix}
Here is the transition matrix of an absorbing Markov chain.
[10000100.3.20.500.4.6] \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ .3 & .2 & 0 & .5 \\ 0 & 0 & .4 & .6 \\ \end{bmatrix}
Assuming the system starts out in State 3, what is the probability that it is eventually absorbed into State 2?
Concept Clari er
Is the transition matrixP=[010001.1.6.3] regular?\text{Is the transition matrix}P = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ .1 & .6 &.3 \\ \end{bmatrix}\ regular?
A gambler starts with a fortune of $2. At each play, he has a 0.3 probability of winning; he either wins $2 or loses $2.
If he makes it to $6, he will stop and call it a win. If he runs out of money, he will stop and call it a loss.
Find the probability that he will win.
Practice Question: Linear Dynamical Systems
An old printer has the following behavior:
If it jams printing a page, then there is a 40% chance it will jam printing the next page.
If it prints a page without jamming, then there is a 90% chance it will print the next page without jamming
The office printer is kind of unreliable:
If it jams printing a page, then there is a 40% chance it will jam printing the next page.
If it prints a page without jamming, then there is a 90% chance it will print the next page without jamming
Can the following matrix be the transition matrix of a Markov Chain?
[11.2.8] \begin{bmatrix} 1 & 1 \\ .2 & .8 \\ \end{bmatrix}
Markov Chains Example With 3 Outcomes
Consider Romeo, a single guy, who wishes to date one of two different women, Juliet a pretty tall girl, and Erica, a short girl with beautiful eyes. Romeo has long days sword fighting with his friends. Coming home tired he decides to roll a die. If it shows an even number, he will go knock on Juliet's door and asks her on a date. If it shows a "1" he will stay home and do nothing. Otherwise, he will go ask Erica for a date. In the meantime, Erica is staying making herself pretty in front of a mirror. Juliet is indifferent between going to see Romeo, hang out with Erica or stay home.
Write the transition matrix for the Markov Chain that computes the probabilities of each person going to a place or staying home each day.
Markov Chains Example With 3 Outcomes
On any given night, I might go to a pub, go to the club, or stay home.
If I go out one night, there's a 1/2 chance I'll stay home the next night, and a 1/4 chance I'll go to the same sort of establishment the next night.
If I stay home one night, there's a 1/2 chance I'll stay home the next night, a 1/4 chance I'll go to the pub the next night, and a 1/4 chance I'll go to a club.
Markov Chains
Practice: Markov Chains
Consider the following three temperature scenarios:
If it is hot today, it will not be hot tomorrow, and there is a 50% it will be mild tomorrow.
Limiting matrix
For an absorbing Markov Chain PP, the powers P2, P3, P4,...P^2,\ P^3,\ P^4,... get closer and closer to a limiting matrix P‾\overline P. To find the limiting matrix, first put the transition matrix into standard form by relabeling the states so that the absorbing states come first. The transition matrix then has an identity matrix in the top left and a matrix QQ in the bottom right such that I−QI-Q is invertible. The inverse F=(I−Q)−1F = (I-Q)^{-1} is called the fundamental matrix for PP and is used to construct the limiting matrix.
P=[I0RQ] standard form transition matrixP= \left[ \begin{array}{c|c} I & \mathbf{0} \\ \hline R &Q \\ \end{array} \right] \text{ standard form transition matrix}
F=(I−Q)−1 fundamental matrix F = (I-Q)^{-1} \text{ fundamental matrix}
Consider a random walk with three states that has transition:
P=[8/103/101/102/103/107/1004/102/10]P=\begin{bmatrix} 8/10 &3/10 &1/10\\ 2/10& 3/10& 7/10\\ 0& 4/10& 2/10 \end{bmatrix}
a) If the walker is equally likely to start in each of the three states, what is the chance
Consider a random walk with three states that has transition:
P=[8/103/101/102/103/107/1004/102/10]P=\begin{bmatrix} 8/10 &3/10 &1/10\\ 2/10& 3/10& 7/10\\ 0& 4/10& 2/10 \end{bmatrix}
a) If the walker is equally likely to start in each of the three states, what is the chance