Menu
Sign up Sign in

AI HL · AHL 7

Markov Chains & Transition Matrices

0 of 36 skills done

0
AHL 7.3

Steady state and long-term probabilities

AHL 7.3

Steady state and long-term probabilities

Target: I can find long-term probabilities by applying a high power of \(\mathbf{T}\) to an initial state vector. (+3 more)

By the end of this section

Key points

The steady state

  • In the long run a regular chain settles to a steady state \(\mathbf{s}\): one more step changes nothing, so \(\mathbf{T}\mathbf{s} = \mathbf{s}\).
  • The steady state does not depend on the initial vector \(\mathbf{s}_0\).
  • To estimate it, apply a high power of \(\mathbf{T}\) to \(\mathbf{s}_0\). When \(\mathbf{T}^{50}\mathbf{s}_0\) and \(\mathbf{T}^{100}\mathbf{s}_0\) agree, you have reached it.
  • Check first that the chain is regular (Lesson 2). A regular chain has one steady state that every start reaches. A chain that is not regular, such as one with an absorbing state, may not settle to one vector.

The exact steady state

  • Write \(\mathbf{T}\mathbf{s} = \mathbf{s}\) as \((\mathbf{T} - \mathbf{I})\mathbf{s} = \mathbf{0}\): one equation for each row.
  • These equations are not independent, so one of them is no use. Replace one with \(s_1 + s_2 + \dots = 1\), then solve on the calculator.
  • "Exact" means fractions, not rounded decimals.
  • The steady-state vector is an eigenvector of \(\mathbf{T}\) with eigenvalue 1. Lesson 4 uses this.

The long-term matrix

  • As n grows, \(\mathbf{T}^n\) settles to a matrix whose columns are all the steady-state vector. A high power such as \(\mathbf{T}^{100}\) shows it.
  • Each column says: whichever state you start in, this is the long-term probability of each state.
  • A long-term probability times 100 is the long-term percentage of time spent in that state, or of the population in it.
  • Read a single entry of \(\mathbf{T}\) as column = start, row = end. Do the same for a matrix you build from words.

On the calculator

A high power of the matrix

  • Evaluate \(\mathbf{T}^{50}\mathbf{s}_0\) and \(\mathbf{T}^{100}\mathbf{s}_0\), or just \(\mathbf{T}^{100}\).
  • If the two results agree to 3 significant figures, you have the steady state.
  • In \(\mathbf{T}^{100}\) every column is the same.

Screenshot and video to come

Solving for the steady state

  • Write the equations from \((\mathbf{T} - \mathbf{I})\mathbf{s} = \mathbf{0}\), replace one by the sum equal to 1, and solve the system.
  • The calculator can give the answer as exact fractions.
  • Write the equations in your working. The calculator only solves them.

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.
Long-term shares from a high power

Three gyms, 1, 2 and 3, have market shares of 50%, 30% and 20%. Each month members move between gyms with transition matrix \(\mathbf{T} = \begin{pmatrix} 0.8 & 0.1 & 0.15 \\ 0.1 & 0.75 & 0.25 \\ 0.1 & 0.15 & 0.6 \end{pmatrix}\), in that order. Find the long-term market share of each gym.

Working
  1. Apply a high power to \(\mathbf{s}_0\)

    \(\mathbf{s}_0 = \begin{pmatrix} 0.5 \\ 0.3 \\ 0.2 \end{pmatrix}\). Find \(\mathbf{T}^{50} \mathbf{s}_0\) and \(\mathbf{T}^{100} \mathbf{s}_0\)

    Long-term means n large. Use two big powers and compare.

  2. From the calculator

    \(\mathbf{T}^{50} \mathbf{s}_0 = \begin{pmatrix} 0.373 \\ 0.388 \\ 0.239 \end{pmatrix}\), \(\mathbf{T}^{100} \mathbf{s}_0 = \begin{pmatrix} 0.373 \\ 0.388 \\ 0.239 \end{pmatrix}\)

    The two results agree to 3 significant figures, so the system has reached its steady state.

  3. Give the shares

    Gym 1: 37.3%, gym 2: 38.8%, gym 3: 23.9%

    The three shares add to 100%.

Video walkthrough coming
Exact steady state from Ts = s

