4.19 Transition matrices and Markov chains

4.19 Transition matrices and Markov chains

IB Maths: Applications and Interpretation HL: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A transition matrix TT has TijT_{ij} = probability of moving from state jj to state ii, so each column sums to 1.
  • The state after nn steps is sn=Tns0\mathbf{s}_n=T^n\mathbf{s}_0, with TT on the left.
  • In a regular chain, sn\mathbf{s}_n tends to the same steady state whatever the start.
  • The steady state solves Ts=sT\mathbf{s}=\mathbf{s} with the entries summing to 1.
  • It is an eigenvector of TT 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 TT.

Here TijT_{ij} is the probability of moving from state jj to state ii, 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. 1

    State vector sₙ

    probabilities of being in each state

  2. 2

    Multiply: sₙ₊₁ = T sₙ

    each column of T sums to 1

  3. 3

    New state vector sₙ₊₁

    probabilities after one more step

Each step multiplies the state vector by the transition matrix.
  • Each columnsums to 1
  • TijT_{ij}from state jj to state ii

Worked example

Rain (R) or dry (D): after rain, rain again with probability 0.80.8; after dry, rain with probability 0.30.3. Write TT.

A transition matrix has first column (0.6x)\begin{pmatrix}0.6\\x\end{pmatrix}. What is xx?

State matrices and powers

Multiply the initial state matrix by TT once for each step, so sn=Tns0\mathbf{s}_n=T^n\mathbf{s}_0.

The initial state matrix s0\mathbf{s}_0 is a column giving the probability (or number) in each state at the start. After one step s1=Ts0\mathbf{s}_1=T\mathbf{s}_0.

The entry (Tn)ij(T^n)_{ij} is the probability of going from state jj to state ii in exactly nn steps. Use your GDC for powers of TT.

  • State after nn stepssn=Tns0\mathbf{s}_n=T^n\mathbf{s}_0

Worked example

It is dry today, so s0=(01)\mathbf{s}_0=\begin{pmatrix}0\\1\end{pmatrix}. Find the probability of rain in two days.

00.10.20.30.40.50.6012345Days nProbability of rain
Probability of rain after n days, starting from a dry day

If it rains today (s0=(10)\mathbf{s}_0=\begin{pmatrix}1\\0\end{pmatrix}), 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 TT has every entry positive. Then sn\mathbf{s}_n approaches the same steady state whatever s0\mathbf{s}_0 is.

  • Calculate Tns0T^n\mathbf{s}_0 for a large nn on your GDC until the values stop changing.
  • Or solve Ts=sT\mathbf{s}=\mathbf{s} with the entries summing to 1 (for an exact answer).
123456789100.20.40.60.81xy0.6Start dryStart wet
The probability of rain levels off at 0.6, whether the first day is dry or wet

Worked example

Find the long-term probability of rain for T=(0.80.30.20.7)T=\begin{pmatrix}0.8&0.3\\0.2&0.7\end{pmatrix}.

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

Ts=sT\mathbf{s}=\mathbf{s} says the steady state is an eigenvector of TT with eigenvalue 1.

Every transition matrix has eigenvalue 1. The steady state is the matching eigenvector, scaled so its entries sum to 1.

Solve (T−I)v=0(T-I)\mathbf{v}=\mathbf{0}, then divide v\mathbf{v} by the sum of its entries. The other eigenvalues have size less than 1, so their effect fades as nn grows.

24681012140.20.40.60.81xysteady state 2/3P(state 1) after n steps
Illustrative chain with eigenvalues 1 and 0.7: P(state 1) rises from 0 and settles at the steady state 2/3.
  • Steady stateeigenvector for λ=1\lambda=1

Worked example

Find the eigenvalues and steady state of T=(0.80.30.20.7)T=\begin{pmatrix}0.8&0.3\\0.2&0.7\end{pmatrix}.

Which eigenvalue does every transition matrix have?

Modelling and exam technique

Fix the order of the states, build TT with columns summing to 1, then use Tns0T^n\mathbf{s}_0 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 TT with columns summing to 1 and check.
  • Use sn=Tns0\mathbf{s}_n=T^n\mathbf{s}_0 for a given time.
  • For the long term, use a high power or Ts=sT\mathbf{s}=\mathbf{s} with sum 1.
  • If TT has an unknown pp, use the steady-state equations to find it.
  1. 1

    Order the states

    Write them next to TT

  2. 2

    Build TT

    Columns sum to 1

  3. 3

    Choose a method

    Tns0T^n\mathbf{s}_0 or Ts=sT\mathbf{s}=\mathbf{s}

  4. 4

    Answer in context

    Probabilities or counts, 3 s.f.

Answering a Markov chain question

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 70%70\% of buses at A stay at A and 30%30\% move to B; 60%60\% of buses at B stay at B and 40%40\% move to A. (a) Write down the transition matrix TT. (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]

That's the notes covered.

Carry on to the next subtopic.

Try a question

The transition matrix TT is defined so that sn+1=Tsn\mathbf{s}_{n+1}=T\mathbf{s}_n, where sn\mathbf{s}_n is the column state matrix on day nn. Which matrix is TT?

1 mark, marked against the mark scheme

Revision notes