Menu
Sign up Sign in

AI HL · AHL 7

Markov Chains & Transition Matrices

0 of 36 skills done

0
AHL 7.2

Powers of the transition matrix and initial state vectors

AHL 7.2

Powers of the transition matrix and initial state vectors

Target: I can find the probability of being in a state n steps ahead by reading an entry of \(\mathbf{T}^n\). (+5 more)

By the end of this section

Key points

Probabilities n steps ahead

  • \(\mathbf{T}\) gives the probabilities after one step. After n steps they are in \(\mathbf{T}^n\).
  • In \(\mathbf{T}^n\) the columns are still the start state and the rows the end state. The entry in column X, row Y is the probability of being in Y after n steps, starting in X.
  • Find \(\mathbf{T}^n\) on the calculator. Raising each entry to the power n gives a wrong matrix.
  • Count the steps. "After four weeks" is \(\mathbf{T}^4\), and "on Thursday, given Monday" is \(\mathbf{T}^3\).
  • A stated sequence of states, such as sunny then rainy then rainy, is one route. Multiply the entries for each step. Leaving a day out of the question means adding routes, which is what \(\mathbf{T}^n\) does.

State vectors

  • A state vector \(\mathbf{s}_n\) is a column that lists the probabilities, shares or numbers in each state after n steps. Its entries are in the same order as the states.
  • The initial state vector is \(\mathbf{s}_0\). Then \(\mathbf{s}_n = \mathbf{T}^n \mathbf{s}_0\), with \(\mathbf{T}^n\) on the left.
  • If you know the starting state for certain, \(\mathbf{s}_0\) has a 1 in that state and 0 elsewhere. Then \(\mathbf{s}_n\) is that column of \(\mathbf{T}^n\).
  • Shares and probabilities add to 1. With numbers of people, the entries add to the total, which does not change.

Regular matrices

  • A transition matrix is regular if some power of it has every entry positive. A regular chain can reach any state from any state.
  • To test it, find \(\mathbf{T}^2\), \(\mathbf{T}^3\), \(\mathbf{T}^4\), … on the calculator until every entry is positive. A zero in \(\mathbf{T}\) does not stop a matrix being regular: it often disappears in a higher power.
  • A chain with an absorbing state is not regular, because the absorbing column keeps its zeros in every power.
  • A chain that is not regular may not settle. A chain that cycles, such as A to B to C to A, keeps zeros in every power.

On the calculator

A power of the transition matrix

  • Enter the transition matrix T, then raise it to the power n.
  • Read the entry by column (start) then row (end).
  • Keep the full calculator value. Round only the answer, to 3 significant figures.
  • To test whether \(\mathbf{T}\) is regular, raise it to 2, 3, 4, … in turn and stop at the first power with no zero entries.

Screenshot and video to come

A state vector after n steps

  • Enter T as a matrix and \(\mathbf{s}_0\) as a column matrix.
  • Evaluate \(\mathbf{T}^n \mathbf{s}_0\), with the matrix first.
  • To find the first n that passes a target, evaluate for n = 1, 2, 3, … and watch the entry.

Screenshot and video to come

Explore: a Markov chain

Choose a chain and a starting state. Press Next to move the state vector one step on, and watch it settle. Change a probability in the matrix: each column must add to 1, so the last one is found for you.

Start in:

Steps so far, n
State vector,
Steady state, Ts = s

Press Next to take a step.

  1. Start in one state, press Next ten times, then Reset and start in another. What do you notice about where the bars end up?
  2. Add the entries of each column of the matrix. Why must they add to 1? What would a column of 0.5 and 0.4 mean?
  3. Change one probability. Which bars move, and does the steady state move with them?
  4. Press a bar to see the working for that entry. Which column of the matrix is multiplied by which part of the vector?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Probability several steps ahead

Each week a member of an online game is either active (A) or inactive (I). The transition matrix is \(\mathbf{T} = \begin{pmatrix} 0.9 & 0.35 \\ 0.1 & 0.65 \end{pmatrix}\), with the states in the order A, I. A member is inactive this week. Find the probability that the member is active four weeks from now.

Working
  1. Use the fourth power

    Four steps: find \(\mathbf{T}^4\)

    The entries of \(\mathbf{T}^n\) are the probabilities after n steps.

  2. From the calculator

    \(\mathbf{T}^4 = \begin{pmatrix} 0.798 & 0.707 \\ 0.202 & 0.293 \end{pmatrix}\)

    Enter T and raise it to the power 4. Do not raise each entry to the power 4.

  3. Read the entry: column = start, row = end

    Start inactive: column I. End active: row A. \(P = 0.707\)

    Column first, then row. The answer is 3 significant figures.

Video walkthrough coming
A state vector after n steps

A phone company has two plans, Premium (P) and Basic (B). Each month the customers move between plans with transition matrix \(\mathbf{T} = \begin{pmatrix} 0.85 & 0.3 \\ 0.15 & 0.7 \end{pmatrix}\). At the start, 40% of the customers are on Premium and 60% on Basic. Find the proportions of customers on each plan after 3 months.

