Transition Matrices – Using a Certain Rule Revision Notes for VCE SSCE General Mathematics

Transition Matrices – Using a Certain Rule

Introduction

Previously, we worked with transition matrices using the basic recurrence relation:

$S_0 = \text{initial state matrix}, \quad S_{n+1} = TS_n$

This model works well when the total number of items in a system stays constant. For example, if a car rental company has exactly $90$ cars that move between locations but the fleet size never changes.

However, what happens when items are added to or removed from the system at each step? For instance, if the rental company adds new cars each week, or if a population receives new members regularly?

To handle these situations, we need an extended model that includes additions or reductions.

infoNote

Key Difference Between Models:

The basic model ( $S_{n+1} = TS_n$ ) assumes a closed system where items only move between states. The extended model ( $S_{n+1} = TS_n + B$ ) accounts for external changes to the system at each time step.

Understanding the recurrence relation $S_{n+1} = TS_n + B$

When a system experiences external additions or reductions at each time step, we use the matrix recurrence relation:

$S_0 = \text{initial state matrix}, \quad S_{n+1} = TS_n + B$

where:

$S_0$ is the initial state matrix (starting conditions)
$S_n$ is the state matrix after $n$ time steps
$T$ is the transition matrix (showing movement between states)
$B$ is a column matrix representing external additions or reductions

The role of matrix $B$

The matrix $B$ captures changes that come from outside the system:

Positive values in $B$ represent additions (e.g., new cars added to locations)
Negative values in $B$ represent reductions (e.g., cars removed from service)
Each element in $B$ corresponds to a state in the system

When to use this model

chatImportant

Choosing the Right Model:

Use $S_{n+1} = TS_n + B$ when:

Items are regularly added to or removed from the system
The total number of items changes over time
External factors influence the system at each step

Use $S_{n+1} = TS_n$ when:

The total number of items remains constant
Items only move between states, with no additions or removals

Worked example: rental car problem with additions

Let's apply this model to a rental car scenario where the company expands its fleet each week.

lightbulbExample

Worked Example: Rental Car Fleet with Weekly Additions

Problem setup:

A car rental company starts with $90$ cars: 50 located at Bendigo and 40 located at Colac.

Most cars are rented and returned in the same town, but some are returned to the other location. The transition diagram below shows these percentages:

To expand the business, management decides to add 2 extra cars at each location every week.

Defining the matrices:

The recurrence relation for this situation is:

$S_0 = \begin{bmatrix} 50 \\ 40 \end{bmatrix}, \quad S_{n+1} = TS_n + B$

where:

$T = \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 2 \\ 2 \end{bmatrix}$

The transition matrix $T$ shows:

$80\%$ of cars in Bendigo stay in Bendigo, $20\%$ move to Colac
$10\%$ of cars in Colac move to Bendigo, $90\%$ stay in Colac

The matrix $B$ shows that $2$ cars are added at each location every week.

Step 1: Calculating the state after 1 week

To find the number of cars at each location after $1$ week, we use $S_1 = TS_0 + B$ :

$S_1 = TS_0 + B$

$= \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix} \begin{bmatrix} 50 \\ 40 \end{bmatrix} + \begin{bmatrix} 2 \\ 2 \end{bmatrix}$

First, calculate $TS_0$ :

$= \begin{bmatrix} 44 \\ 46 \end{bmatrix} + \begin{bmatrix} 2 \\ 2 \end{bmatrix}$

Then add $B$ :

$= \begin{bmatrix} 46 \\ 48 \end{bmatrix}$

Conclusion: After 1 week, we predict there will be 46 cars in Bendigo and 48 cars in Colac.

Step 2: Calculating the state after 2 weeks

To find the number of cars after $2$ weeks, we use $S_2 = TS_1 + B$ :

$S_2 = TS_1 + B$

$= \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix} \begin{bmatrix} 46 \\ 48 \end{bmatrix} + \begin{bmatrix} 2 \\ 2 \end{bmatrix}$

Calculate $TS_1$ :

$= \begin{bmatrix} 41.6 \\ 52.4 \end{bmatrix} + \begin{bmatrix} 2 \\ 2 \end{bmatrix}$

Then add $B$ :

$= \begin{bmatrix} 43.6 \\ 54.4 \end{bmatrix}$

Conclusion: After 2 weeks, we predict there will be 43.6 cars in Bendigo and 54.4 cars in Colac.

chatImportant

Critical Observation: No Shortcut Formula

Unlike the basic model $S_{n+1} = TS_n$ , the extended recurrence relation $S_{n+1} = TS_n + B$ doesn't have a simple formula for finding $S_n$ directly. This means we cannot use $S_n = T^nS_0$ as we did before.

Instead, we must work through the problem step-by-step, calculating each successive state matrix in order:

$S_0 \rightarrow S_1 \rightarrow S_2 \rightarrow \ldots \rightarrow S_n$

Working backwards using inverse matrices

Sometimes we need to work backwards through the transition states. For example, if we know the state after several weeks, we might want to find the state from the previous week.

We can move backwards through the sequence:

$S_0, S_1, S_2, \ldots, S_n, S_{n+1}, \ldots$

using the relationship between the forward and reverse formulas.

Forward formula:

$S_{n+1} = TS_n + B$

Reverse formula:

$S_n = T^{-1}(S_{n+1} - B)$

This reverse formula allows us to calculate earlier states when we know later ones.

infoNote

How the Reverse Formula Works

Starting from $S_{n+1} = TS_n + B$ , we can rearrange to solve for $S_n$ :

Subtract $B$ from both sides: $S_{n+1} - B = TS_n$
Multiply both sides by $T^{-1}$ : $T^{-1}(S_{n+1} - B) = S_n$

This gives us the reverse formula: $S_n = T^{-1}(S_{n+1} - B)$

When to use the reverse method

Use this approach when:

You know a later state and need to find an earlier state
You're working backwards to verify calculations
A problem specifically asks for a previous state

bookmarkSummary

Key Points to Remember:

The extended model $S_{n+1} = TS_n + B$ is used when items are added to or removed from a system at each time step.
Matrix $B$ represents external additions (positive values) or reductions (negative values) to the system.
Unlike the basic model, there is no shortcut formula—you must calculate each state step-by-step.
To work backwards through states, use the reverse formula: $S_n = T^{-1}(S_{n+1} - B)$ .
Always perform the matrix multiplication $TS_n$ first, then add matrix $B$ .

Transition Matrices – Using a Certain Rule (VCE SSCE General Mathematics): Revision Notes