Markov chains: transition matrices, Chapman-Kolmogorov and the stationary distribution

CS2 · Risk Modelling & Survival Analysis · 11 min read

The assumption, and what it buys

A process moves between a set of states — healthy and sick, discount levels on a motor policy, credit ratings, in force and lapsed. It has the Markov property if the probability of where it goes next depends only on where it is now, and not at all on how it got there.

In words: the present state is a complete summary of the past, as far as the future is concerned.

That is a strong assumption and it is frequently false. A policyholder who has just dropped from the top discount level after a claim may well be a worse driver than one who has arrived at the same level on the way up, and if so the chain is not Markov in those states. The usual repair is to enlarge the state space until it is — split "level 1" into "level 1, arrived from below" and "level 1, arrived from above". That trick is worth knowing because it is what makes the assumption workable in practice, and because an exam question that says "comment on the Markov assumption" is usually asking for it.

What the assumption buys is enormous. Without it, the probability of a path of length 20 needs the whole history; with it, everything about the process is contained in one table of one-step probabilities, and every question about the future is answered by multiplying that table by itself.

The transition matrix

Collect the one-step probabilities into a matrix P, with pij in row i and column j meaning "the probability of being in j next, given you are in i now".

Two properties, and the second is the free check you should use every time.

• Every entry is between 0 and 1, because each is a probability.
• Every row sums to exactly 1, because from any state the process must go somewhere, including possibly staying put. Columns need not sum to anything.

Rows sum to 1; columns do not. Getting that the wrong way round transposes the matrix, and a transposed transition matrix gives answers that are wrong but entirely plausible-looking. Check the row sums before using a matrix you have just written down, and again after every multiplication.

Reading a matrix

Two state types have names worth knowing. A state with pii = 1 is absorbing: once in, never out. Death in a mortality model is the standard example, and an absorbing state shows up as a row with a single 1 on the diagonal and zeros elsewhere. A set of states you can get out of but not back into makes the chain reducible, and a reducible chain has no single long-run distribution — where it ends up depends on where it started.

Chapman-Kolmogorov: multi-step probabilities

How do you get from i to j in two steps? You go somewhere in between, and that somewhere can be any state. So add up over the possibilities:

That is exactly the formula for the (i, j) entry of P × P. Which means the two-step transition matrix is P2, and the general statement — the Chapman-Kolmogorov equation — is

In words: to go somewhere in m + n steps, go somewhere in m steps and then onwards in n, and add up over every possible stopping point in the middle.

That is the whole of it. There is no new probability in the Chapman-Kolmogorov equations; they are the law of total probability, applied to an intermediate time, and the only reason they get a name is that the name is shorter than the sentence. The practical consequence is that n-step probabilities are powers of one matrix, and nothing beyond matrix multiplication is needed to answer any question about where the chain will be.

Where the chain is after n steps

If the starting position is a row vector of probabilities π(0), then

The second form is the one to compute with. Each step is one vector-matrix product, the intermediate answers are themselves meaningful, and you never have to square a matrix. A question asking for the distribution after six years wants six of these, not P6.

The stationary distribution

Keep stepping and, for a well-behaved chain, the distribution settles down to something that stops changing. A row vector π is a stationary distribution if applying one more step leaves it alone:

In words: the proportions in each state are such that the flows in and out of every state exactly balance.

Finding it is solving a set of linear equations. Note the shape of the problem: πP = π is n equations in n unknowns but one of them is redundant, because the row sums force it. So you discard any one equation and use ∑πi = 1 in its place. Forgetting to do that leaves you with a system whose only solution is all zeros, which is the usual way this calculation fails.

When a stationary distribution is also the long-run answer

Two conditions, and a question may well turn on them.

The chain must be irreducible — every state reachable from every other, so the chain cannot get stuck in part of the space. And it must be aperiodic — not forced to return to a state only at multiples of some fixed number of steps. A chain that alternates strictly between two states has a stationary distribution of (0.5, 0.5) but never settles there; it oscillates forever. Under both conditions the distribution converges to π whatever the starting state, and π is also the long-run proportion of time spent in each state.

A chain with an absorbing state fails irreducibility, and its stationary distribution is the trivial one that puts all the probability on the absorbing state. That is correct and useless — for an absorbing chain the interesting questions are how long until absorption and which absorbing state, not where it settles.

Where marks are lost

Transposing the matrix. Rows are "from", columns are "to", and rows sum to 1. If your row sums are not 1, stop.

Writing π as a column and computing Pπ. The stationary equation is πP = π with π a row vector. Pπ = π with a column vector asks a different question and gives a different answer.

Dropping the normalisation. πP = π determines π only up to a scale factor. The condition that the entries add to 1 is part of the problem, not an afterthought.

Confusing p(n)ij with "first reaches j at step n". The n-step transition probability allows the chain to have visited j and left again. First-passage probabilities are a different calculation and a question will word it carefully: "is in state j at time n" against "first enters state j at time n".

Assuming convergence without checking. Before asserting a long-run distribution, say that the chain is irreducible and aperiodic, or say which condition fails.

