AHL 7.4 Markov chain problems, absorbing states and eigenvalues · AI HL · AHL 7: Markov Chains & Transition Matrices

AHL 7.4

Markov chain problems, absorbing states and eigenvalues

AHL 7.4

Markov chain problems, absorbing states and eigenvalues

By the end of this section

Key points

Setting up a model

Columns are the starting state and rows are the ending state. The entry in column X, row Y is the probability of going from X to Y. Every column sums to 1: use this to find a missing entry.
In a transition diagram, each non-zero entry is an arrow from the column state to the row state, labelled with the probability. The diagonal entries are loops. A zero entry has no arrow.
Read a description one starting state at a time: each starting state is one column. If a column is not fully described, the missing probability is 1 minus the others.
Use numbers of people in the initial vector to get numbers of people in every later vector. Round only at the end.

Powers and long-term behaviour

The state vector after n steps is \(\mathbf{s}_n=T^n\mathbf{s}_0\). An entry of \(T^n\) is the probability of going from the column state to the row state in n steps.
Long term: a high power of T has identical columns. Each column is the steady-state vector, and it does not depend on the starting state.
Steady state: \(T\mathbf{s}=\mathbf{s}\). Write one equation for each row, replace one of them by \(s_1+s_2+\dots=1\), and solve. One of the equations from \(T\mathbf{s}=\mathbf{s}\) is always redundant.
Write exact answers as fractions and give decimals to 3 significant figures.

Absorbing states

An absorbing state has a 1 on the diagonal and 0 elsewhere in its column: once the chain is there, it stays.
A chain with absorbing states has no single steady state: the long-term columns differ, because where you end depends on where you start.
The probability of ending in an absorbing state is an entry of a high power of T. Start is the column and the absorbing state is the row. Raise the power until the 3 significant figures stop changing.

The eigenvalue method

The steady-state vector is an eigenvector of T with eigenvalue 1, scaled so that its entries sum to 1.
To diagonalise, find the eigenvalues from \(\det(T-\lambda I)=0\) and an eigenvector for each. Put the eigenvectors in the columns of P and the eigenvalues, in the same order, on the diagonal of D. Then \(T=PDP^{-1}\).
Then \(T^n=PD^nP^{-1}\), and \(D^n\) raises each diagonal entry to the power n. This gives \(\mathbf{s}_n\) as an expression in n.
Let \(n\to\infty\): an eigenvalue between \(-1\) and 1 gives a term that tends to 0, so the long-term probabilities come from the eigenvalue 1 term only.

On the calculator

Powers of the transition matrix

Enter T as a matrix, then evaluate T to the power n. Columns are the starting state, rows are the ending state.
To find a state vector, enter the initial vector and multiply by the power: \(T^n\mathbf{s}_0\).
For the long term, use a high power such as \(T^{60}\) or \(T^{100}\), and check that a higher power gives the same 3 significant figures.

Screenshot and video to come

Solving for the steady state

Write the equations from \(T\mathbf{s}=\mathbf{s}\), replace one by the sum of the proportions equal to 1, and solve the system of equations.
Give the exact answer as fractions where the question asks for an exact answer.

Screenshot and video to come

Eigenvalues and eigenvectors

Use the calculator's eigenvalue and eigenvector commands on T.
An eigenvector can be given as any non-zero multiple. For the steady state, scale the eigenvalue 1 vector so its entries sum to 1.
For the steady state, take the eigenvector for the eigenvalue 1 and divide each entry by their sum.

Screenshot and video to come

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.

Reading a transition diagram

Each morning a commuter buys coffee at one of three station cafes: the Platform Cafe (P), the Kiosk (K) or the Deli (D). The transition diagram shows the probabilities of changing cafe from one morning to the next. Write down the transition matrix \(T\).

Working

Columns are the starting state
Column P: arrows leaving P. Column K: arrows leaving K. Column D: arrows leaving D.

The entry in column X, row Y is the probability of going from X to Y.
Read each column
\(P:\ 0.75\text{ (loop)},\ 0.25\text{ to K},\ 0\text{ to D}\) \(K:\ 0.3,\ 0.5,\ 0.2\) \(D:\ 0,\ 0.4,\ 0.6\)

No arrow from P to D, or from D to P, so those entries are 0.
Check the columns
\(0.75 + 0.25 = 1,\quad 0.3 + 0.5 + 0.2 = 1,\quad 0.4 + 0.6 = 1\)

Every column of a transition matrix sums to 1.
The matrix
\(T = \begin{pmatrix}0.75 & 0.3 & 0 \\ 0.25 & 0.5 & 0.4 \\ 0 & 0.2 & 0.6\end{pmatrix}\)

Rows and columns both run P, K, D.

Drawing a transition diagram

