Transition Matrices – Using Recursion (VCE SSCE General Mathematics): Revision Notes

Transition Matrices – Using Recursion

Introduction to matrix recurrence relations

A recurrence relation is a mathematical method for modelling systems that change over time. You may have encountered recurrence relations when studying financial modelling, such as calculating compound interest year by year. The same principle applies to transition matrices, but now we work with matrices instead of single values.

When using transition matrices with recursion, we track how a system evolves through successive states. Each state is represented by a state matrix, and we use a transition matrix to move from one state to the next.

Key components

Every matrix recurrence relation requires:

• An initial state matrix ($S_0$) representing the starting conditions
• A transition matrix ($T$) showing how the system changes
• A recurrence rule that generates each successive state

The beauty of this method is that it allows us to predict future states of complex systems through straightforward matrix multiplication.

The matrix recurrence relation formula

The fundamental formula for matrix recurrence relations is:

$S_0 = \text{initial state matrix}$

$S_{n+1} = T S_n$

This formula tells us that to find the state at step $n+1$, we multiply the transition matrix $T$ by the current state matrix $S_n$.

Understanding the notation

• $S_0$ represents the initial state (at time 0)
• $S_1$ represents the state after one transition
• $S_2$ represents the state after two transitions
• $S_n$ represents the state after $n$ transitions
• $T$ is the transition matrix that remains constant

Generating state matrices step-by-step

Let's examine how to generate successive state matrices using the car rental example. A rental company has cars distributed between two locations: Bendigo and Colac. Initially, there are 50 cars in Bendigo and 40 in Colac.

The transition matrix is:

$T = \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix}$

The initial state matrix is:

$S_0 = \begin{bmatrix} 50 \\ 40 \end{bmatrix}$

Calculating $S_1$ (state after 1 week)

To find the distribution after one week, we calculate:

$S_1 = T S_0$

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

$S_1 = \begin{bmatrix} 0.8 \times 50 + 0.1 \times 40 \\ 0.2 \times 50 + 0.9 \times 40 \end{bmatrix}$

$S_1 = \begin{bmatrix} 44 \\ 46 \end{bmatrix}$

After 1 week, there will be 44 cars in Bendigo and 46 in Colac.

Calculating $S_2$ (state after 2 weeks)

Using the same approach:

$S_2 = T S_1$

$S_2 = \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix} \begin{bmatrix} 44 \\ 46 \end{bmatrix}$

$S_2 = \begin{bmatrix} 39.8 \\ 50.2 \end{bmatrix}$

After 2 weeks, there will be 39.8 cars in Bendigo and 50.2 in Colac.

Calculating $S_3$ (state after 3 weeks)

Continuing the pattern:

$S_3 = T S_2$

$S_3 = \begin{bmatrix} 0.8 & 0.1 \\ 0.2 & 0.9 \end{bmatrix} \begin{bmatrix} 39.8 \\ 50.2 \end{bmatrix}$

$S_3 = \begin{bmatrix} 36.9 \\ 53.1 \end{bmatrix}$

After 3 weeks, there will be 36.9 cars in Bendigo and 53.1 in Colac.

Recognising the pattern

From these calculations, we can see the pattern emerging:

$S_1 = T S_0$

$S_2 = T S_1$

$S_3 = T S_2$

Worked example: Factory machines using recursion

Direct calculation method: Finding $S_n$ efficiently

While the step-by-step method works well for small values of $n$, it becomes tedious for large values. There is a more efficient method for finding the state after $n$ steps without calculating all intermediate states.

Deriving the direct formula

Let's follow the pattern algebraically:

$S_1 = T S_0$

$S_2 = T S_1 = T(T S_0) = T^2 S_0$

$S_3 = T S_2 = T(T S_1) = T^2 S_1 = T^2(T S_0) = T^3 S_0$

Continuing this pattern:

$S_4 = T^4 S_0$

$S_5 = T^5 S_0$

This gives us the general formula:

$S_n = T^n S_0$

This formula allows us to jump directly to any future state without calculating intermediate steps.

Worked example: Using the direct formula

Using inverse matrices to find previous states

Sometimes we need to work backwards through the sequence of states. For example, if we know the state at step $n+1$ but need to find the state at step $n$, we can use the inverse of the transition matrix.

The inverse relationship

We know that:

$S_{n+1} = T S_n$

By multiplying both sides by $T^{-1}$:

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

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

Therefore:

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

This allows us to move backwards through the state sequence.

Worked example: Finding previous states

The steady-state solution

One of the most important questions when analysing transition matrices is: "What happens in the long term?" Often, systems don't continue changing indefinitely. Instead, they settle down to a steady state or equilibrium state where the values remain constant.

What is a steady state?

A steady state occurs when the state matrix stops changing, even though transitions continue to happen. The values stabilize at fixed amounts.

For the car rental problem, let's examine what happens over 15 weeks:

Notice that:

• Initially, the values change significantly each week
• After several weeks, the changes become smaller
• Eventually, the values stabilize at approximately 30 cars in Bendigo and 60 in Colac
• Once reached, these values don't change

The graph shows this convergence visually. Both locations' car numbers approach fixed values and remain there.

Understanding equilibrium

The term "equilibrium" is particularly apt because, even though cars are still moving between locations in the steady state, the flows are balanced. The number of cars leaving Bendigo for Colac equals the number leaving Colac for Bendigo. This balance maintains the steady-state values.

Conditions for a steady state

Estimating the steady-state solution

While we can observe steady-state values by calculating many successive state matrices, there's a more efficient approach using the direct formula.

The steady-state formula

If $S_0$ is the initial state matrix, the steady-state matrix $S$ is given by:

$S = T^n S_0$

as $n$ tends to infinity ($\infty$).

In practice, we cannot calculate $T^\infty$, but we can approximate the steady state by using large values of $n$. Depending on the system, values like $n = 10, 15, 20$ often give excellent approximations.

How to verify convergence

To confirm that a steady state has been reached to a given degree of accuracy, check that at least two successive state matrices agree to that accuracy. For example, if $S_{17}$ and $S_{18}$ both round to the same values, the steady state has been reached.

Worked example: Estimating steady state

Using technology: Calculator methods

Modern calculators can greatly simplify recurrence relation calculations. Here's how to use a CAS calculator effectively:

Summary