For the gyms in the last example (\(\mathbf{T} = \begin{pmatrix} 0.8 & 0.1 & 0.15 \\ 0.1 & 0.75 & 0.25 \\ 0.1 & 0.15 & 0.6 \end{pmatrix}\)): (a) set up a system of linear equations for the steady-state shares \(s_1, s_2, s_3\); (b) solve the system to find the exact shares.

Working
  1. Write the steady-state condition

    \(\mathbf{T}\mathbf{s} = \mathbf{s}\) with \(\mathbf{s} = (s_1, s_2, s_3)\)

    In the steady state one more step changes nothing.

  2. (a) Multiply out

    \(0.8 s_1 + 0.1 s_2 + 0.15 s_3 = s_1\) ; \(0.1 s_1 + 0.75 s_2 + 0.25 s_3 = s_2\) ; \(0.1 s_1 + 0.15 s_2 + 0.6 s_3 = s_3\)

    One equation for each row of \(\mathbf{T}\).

  3. Rearrange and add the sum

    \(−0.2 s_1 + 0.1 s_2 + 0.15 s_3 = 0\) ; \(0.1 s_1 − 0.25 s_2 + 0.25 s_3 = 0\) ; \(s_1 + s_2 + s_3 = 1\)

    The three equations from \(\mathbf{T}\mathbf{s} = \mathbf{s}\) are not independent, so drop one and use the fact that the shares add to 1.

  4. (b) Solve on the calculator

    \(\mathbf{s} = (\frac{25}{67}, \frac{26}{67}, \frac{16}{67})\)

    Give exact fractions when the question says exact. They match the decimals from the high power.

Video walkthrough coming
The long-term matrix

People buy either an electric car (E) or a petrol car (P). If someone owns an electric car, the probability that their next car is electric is 0.9. If someone owns a petrol car, the probability that their next car is electric is 0.3. (a) Write down the transition matrix. (b) Write down the probability that the owner of a petrol car buys an electric car next. (c) Find the long-term probability matrix. (d) Hence state the long-term percentage of electric cars.

Working
  1. (a) The matrix

    \(P(E \to E) = 0.9,\ P(P \to E) = 0.3\), so \(\mathbf{T} = \begin{pmatrix} 0.9 & 0.3 \\ 0.1 & 0.7 \end{pmatrix}\)

    Complete each column so that it adds to 1.

  2. (b) Read the entry

    Column P, row E: 0.3

    From petrol (column) to electric (row).

  3. (c) A high power of T

    \(\mathbf{T}^{100} = \begin{pmatrix} 0.750 & 0.750 \\ 0.250 & 0.250 \end{pmatrix}\)

    From the calculator. The columns are the same: the long-term probabilities do not depend on the starting car.

  4. (d) Read a column

    Electric: 75%, petrol: 25%

    Each column is the steady-state vector. The long-term percentage of electric cars is the top entry as a percentage.

Video walkthrough coming
From words to a long-term probability

A commuter train is on time (O) or late (L). If it is on time today, the probability that it is on time tomorrow is 0.85. If it is late today, the probability that it is on time tomorrow is 0.6. (a) Write down the transition matrix. (b) The train is late today. Find the probability that it is on time three days from now. (c) Find the exact long-term probability that the train is on time.

Working
  1. (a) The matrix

    \(\mathbf{T} = \begin{pmatrix} 0.85 & 0.6 \\ 0.15 & 0.4 \end{pmatrix}\), states in the order O, L

    Columns: O gives (0.85, 0.15). L gives (0.6, 0.4).

  2. (b) Cube the matrix

    \(\mathbf{T}^3 = \begin{pmatrix} 0.803 & 0.788 \\ 0.197 & 0.213 \end{pmatrix}\)

    From the calculator. Start late: column L. End on time: row O.

  3. (b) Read the entry

    \(P = 0.788\)

    Three days from now is three steps.

  4. (c) Steady state

    \(-0.15 s_1 + 0.6 s_2 = 0\), \(s_1 + s_2 = 1\). \(\mathbf{s} = (\frac{4}{5}, \frac{1}{5})\)

    The long-term probability that the train is on time is \(\frac{4}{5}\).

Video walkthrough coming