A tennis player's form in a match is Good (G), Average (A) or Poor (P). Her form in the next match depends only on her form in this one, with transition matrix \(T=\begin{pmatrix}0.62 & 0.18 & 0 \\ 0.38 & 0.52 & 0.46 \\ 0 & 0.3 & 0.54\end{pmatrix}\) (columns G, A, P in that order, rows in the same order). Draw the transition diagram. How many arrows are there, counting loops?

Working

One vertex for each state
Vertices G, A, P

Place them in a triangle so the arrows are easy to see.
The diagonal gives loops
\(0.62,\ 0.52,\ 0.54\)

The entry in row X, column X is a loop at X.
Each other non-zero entry is an arrow
\(G\to A: 0.38,\ \ A\to G: 0.18,\ \ A\to P: 0.3,\ \ P\to A: 0.46\)

Column G, row A is the probability of going from G to A. The zero entries (G to P and P to G) get no arrow.
The diagram
3 loops + 4 arrows = 7 arrows

Check that the labels leaving each vertex add to 1.

Numbers of customers after n weeks

In the cafe model of the first example, 300 commuters use the Platform Cafe, 200 use the Kiosk and 100 use the Deli on Monday. Assume the same 600 commuters come each morning and the matrix does not change. Find the number of commuters using each cafe four mornings later. Give each answer to the nearest whole number.

Working

The initial vector holds numbers
\(\mathbf{s}_0=\begin{pmatrix}300 \\ 200 \\ 100\end{pmatrix}\)

Using numbers of people instead of probabilities gives numbers of people in every later vector.
The power of T
From the calculator: \(T^{4}=\begin{pmatrix}0.53 & 0.417 & 0.294 \\ 0.348 & 0.378 & 0.409 \\ 0.123 & 0.205 & 0.296\end{pmatrix}\)

Four steps means the fourth power.
Multiply
\(\mathbf{s}_4=T^{4}\mathbf{s}_0=\begin{pmatrix}272 \\ 221 \\ 107\end{pmatrix}\)

The vector \(\mathbf{s}_4\) lists the numbers at P, K and D.
Round at the end
P: 272, K: 221, D: 107

These add to 600, the 600 commuters.

Probability n steps later

A commuter bus is Early (E), On time (O) or Late (L) each day. The state tomorrow depends only on the state today, with transition matrix \(T=\begin{pmatrix}0.48 & 0.28 & 0.12 \\ 0.4 & 0.52 & 0.34 \\ 0.12 & 0.2 & 0.54\end{pmatrix}\) (columns E, O, L, rows in the same order). The bus is early on Monday. Find (a) the probability that it is late on Wednesday, (b) the probability that it is late on Friday.

Working

Count the steps
Monday to Wednesday: 2 steps. Monday to Friday: 4 steps.

An entry of \(T^n\) is the probability of going from the column state to the row state in n steps.
Part (a): square the matrix
From the calculator: \(T^{2}=\begin{pmatrix}0.357 & 0.304 & 0.218 \\ 0.441 & 0.45 & 0.408 \\ 0.202 & 0.246 & 0.374\end{pmatrix}\)

Start E is column E. End L is row L.
Read the entry
\(P(\text{L on Wednesday}) = 0.202\)

Row L, column E of \(T^2\).
Part (b): the fourth power
From the calculator: \(T^{4}=\begin{pmatrix}0.305 & 0.299 & 0.283 \\ 0.438 & 0.437 & 0.433 \\ 0.256 & 0.264 & 0.284\end{pmatrix}\)

Friday is four steps after Monday.
Read the entry
\(P(\text{L on Friday}) = 0.256\)

Row L, column E of \(T^4\). Give 3 significant figures.

Setting up and solving Ts = s

For the three station cafes of the first example, the long-term proportions of commuters at P, K and D are \(x\), \(y\) and \(z\). Set up the equations from \(T\mathbf{s}=\mathbf{s}\) and solve them exactly. Give the proportion at the Kiosk to 3 significant figures.

Working

Write Ts = s
\(\begin{pmatrix}x\\y\\z\end{pmatrix}\) is unchanged by T, so \(0.75x + 0.3y = x; \quad 0.25x + 0.5y + 0.4z = y; \quad 0.2y + 0.6z = z\)

One equation for each row of T.
Tidy the equations
\(-0.25x+0.3y=0;\quad 0.25x-0.5y+0.4z=0;\quad 0.2y-0.4z=0\)

These three add up to 0, so one of them says nothing new.
Replace one by the sum
\(x+y+z=1\)

The proportions add to 1. Keep two of the equations and use this one.
Solve
\(x=\frac{4}{9},\ y=\frac{10}{27},\ z=\frac{5}{27}\)

