Lesson 1: States and Transition Probabilities

1 Modelling context

Many systems can be described by a small number of categories and the probabilities of moving between them. A patient's health status might be healthy, ill, or recovered. A borrower's credit rating might be AAA, AA, A, BBB, …, D. A consumer's brand preference might be one of several competing products. A machine's operational state might be working, degraded, or failed.

When the transitions between categories happen in discrete steps and the future depends only on the present category, the model is a Markov chain. The chain's behaviour is entirely determined by two things: the list of states, and the probabilities of moving between them in one step. Both are modelling decisions.

The Markov assumption is strong

The Markov property assumes that the next state depends only on the current state. This is often an approximation. In disease progression, for example, the future may depend on how long the patient has been in the current state. In such cases, the state space must be expanded (e.g. "healthy for less than 1 year", "healthy for 1 to 2 years") to preserve the Markov property.

2 Learning objectives

By the end of this lesson you will be able to

Define the state space of a Markov chain.
State the Markov property precisely.
Construct a transition matrix from a specification.
Verify that the rows of a transition matrix sum to 1.
Compute one-step state distributions from an initial distribution.
Recognise situations in which the Markov assumption is violated.

3 Prerequisite review

Random variable: A function that assigns a numerical value to each outcome of a random experiment. In a Markov chain, the state at time t is a random variable X_t.
Conditional probability: The probability of an event given that another event has occurred. Denoted P(A | B).
Matrix multiplication: For a row vector π and a matrix P, the product π P is another row vector with entries (π P)_j = Σ_i π_i P_ij.
Stochastic matrix: A nonnegative matrix whose rows (or columns) sum to 1. A transition matrix is a stochastic matrix.

4 Mathematical formulation

The Markov property

A stochastic process {X_t : t = 0, 1, 2, …} taking values in a set S is a Markov chain if for all t ≥ 0 and all states i, j, i_{t−1}, …, i_0:

P( X_{t+1} = j | X_t = i, X_{t−1} = i_{t−1}, …, X_0 = i_0 )
    = P( X_{t+1} = j | X_t = i )

In words: the conditional distribution of the next state depends only on the current state. The path taken to reach the current state is irrelevant.

When the transition probabilities do not depend on t (time-homogeneous), the chain is specified by a single transition matrix P.

The transition matrix

For a chain with n states 1, 2, …, n, the transition matrix is

P_ij = P( X_{t+1} = j | X_t = i )

Each row of P is a probability distribution over the next state, so

P_ij ≥ 0  for all i, j
Σ_j P_ij = 1  for all i

State distributions

Let π^(t) be the row vector of state probabilities at time t:

π_i^(t) = P( X_t = i )

By the law of total probability and the Markov property,

π_j^(t+1) = Σ_i π_i^(t) P_ij

In matrix form:

π^(t+1) = π^(t) P

Iterating from the initial distribution π^(0):

π^(t) = π^(0) P^t

Figure 5.1. A three-state Markov chain. Arrows between states are labelled with the one-step transition probabilities. Self-loops represent the probability of remaining in the current state.

Reading the diagram

The transition matrix for this chain has rows summing to 1. For example, from state A the chain moves to A with probability 0.1, to B with probability 0.6, and to C with probability 0.3. The sum is 1, as required.

5 Worked example

A simple weather model

Suppose the weather in a certain location is classified each day as sunny (S), cloudy (C), or rainy (R). From historical data, the one-day transition probabilities are estimated as follows:

After a sunny day: 0.7 sunny, 0.2 cloudy, 0.1 rainy.
After a cloudy day: 0.3 sunny, 0.4 cloudy, 0.3 rainy.
After a rainy day: 0.2 sunny, 0.3 cloudy, 0.5 rainy.

Step 1 — Write the transition matrix.

       S    C    R
S   [ 0.7  0.2  0.1 ]
C   [ 0.3  0.4  0.3 ]
R   [ 0.2  0.3  0.5 ]

Step 2 — Verify the rows sum to 1.

Row S: 0.7 + 0.2 + 0.1 = 1.0  ✓
Row C: 0.3 + 0.4 + 0.3 = 1.0  ✓
Row R: 0.2 + 0.3 + 0.5 = 1.0  ✓

Step 3 — Compute the distribution after one day.

Suppose today is sunny, so the initial distribution is π^(0) = (1, 0, 0). The distribution tomorrow is:

π^(1) = π^(0) P = (1, 0, 0) P = (0.7, 0.2, 0.1)

Which is just the first row of the matrix — the distribution of the next state given that today is sunny.

Step 4 — Compute the distribution after two days.

π^(2) = π^(1) P = (0.7, 0.2, 0.1) P

       = 0.7 · (0.7, 0.2, 0.1)
       + 0.2 · (0.3, 0.4, 0.3)
       + 0.1 · (0.2, 0.3, 0.5)

       = (0.49, 0.14, 0.07) + (0.06, 0.08, 0.06) + (0.02, 0.03, 0.05)

       = (0.57, 0.25, 0.18)

Step 5 — Compare with a different starting state.

Starting from a rainy day, π^(0) = (0, 0, 1):

π^(1) = (0.2, 0.3, 0.5)
π^(2) = 0.2·(0.7,0.2,0.1) + 0.3·(0.3,0.4,0.3) + 0.5·(0.2,0.3,0.5)
       = (0.14, 0.04, 0.02) + (0.09, 0.12, 0.09) + (0.10, 0.15, 0.25)
       = (0.33, 0.31, 0.36)

After two days the distributions from the two starting points differ — (0.57, 0.25, 0.18) versus (0.33, 0.31, 0.36). As more days pass, they will converge toward the stationary distribution, which is the subject of Lesson 2.

