4.19 Transition matrices and Markov chains
Studying this course? Keep your progress in one place.
Key facts
- A transition matrix has = probability of moving from state to state , so each column sums to 1.
- The state after steps is , with on the left.
- In a regular chain, tends to the same steady state whatever the start.
- The steady state solves with the entries summing to 1.
- It is an eigenvector of with eigenvalue 1.
Transition matrices
The next state depends only on the current one, and a transition matrix records every probability of moving, one column per starting state.
A system that moves between fixed states, where the next state depends only on the current one, is described by a transition matrix .
Here is the probability of moving from state to state , so each column sums to 1. A transition diagram shows the same data: a node per state and a labelled arrow per move (a loop for staying put).
- 1
State vector sₙ
probabilities of being in each state
- 2
Multiply: sₙ₊₁ = T sₙ
each column of T sums to 1
- 3
New state vector sₙ₊₁
probabilities after one more step
- Each columnsums to 1
- from state to state
Worked example
Rain (R) or dry (D): after rain, rain again with probability ; after dry, rain with probability . Write .
- 1
Column 1 is "from R": rain , dry .
- 2
Column 2 is "from D": rain , dry .
- 3
Each column sums to 1.
A transition matrix has first column . What is ?
State matrices and powers
Multiply the initial state matrix by once for each step, so .
The initial state matrix is a column giving the probability (or number) in each state at the start. After one step .
The entry is the probability of going from state to state in exactly steps. Use your GDC for powers of .
- State after steps
Worked example
It is dry today, so . Find the probability of rain in two days.
- 1
.
- 2
.
- 3
Rain is the first state, so read the first entry.
If it rains today (), what is the probability of rain tomorrow?
The steady state
In a regular chain the state matrix settles to one steady state, whatever the starting state.
A Markov chain is regular if some power of has every entry positive. Then approaches the same steady state whatever is.
- Calculate for a large on your GDC until the values stop changing.
- Or solve with the entries summing to 1 (for an exact answer).
Worked example
Find the long-term probability of rain for .
- 1
Let . gives .
- 2
So , giving .
- 3
The entries sum to 1: , so .
- 4
Hence and .
A regular chain is started in state A in one trial and state B in another. What happens to the long-term probabilities?
Eigenvalue method
says the steady state is an eigenvector of with eigenvalue 1.
Every transition matrix has eigenvalue 1. The steady state is the matching eigenvector, scaled so its entries sum to 1.
Solve , then divide by the sum of its entries. The other eigenvalues have size less than 1, so their effect fades as grows.
- Steady stateeigenvector for
Worked example
Find the eigenvalues and steady state of .
- 1
.
- 2
So or .
- 3
For : , so .
- 4
Divide by so the entries sum to 1.
Which eigenvalue does every transition matrix have?
Modelling and exam technique
Fix the order of the states, build with columns summing to 1, then use or the steady state.
Markov chains model weather, customer loyalty, population movement and machine states. Read whether the state matrix holds counts or probabilities.
- Write with columns summing to 1 and check.
- Use for a given time.
- For the long term, use a high power or with sum 1.
- If has an unknown , use the steady-state equations to find it.
- 1
Order the states
Write them next to
- 2
Build
Columns sum to 1
- 3
Choose a method
or
- 4
Answer in context
Probabilities or counts, 3 s.f.
A state matrix gives 500 and 300 customers. What should the next state matrix add up to?
Try an exam question
A bus company has two depots, A and B. Each day of buses at A stay at A and move to B; of buses at B stay at B and move to A. (a) Write down the transition matrix . (b) Initially 100 buses are at A and none at B. Find the number at A after one day. (c) Find the long-term proportion of buses at A.
[6 marks]
- [1], with columns summing to 1.
- [1]Uses with .
- [1]70 buses at A after one day.
- [1]Sets with , giving .
- [1]So , and gives .
- [1]Long-term proportion at A is .
That's the notes covered.
Carry on to the next subtopic.
Try a question
The transition matrix is defined so that , where is the column state matrix on day . Which matrix is ?
1 mark, marked against the mark scheme
The transition matrix is defined so that , where is the column state matrix on day . Which matrix is ?
1 mark, marked against the mark scheme