Questions students ask

Do I have to compute Pⁿ to answer an n-step question?

Almost never. If you want one row of Pn, iterate that row as a vector — n vector-matrix products instead of n matrix multiplications, and far fewer chances to slip. If you want the long-run answer, solve the stationary equations instead of iterating at all.

Is the stationary distribution always unique?

For an irreducible finite chain, yes. A reducible chain can have many: a chain with two absorbing states has a whole family of stationary distributions, one for each way of splitting the probability between them. Uniqueness is a consequence of irreducibility, not a general fact about matrices.

What is the difference between this and a multi-state model?

Mainly time. A Markov chain moves in discrete steps — policy years, calendar years — and is described by transition probabilities. A Markov jump process moves in continuous time and is described by transition intensities, which are hazard rates between states. The ideas carry over directly: the matrix of probabilities becomes a matrix of intensities, and the Chapman-Kolmogorov equations become differential equations.

Why does the no-claims discount example come up so often?

Because it is a genuine commercial system that really is close to Markov, the states are few and meaningful, and the long-run distribution answers a question an insurer actually asks: at equilibrium, what average discount am I giving away? The worked example below computes exactly that.

A worked example

A motor insurer runs a three-level no-claims discount scheme. Level 0 carries no discount, level 1 carries 20% and level 2 carries 40%. A policyholder who makes no claim in a year moves up one level, or stays at level 2 if already there. A policyholder who makes a claim drops to level 0.

The probability of making a claim depends on the level, because better drivers tend to have reached the higher levels. All the probabilities and the premium below are invented for this example.

The transition matrix

From level 0: a claim keeps you at 0, no claim takes you to 1. From level 1: a claim sends you to 0, no claim takes you to 2. From level 2: a claim sends you to 0, no claim keeps you at 2.

Row sums: 1.00, 1.00, 1.00. Column sums: 0.45, 0.80, 1.75 — which are not 1 and are not meant to be. The matrix is the right way round.

Two steps, by matrix multiplication

Row 0 of P2, entry by entry:

The full two-step matrix, with its row sums:

The same two-step probability, by counting paths

What is the probability a driver starting at level 0 is back at level 0 after two years? List every route and add:

Which is the matrix entry. That agreement is not a coincidence or a check on the arithmetic alone — it is the Chapman-Kolmogorov equation, and seeing the two calculations land on the same number is the most useful minute you can spend on this topic.

The long run, route one: solve the equations

Write π = (π0, π1, π2) and read πP = π column by column:

The second equation gives π1 = 0.8π0. The third rearranges to 0.10π2 = 0.85π1, so π2 = 8.5π1 = 6.8π0. Now use the normalisation in place of the first equation, which is the redundant one:

Put it back into the equation that was discarded, which is the real test of the solution:

Equal to π₀ to seven decimal places, and the three entries add to 1.0000000.

The long run, route two: iterate from a single state

Start every policyholder at level 0, so π(0) = (1, 0, 0), and step forward one year at a time.

Every row sums to 1.0000000, and by year eight the distribution agrees with the solved answer to four decimal places. Two completely different calculations — one solving three linear equations, one multiplying a vector by a matrix eight times — arriving at the same place.

Row 2 of this table is row 0 of P2, as it has to be, which is a third cross-check for free.

What the insurer actually wanted to know

The chain is irreducible — level 0 is reachable from everywhere by claiming, and levels 1 and 2 are reachable from 0 by not claiming — and it is aperiodic, since a driver can stay at level 0 or at level 2 for a single year. So the stationary distribution really is the long-run answer, and it is the long-run proportion of time any one policyholder spends at each level.

The average discount given away in the long run is therefore

On a full premium of ₹20,000, the insurer collects 20,000 × (1 − 0.334884) = ₹13,302.32 on average once the book has matured. Check it the other way: the discount given away is 20,000 × 0.334884 = ₹6,697.68, and 13,302.32 + 6,697.68 = ₹20,000.00 exactly.

And read the number before moving on. Nearly 79% of the time is spent at the top level, because at a 10% claim rate a driver who gets there tends to stay. A scheme designed with a vague sense that the three levels would be roughly populated would be giving away a third of its premium income without having noticed, and two matrix calculations are all it took to find that out.

Where this fits in CS2

This page explains one idea from CS2 Risk Modelling & Survival Analysis. The full CS2 syllabus, with what each part is examined on, sits on the course page, and past-paper style mock exams with full solutions are where you find out whether the idea has stuck under time pressure.

Other CS2 topics explained

• The survival function and the hazard rate, explained
• The Kaplan-Meier estimator, and why censoring needs it
• The Cox proportional hazards model, and what a hazard ratio means
• Central exposed to risk, and the two mortality rates it produces
• Bühlmann credibility: how much to trust one risk's own experience
• Extreme value theory: block maxima, thresholds and the generalised Pareto distribution
• Copulas and Sklar's theorem: modelling dependence without touching the margins

Stuck on a term rather than the idea? The actuarial glossary defines the notation used above. If something here is wrong or unclear, tell us — these pages get corrected.