6 Verification check

Checks to perform

Rows sum to 1. Every row of the transition matrix must sum to 1, to within floating-point tolerance.
Entries are nonnegative. Transition probabilities are nonnegative. A negative entry indicates an input error.
The initial distribution sums to 1. Any valid starting distribution should be a probability distribution.
One-step distributions match the rows. Starting from a state i with probability 1, the one-step distribution should equal row i of the matrix.
Comparison with direct calculation. For small chains, compute the t-step distribution directly from the definition and compare against the matrix-power result.

7 Interpretation

The transition matrix is the Markov chain. Once P is specified, the entire behaviour of the chain — its short-run trajectories, its long-run distribution, its return times — is determined. This is why the specification of P is the critical modelling step, and why errors in P propagate into everything the model produces.

Three interpretive points:

The rows are conditional distributions. Row i describes where the chain goes next, given that it is currently in state i. It says nothing about how the chain got there.
The Markov property is an assumption, not a theorem. Real systems often violate it. The state space must be chosen so that the assumption is a reasonable approximation.
Time-homogeneity is also an assumption. The transition probabilities are assumed not to change over time. If the system's dynamics vary (seasonally, for example), a time-inhomogeneous model may be required.

Specification is the modelling step

Estimating the transition probabilities from data — or choosing them from domain knowledge — is the modelling content of this lesson. The matrix computations that follow are mechanical.

8 Uncertainty and limitations

The transition matrix is rarely known exactly. It is usually estimated from finite data, and it carries the uncertainty of that estimation.

Sources of uncertainty in a Markov-chain model
Source	Effect
Finite estimation data	Each `P_ij` has its own sampling error
State-space definition	Merging or splitting states changes the transition probabilities
Time-homogeneity assumption	Dynamics that change over time are not captured
Markov assumption	If violated, the model's predictions are biased

State-space choice is a modelling decision

Splitting a state into finer sub-states can restore the Markov property but increases the number of parameters. Merging states reduces parameters but may violate the Markov property. The choice should be justified in terms of the model's purpose and the available data.

9 Common implementation errors

Watch for these

Rows that do not sum to 1. A common error is to omit a transition (or to add an extra one) so that the row sums to slightly more or less than 1. Always verify.
Confusing rows and columns. The convention in this course is that rows represent the current state and columns represent the next state. Transposing the matrix produces a different chain.
Forgetting that self-transitions are allowed. Remaining in the same state is a valid transition and must be specified with a probability.
Using a chain that violates the Markov property. If the future depends on more than the current state, the model must be expanded until the property holds.
Assuming the initial distribution is uniform. Unless specified, the initial distribution is part of the model and must be stated.
Not documenting the state definitions. The states must be operationally defined. "Healthy" means nothing without a criterion.

10 Independent modelling task

Your turn

Choose a system that can be described by a small number of states. A customer loyalty model, a machine's operational states, or a simple disease progression model are all suitable.
Define each state operationally. State the time step (day, month, transaction).
Specify the transition probabilities. Use data if available; otherwise state the assumptions under which you chose them.
Write the transition matrix. Verify that rows sum to 1.
Choose an initial distribution and compute the state distribution after 1, 2, and 5 steps.
Discuss whether the Markov property is likely to hold, and what would need to change if it did not.

This exercise forms part of Laboratory 9 and the specification component of Assignment 5.

11 Reflection prompt

Reflect before continuing

The Markov property assumes the future depends only on the present. Give an example of a real system where this is clearly false, and suggest how the state space could be expanded to make it true.

Two or three sentences. Consider systems whose behaviour depends on duration, history, or accumulated state.

12 Lesson summary

Key takeaways

A Markov chain is specified by its states and its transition matrix. Both are modelling decisions.
The Markov property states that the future depends only on the present. It is an assumption, not a theorem.
Rows of the transition matrix sum to 1. Each row is a probability distribution over the next state.
State distributions evolve as π^(t+1) = π^(t) P. The t-step distribution is π^(0) P^t.
The state-space definition determines the model. Merging or splitting states changes the dynamics.

Coming next

Lesson 2 develops the multi-step and steady-state behaviour of a Markov chain, including the Chapman–Kolmogorov equations and the stationary distribution.

§ Self-quiz, practice, and homework

Practice exercises

For the weather model in the worked example, compute the distribution after 3 days starting from a cloudy day.
Construct a transition matrix for a two-state chain (e.g. on/off) with P_{on→off} = 0.1 and P_{off→on} = 0.3. Verify the rows sum to 1.
For the chain in exercise 2, compute the distribution after 5 steps starting from the on state.
Describe a real system where the Markov property is clearly violated. Suggest how to expand the state space to restore it.

Homework problems

Chain specification. Choose a real system with 3–4 states. Define each state operationally, specify the transition matrix (using data or reasoned assumptions), and verify the rows sum to 1. Compute the state distribution after 1, 2, 5, and 10 steps from three different initial distributions. Write a 500-word report.
Markov property assessment. For your chain in problem 1, discuss whether the Markov property is likely to hold. Identify any duration dependence, path dependence, or memory in the system. If the property is violated, propose an expanded state space and estimate the size of the resulting transition matrix.
State-space sensitivity. For the weather model in the worked example, merge "sunny" and "cloudy" into a single state. Reconstruct the transition matrix. Compare the behaviour of the merged and original chains.

Mini project

Choose a real system with a natural state space — customer transitions between brands, patient transitions between health states, machine transitions between operational conditions. Specify the chain, estimate (or assume) the transition probabilities, compute multi-step distributions, and discuss the limitations. Submit the spreadsheet and a two-page report. This is the basis for Laboratory 9 and Assignment 5.