From the calculator: the exact answer is the ratio 12:10:5 out of 27.
Answer
\(y=\tfrac{10}{27}=0.370\)

About 37.0% of commuters end up at the Kiosk in the long term.

Long-term probabilities with technology

For the bus of the fourth example, find the long-term probability that the bus is late. On 500 journeys, how many would you expect to be late in the long term?

Working

A high power of T
From the calculator: \(T^{60}=\begin{pmatrix}0.297 & 0.297 & 0.297 \\ 0.436 & 0.436 & 0.436 \\ 0.267 & 0.267 & 0.267\end{pmatrix}\)

Every column is now the same, so the starting state no longer matters.
Read a column
\(\mathbf{s}=\begin{pmatrix}0.297 \\ 0.436 \\ 0.267\end{pmatrix}\)

Check with \(T^{100}\): it gives the same to 3 significant figures.
The probability
\(P(\text{late})=0.267\)

The long-term probability does not depend on the start.
Numbers of journeys
\(500\times0.26708=133.54\approx134\)

About 134 late journeys. Round to a whole number.

A matrix from a description

A student's week is Focused (F), Distracted (D) or Resting (R). After a focused week, the next week is focused with probability 0.55 and resting with probability 0.15. After a distracted week, the next is focused with probability 0.5 and distracted with probability 0.3. After a resting week, the next is focused with probability 0.6, and distracted and resting are equally likely. Write down the transition matrix, with states in the order F, D, R.

Working

One column for each starting state
Column F, column D, column R

Each column lists what can happen next, and sums to 1.
Column F
\(0.55 + ? + 0.15 = 1 \Rightarrow ? = 0.3\)

The missing entry is F to D.
Column D
\(0.5 + 0.3 + ? = 1 \Rightarrow ? = 0.2\)

The missing entry is D to R.
Column R
\(0.6 + ? + ? = 1 \Rightarrow ? = 0.2 \text{ each}\)

The remaining 0.4 is shared equally between D and R.
The matrix
\(T = \begin{pmatrix}0.55 & 0.5 & 0.6 \\ 0.3 & 0.3 & 0.2 \\ 0.15 & 0.2 & 0.2\end{pmatrix}\)

Check each column sums to 1.

A game with absorbing states

In a game a player starts with 2 points. Each round she wins 1 point with probability 0.4 and loses 1 point with probability 0.6. The game stops when she has 0 points or 4 points. Write down the transition matrix for the number of points, with states 0, 1, 2, 3, 4. Find the probability that she finishes with 4 points.

Working

Absorbing states
0 and 4: once there, she stays. Column 0 is (1, 0, 0, 0, 0). Column 4 is (0, 0, 0, 0, 1).

An absorbing state has a 1 on the diagonal and 0 elsewhere in its column.
The other columns
From 1: to 0 with 0.6, to 2 with 0.4. From 2: to 1 with 0.6, to 3 with 0.4. From 3: to 2 with 0.6, to 4 with 0.4.

Win means up one state, lose means down one.
The matrix
\(T = \begin{pmatrix}1 & 0.6 & 0 & 0 & 0 \\ 0 & 0 & 0.6 & 0 & 0 \\ 0 & 0.4 & 0 & 0.6 & 0 \\ 0 & 0 & 0.4 & 0 & 0 \\ 0 & 0 & 0 & 0.4 & 1\end{pmatrix}\)

Columns and rows run 0 to 4. Every column sums to 1.
A high power
From the calculator: \(T^{100}=\begin{pmatrix}1 & 0.877 & 0.692 & 0.415 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0.123 & 0.308 & 0.585 & 1\end{pmatrix}\)

After many rounds she is almost certainly in 0 or 4, and the columns show where she ends from each start.
Read the entry
Start 2 is column 2, end 4 is row 4: \(0.308\)

About 30.8%. Check that a higher power gives the same 3 significant figures.

Eigenvalues and diagonalising T

A streaming site has Free (F) and Premium (M) users. Each month 0.12 of free users upgrade to premium and 0.2 of premium users go back to free. Write down the transition matrix \(T\), find its eigenvalues and eigenvectors, and write \(T=PDP^{-1}\). Give the eigenvalue that is not 1.

Working

The matrix
\(T = \begin{pmatrix}0.88 & 0.2 \\ 0.12 & 0.8\end{pmatrix}\)

Column F: 0.88 stay, 0.12 upgrade. Column M: 0.2 leave, 0.8 stay.
The characteristic equation
\(\det(T-\lambda I)=(0.88-\lambda)(0.8-\lambda)-0.024=\lambda^2-1.68\lambda+0.68=0\)

A transition matrix always has the eigenvalue 1.
The eigenvalues
\((\lambda-1)(\lambda-0.68)=0 \Rightarrow \lambda=1,\ \lambda=0.68\)