Working
  1. Write the initial state vector

    \(\mathbf{s}_0 = \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix}\)

    Its entries are in the same order as the states, and they add to 1.

  2. Use \(\mathbf{s}_n = \mathbf{T}^n \mathbf{s}_0\)

    \(\mathbf{s}_3 = \mathbf{T}^3 \mathbf{s}_0 = \begin{pmatrix} 0.85 & 0.3 \\ 0.15 & 0.7 \end{pmatrix}^3 \begin{pmatrix} 0.4 \\ 0.6 \end{pmatrix}\)

    The matrix goes on the left of the vector.

  3. From the calculator

    \(\mathbf{s}_3 = \begin{pmatrix} 0.622 \\ 0.378 \end{pmatrix}\)

    Keep the full value in the calculator and round only the answer.

  4. Answer in words

    After 3 months about 62.2% are on Premium and 37.8% on Basic.

    Check that the two proportions add to 100%.

Video walkthrough coming
Market shares over several months

Three streaming services, X, Y and Z, have market shares of 10%, 20% and 70%. Each month customers move between services with transition matrix \(\mathbf{T} = \begin{pmatrix} 0.78 & 0.06 & 0.17 \\ 0.14 & 0.83 & 0.21 \\ 0.08 & 0.11 & 0.62 \end{pmatrix}\), with the services in the order X, Y, Z. Find the projected market share of each service after 6 months.

Working
  1. Set up the initial state

    \(\mathbf{s}_0 = \begin{pmatrix} 0.1 \\ 0.2 \\ 0.7 \end{pmatrix}\)

    Write the percentages as decimals, in the order X, Y, Z.

  2. Multiply by the sixth power

    \(\mathbf{s}_6 = \mathbf{T}^6 \mathbf{s}_0\)

    6 months is 6 steps.

  3. From the calculator

    \(\mathbf{s}_6 = \begin{pmatrix} 0.301 \\ 0.484 \\ 0.216 \end{pmatrix}\)

    Enter T and s\(_0\) as matrices and evaluate the product.

  4. Give the shares

    X: 30.1%, Y: 48.4%, Z: 21.6%

    The three shares add to 100%.

Video walkthrough coming
Four states with an absorbing state

A machine part is new (N), used (U), worn (W) or failed (F). It is inspected once a month. The transition matrix is \(\mathbf{T} = \begin{pmatrix} 0.76 & 0 & 0 & 0 \\ 0.24 & 0.58 & 0 & 0 \\ 0 & 0.31 & 0.43 & 0 \\ 0 & 0.11 & 0.57 & 1 \end{pmatrix}\), with the states in the order N, U, W, F. A part is new. Find the probability that it has failed after 5 inspections.

Working
  1. Find the fifth power

    \(\mathbf{T}^5 = \begin{pmatrix} 0.254 & 0 & 0 & 0 \\ 0.251 & 0.0656 & 0 & 0 \\ 0.159 & 0.105 & 0.0147 & 0 \\ 0.337 & 0.829 & 0.985 & 1.00 \end{pmatrix}\)

    From the calculator. The same method works for any number of states.

  2. Pick the entry

    Start new: column N. End failed: row F. \(P = 0.337\)

    Column F is \((0, 0, 0, 1)\): a failed part stays failed. F is an absorbing state.

Video walkthrough coming
Is the chain regular?

A robot in a warehouse is in the Dock (D), an Aisle (A) or the Packing bay (P) at the start of each minute. The transition matrix is \(\mathbf{T} = \begin{pmatrix} 0.5 & 0.3 & 0 \\ 0.5 & 0 & 1 \\ 0 & 0.7 & 0 \end{pmatrix}\), with the states in the order D, A, P. Show that the chain is regular, and find the smallest power of \(\mathbf{T}\) with every entry positive.

Working
  1. Look at T

    \(\mathbf{T}\) has zeros, so check the powers

    A zero in \(\mathbf{T}\) does not decide it. Regular means some power has no zeros.

  2. From the calculator

    \(\mathbf{T}^2 = \begin{pmatrix} 0.4 & 0.15 & 0.3 \\ 0.25 & 0.85 & 0 \\ 0.35 & 0 & 0.7 \end{pmatrix}\)

    Two zeros are left, in column P, row A and in column A, row P: not yet.

  3. The next powers

    \(\mathbf{T}^3 = \begin{pmatrix} 0.275 & 0.33 & 0.15 \\ 0.55 & 0.075 & 0.85 \\ 0.175 & 0.595 & 0 \end{pmatrix}\)

    One zero is left, in column P, row P.

  4. All entries positive

    \(\mathbf{T}^4 = \begin{pmatrix} 0.3025 & 0.1875 & 0.33 \\ 0.3125 & 0.76 & 0.075 \\ 0.385 & 0.0525 & 0.595 \end{pmatrix}\)

    Every entry is positive. The chain is regular, and the smallest power is 4. If a zero stays in the same place in every power, the chain is not regular.

Video walkthrough coming
A stated sequence of states

A student has lunch in the Canteen (C) or eats a Packed lunch (P) each day. The transition matrix is \(\mathbf{T} = \begin{pmatrix} 0.7 & 0.5 \\ 0.3 & 0.5 \end{pmatrix}\), with the states in the order C, P. The student eats in the canteen on Monday. Find the probability that on Tuesday and Wednesday the student has a packed lunch and on Thursday is back in the canteen.

Working
  1. The three steps

    C to P, then P to P, then P to C

    Monday to Tuesday, Tuesday to Wednesday, Wednesday to Thursday.

  2. The entries: column = start, row = end

    \(P(C \to P) = 0.3,\quad P(P \to P) = 0.5,\quad P(P \to C) = 0.5\)

    Each step depends only on the day before.

  3. Multiply

    \(0.3 \times 0.5 \times 0.5 = 0.075\)

    Every day is fixed, so there is one route. Do not use \(\mathbf{T}^3\): that adds all the routes.

Video walkthrough coming