Menu
Sign up Sign in

AI HL · AHL 7

Markov Chains & Transition Matrices

0 of 36 skills done

0
AHL 7.1

States, transition matrices and transition diagrams

AHL 7.1

States, transition matrices and transition diagrams

Target: I can write a transition matrix from probability statements, finding missing entries so that each column adds to 1. (+3 more)

By the end of this section

Key points

States and the transition matrix

  • A Markov chain has two or more states. The probability of the next state depends only on the state now, not on the earlier history.
  • The transition matrix \(\mathbf{T}\) holds the probabilities of moving between states. The entry in column X, row Y is \(P(X \to Y)\). Write "Start" above the columns and "End" beside the rows.
  • Every column adds to 1. From any state the chain must go somewhere, and staying where you are counts.
  • Columns are the start state and rows are the end state. Keep the states in the same order for the rows and the columns.

Finding missing entries

  • Fill in what you are given first. Each statement \(P(X \to Y)\) goes in column X, row Y.
  • A missing entry is 1 minus the other entries in its column. A diagonal entry is the probability of staying in that state.
  • "Never" or "impossible" gives a 0 in that place.
  • Add each column when you have finished. A column that does not add to 1 means a mistake.

Transition diagrams

  • A transition diagram is a directed graph. The vertices are the states. An arrow from X to Y is labelled \(P(X \to Y)\).
  • A loop at a vertex is a diagonal entry of \(\mathbf{T}\). The labels on the arrows leaving a vertex, loop included, add to 1.
  • To read a matrix from a diagram, take one vertex at a time. Its arrows give one column. No arrow means 0.
  • An absorbing state has a loop of 1 and no arrow leaving it. Its column is a 1 on the diagonal and 0 elsewhere.

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.
A matrix from two probabilities

Each school day Maya either walks (W) or cycles (C). If she walks today, the probability that she walks tomorrow is 0.7. If she cycles today, the probability that she walks tomorrow is 0.45. Write down the transition matrix for this system.

Working
  1. Write down what is given

    \(P(W \to W) = 0.7\), \(P(C \to W) = 0.45\)

    The start state decides the column. Both numbers go in row W: 0.7 in column W, 0.45 in column C.

  2. Complete each column

    \(P(W \to C) = 1 − 0.7 = 0.3\), \(P(C \to C) = 1 − 0.45 = 0.55\)

    From either state Maya has to do something tomorrow, so each column adds to 1.

  3. Write the matrix

    \(\mathbf{T} = \begin{pmatrix} 0.7 & 0.45 \\ 0.3 & 0.55 \end{pmatrix}\)

    Columns are the start state (W, C). Rows are the end state (W, C).

Video walkthrough coming
Drawing a transition diagram

Draw the transition diagram for \(\mathbf{T} = \begin{pmatrix} 0.42 & 0.14 & 0 \\ 0.31 & 0.57 & 0.38 \\ 0.27 & 0.29 & 0.62 \end{pmatrix}\), where the rows and columns are in the order A, B, C.

Working
  1. Draw one vertex for each state

    Vertices A, B, C

    The diagram is a directed graph. Its vertices are the states.

  2. Diagonal entries are loops

    Loops: A 0.42, B 0.57, C 0.62

    A diagonal entry is the chance of staying where you are.

  3. Other entries are arrows

    Column A: arrows A to B 0.31 and A to C 0.27. Column B: arrows B to A 0.14 and B to C 0.29. Column C: arrow C to B 0.38 only.

    An entry in column X, row Y is the arrow from X to Y. The 0 in column C, row A means there is no arrow from C to A.

  4. 0.420.310.270.140.570.290.380.62ABC
    Check the arrows leaving each vertex

    A: 0.42 + 0.31 + 0.27 = 1, B: 0.14 + 0.57 + 0.29 = 1, C: 0.38 + 0.62 = 1

    The labels on the arrows leaving a vertex, loop included, add to 1.

Video walkthrough coming
A matrix from a diagram with an absorbing state

A machine is checked each week and is working (W), faulty (F) or scrapped (S). The transition diagram is shown. Write down the transition matrix, with the states in the order W, F, S.

0.80.150.050.40.30.31WFS
Working
  1. Go vertex by vertex

    From W: loop 0.8, to F 0.15, to S 0.05. From F: to W 0.4, loop 0.3, to S 0.3. From S: loop 1.

    Each vertex gives one column: the arrows leaving it.

  2. Place each label

    An arrow from X to Y goes in column X, row Y. A loop at X goes in column X, row X.

    A missing arrow is a 0.

  3. Write the matrix

    \(\mathbf{T} = \begin{pmatrix} 0.8 & 0.4 & 0 \\ 0.15 & 0.3 & 0 \\ 0.05 & 0.3 & 1 \end{pmatrix}\)

    Column S is (0, 0, 1): once scrapped, the machine stays scrapped. S is an absorbing state: its loop is 1 and nothing leaves it.

Video walkthrough coming
Four states, diagonal entries missing

A bike is at one of four docking stations, A, B, C or D, at the end of each day. These probabilities are known for the next day: \(P(A \to B) = 0.22\), \(P(A \to C) = 0.13\), \(P(A \to D) = 0.3\); \(P(B \to A) = 0.18\), \(P(B \to C) = 0.32\), and a bike at B never goes to D; \(P(C \to A) = 0.12\), \(P(C \to B) = 0.27\), \(P(C \to D) = 0.21\); \(P(D \to A) = 0.17\), \(P(D \to B) = 0.08\), \(P(D \to C) = 0.41\). Write down the transition matrix.

Working
  1. Fill the given entries

    Each statement \(P(X \to Y)\) goes in column X, row Y. "Never" is 0.

    The diagonal entries are not given. They are the probability of staying at the same station.

  2. Find each diagonal entry

    A: \(1 − 0.22 − 0.13 − 0.3 = 0.35\). B: \(1 − 0.18 − 0.32 − 0 = 0.5\). C: \(1 − 0.12 − 0.27 − 0.21 = 0.4\). D: \(1 − 0.17 − 0.08 − 0.41 = 0.34\)

    Take the other three entries of the column away from 1.

  3. Write the matrix

    \(\mathbf{T} = \begin{pmatrix} 0.35 & 0.18 & 0.12 & 0.17 \\ 0.22 & 0.5 & 0.27 & 0.08 \\ 0.13 & 0.32 & 0.4 & 0.41 \\ 0.3 & 0 & 0.21 & 0.34 \end{pmatrix}\)

    Check that every column adds to 1 before you move on.

Video walkthrough coming