The calculator's eigenvalue command gives the same two values.
The eigenvectors
\(\lambda=1:\ -0.12x+0.2y=0 \Rightarrow \begin{pmatrix}5\\3\end{pmatrix}\qquad \lambda=0.68:\ 0.2x+0.2y=0 \Rightarrow \begin{pmatrix}1\\-1\end{pmatrix}\)

Any non-zero multiple of an eigenvector is also an eigenvector.
P and D
\(P=\begin{pmatrix}5 & 1 \\ 3 & -1\end{pmatrix},\quad D=\begin{pmatrix}1 & 0 \\ 0 & 0.68\end{pmatrix},\quad T=PDP^{-1}\)

The columns of P are the eigenvectors, in the same order as the eigenvalues in D.

The state after n steps in closed form

Using the streaming site of the last example, 70% of users are free users at the start. Use \(T=PDP^{-1}\) to find an expression for the proportion of free users after \(n\) months. Hence find the proportion of free users in the long term.

Working

Powers of T
\(T^n=PD^nP^{-1}\ \Rightarrow\ \mathbf{s}_n=PD^nP^{-1}\mathbf{s}_0\)

To raise D to a power, raise each diagonal entry to that power.
Find P inverse times s0
\(P^{-1}\mathbf{s}_0=\begin{pmatrix}0.125 \\ 0.075\end{pmatrix}\)

From the calculator, or by hand for a 2 by 2 matrix.
The expression
\(\mathbf{s}_n=\begin{pmatrix}5 & 1 \\ 3 & -1\end{pmatrix}\begin{pmatrix}1&0\\0&0.68^{n}\end{pmatrix}\begin{pmatrix}0.125 \\ 0.075\end{pmatrix}=0.125\begin{pmatrix}5 \\ 3\end{pmatrix}+0.075(0.68)^{n}\begin{pmatrix}1 \\ -1\end{pmatrix}\)

The first component is the proportion of free users.
Free users after n months
\(f_n = 0.625 + 0.075(0.68)^{n}\)

Check n = 0: 0.625 + 0.075 = 0.7.
Let n tend to infinity
\(0.68^{n}\to 0 \Rightarrow f_n\to 0.625\)

The long-term proportion is 0.625, the first entry of the steady-state vector.

Steady state from an eigenvector

Customers of three phone networks, Alto (A), Beta (B) and Core (C), change network each year. The transition matrix is \(T = \begin{pmatrix} 0.55 & 0.1 & 0.15 \\ 0.2 & 0.65 & 0.35 \\ 0.25 & 0.25 & 0.5 \end{pmatrix}\), with the states in the order A, B, C. Use the eigenvalues and eigenvectors of \(T\) to find the steady-state vector. Give the long-term proportion of customers on Beta.

Working

The eigenvalues
From the calculator: \(\lambda = 1,\ 0.45,\ 0.25\)

A transition matrix always has the eigenvalue 1.
The eigenvector for 1
From the calculator: an eigenvector for \(\lambda = 1\) is \(\begin{pmatrix} 7 \\ 15 \\ 11 \end{pmatrix}\)

The calculator may show a different multiple, such as a vector of length 1. Any non-zero multiple will do.
Scale so the entries add to 1
\(7 + 15 + 11 = 33,\quad \mathbf{s} = \begin{pmatrix} \frac{7}{33} \\ \frac{5}{11} \\ \frac{1}{3} \end{pmatrix} = \begin{pmatrix} 0.212 \\ 0.455 \\ 0.333 \end{pmatrix}\)

Divide each entry by the sum. A steady state is a vector of probabilities, so it adds to 1.
Check
\(T\mathbf{s} = \mathbf{s}\) (the first row: \(0.55 \times \frac{7}{33} + 0.1 \times \frac{5}{11} + 0.15 \times \frac{1}{3} = \frac{7}{33}\))

The same vector as solving \(T\mathbf{s} = \mathbf{s}\) with the entries adding to 1. The long-term proportion on Beta is 0.455.

Menu

Markov Chains & Transition Matrices

Markov chain problems, absorbing states and eigenvalues

By the end of this section

Key points

Setting up a model

Powers and long-term behaviour

Absorbing states

The eigenvalue method

On the calculator

Powers of the transition matrix

Solving for the steady state

Eigenvalues and eigenvectors

Worked examples

Reading a transition diagram

Working

Drawing a transition diagram

Working

Numbers of customers after n weeks

Working

Probability n steps later

Working

Setting up and solving Ts = s

Working

Long-term probabilities with technology

Working

A matrix from a description

Working

A game with absorbing states

Working

Eigenvalues and diagonalising T

Working

The state after n steps in closed form

Working

Steady state from an eigenvector

Working

Choose a skill

Quiz