Transition Matrix

Transition Matrix for Cohort Propagation and Cycle Length Changes in Markov Models

In a Markov model used for economic evaluation, the transition matrix is what moves the cohort forward in time, so every cost and QALY the model reports rests on the state occupancy it produces. Its entries are transition probabilities, whose estimation is a separate topic. The matrix as a whole has its own rules for rows, for cohort propagation and for building it from rates when a state has competing exits, and changing the cycle length needs a matrix root or logarithm rather than a cell-by-cell formula. An illustrative example below runs a three-state cohort for three cycles and converts its annual matrix to six-month cycles, first incorrectly and then correctly.

Rows, columns and the row-sum rule

A cohort model with $K$ mutually exclusive and collectively exhaustive health states needs a $K \times K$ matrix for each cycle. Under the usual convention in health economic models, rows are the states at the start of a cycle and columns the states at its end. Each row therefore accounts for everyone who starts in that state.

$$p_{ij} \ge 0 \quad \text{for all } i, j, \qquad \sum_{j=1}^{K} p_{ij} = 1 \quad \text{for each } i$$

where $p_{ij}$ is the probability that a member of the cohort in state $i$ at the start of the cycle is in state $j$ at its end, and $K$ is the number of states. Sonnenberg and Beck, who called this array the P matrix, noted that probabilities for disallowed transitions are zero; these structural zeros encode the model's transition structure, such as no recovery from a progressed cancer. An absorbing state, usually death, has 1 on the diagonal and 0 elsewhere in its row. Some texts outside health economics put starting states in columns, which reverses the multiplication, so a model should state its orientation.

Constant and cycle-dependent matrices

A model can use one matrix for every cycle or a different matrix in each cycle. Sonnenberg and Beck called the constant case a Markov chain (a time-homogeneous chain in current usage) and observed that age-specific mortality had led modellers to rely more on probabilities that vary over time. The tutorial on time-dependent cohort models by Alarid-Escudero and colleagues separates simulation-time dependence, where the matrix changes with time since the start of the model ($P_1, P_2, \dots$), from state-residence time dependence, where risk changes with time already spent in a state.

The second kind is handled with tunnel states, which change the shape of the matrix rather than its values. Sonnenberg and Beck described them as temporary states visited only in a fixed sequence, so each one adds a row and a column, and its row sends the cohort onward rather than letting it stay. Every tunnel state enlarges the matrix, which limits how much history a cohort model can carry in practice.

Propagating the cohort one cycle at a time

Multiplying the row vector of state proportions by the matrix moves the cohort forward one cycle. Repeating the step builds the cohort trace. With a constant matrix the $n$-cycle result is a matrix power.

$$\mathbf{m}_{t+1} = \mathbf{m}_t P_t, \qquad \mathbf{m}_n = \mathbf{m}_0 P^{n} \quad \text{when } P_t = P \text{ for every cycle}$$

where $\mathbf{m}_t$ is the row vector of proportions in each state at the end of cycle $t$, $P_t$ is the matrix for cycle $t$, and the entries of $P^{n}$ are $n$-cycle transition probabilities summed over every pathway, including those through intermediate states. Counting rewards within a cycle belongs to cohort simulation and half-cycle correction, and leaves the matrix unchanged.

Building a matrix from rates when a state has competing exits

When evidence gives probabilities over the model's own interval, each row is filled directly, with the diagonal as one minus the exits. When evidence gives rates, the coherent route for a multistate model builds a rate matrix and converts it in one step. Jones, Epstein and García-Mochón set out the relationship as follows.

$$P(\Delta) = \exp(\Delta Q) = \sum_{r=0}^{\infty} \frac{(\Delta Q)^{r}}{r!}$$

where $Q$ is the rate (generator) matrix, whose off-diagonal entries $q_{ij}$ are constant transition rates from state $i$ to state $j$ and whose diagonal entries make each row of $Q$ sum to zero, $\Delta$ is the cycle length in the time unit of the rates, and $P(\Delta)$ is the one-cycle matrix. They note that applying the simple formula $p = 1 - e^{-r t}$ to each rate separately is always wrong when a state has competing exits, because exits compete and a person can have more than one event in a cycle, such as healthy to ill to dead; the exponential captures such sequences.

The transition probability page gives a proportional split of competing exits for absorbing exits and notes that it is not universal; the worked example below shows the size of the error when a destination has onward transitions. Numerical software such as the msm package for R can do the conversion, and Jones and colleagues derive algebraic formulas for spreadsheets, although their procedure cannot be used in some cases, for example when the eigenvalues are very close together or when several backward transitions have no algebraic solution.

Changing the cycle length with roots and logarithms, not scaled cells

An annual matrix often has to become monthly or six-monthly. The ISPOR-SMDM report on state-transition modelling recommends converting probabilities between time units through rates. Chhatwal, Jayasuriya and Elbasha showed that the usual way of doing this, converting each annual probability to a rate and back separately, applies only to two-state models; in their three-state example it produced a different Markov chain. Assuming the same shorter-cycle matrix applies throughout the original interval, the correct conversion to cycles $n$ times shorter takes the $n$th root of the whole matrix by eigendecomposition.

$$P^{1/n} = V D^{1/n} V^{-1}$$

where $V$ is the matrix of eigenvectors of $P$, $D$ is the diagonal matrix of its eigenvalues, $D^{1/n}$ takes the $n$th root of each eigenvalue, and $P^{1/n}$ is the shorter-cycle matrix, which returns $P$ when raised to the power $n$. Equivalently, the matrix logarithm of $P$, when it exists, gives a rate matrix, which is divided by $n$ and exponentiated.

The root is not always a valid matrix. Chhatwal and colleagues caution that not every matrix is diagonalisable and that a root may contain complex or negative entries; in their HIV example one monthly probability was minus 0.0053. They list necessary conditions for $P$ to be embeddable, that is, for a valid rate matrix to exist, namely a positive determinant no greater than the product of the diagonal entries, and no zero entry for a transition that is reachable through other states. The authors note that these conditions may also be necessary for the root method to work. When the root is not stochastic, they approximate it with the closest stochastic matrix. Lengthening the cycle to a whole multiple is simpler, since integer powers of a stochastic matrix stay stochastic. In their liver disease example run on monthly cycles, cell-by-cell conversion gave lifetime errors, against the matrix root, of minus 42% in cumulative incidence of liver cancer, minus 19% in total costs and 0.9% in QALYs.

Worked example of a three-state cohort and a six-month conversion

The figures below are illustrative. A cohort with advanced cancer starts progression-free (PF). Each year, 70% remain progression-free, 20% progress (PD) and 10% die; of those who have progressed, 60% remain alive and 40% die. Death is absorbing and there is no return from PD to PF.

1. Three annual cycles. Starting from $\mathbf{m}_0 = (1, 0, 0)$, each row is the previous row times the matrix; for example, PD in cycle 3 is $m_{\mathrm{PD}} = 0.49 \times 0.20 + 0.26 \times 0.60 = 0.254$.

2. An incorrect six-month matrix. Converting each annual probability $p$ separately to $p_{6\mathrm{m}} = 1 - (1 - p)^{1/2}$ gives 0.105573 for PF to PD, 0.051317 for PF to Dead and 0.225403 for PD to Dead, with diagonals of 0.843110 and 0.774597 as remainders. Two cycles should return the annual PF row, but squaring gives $s_{11} = 0.843110^{2} = 0.710834$ for staying in PF and $s_{12} = 0.843110 \times 0.105573 + 0.105573 \times 0.774597 = 0.170786$ for PF to PD, leaving 0.118380 for PF to Dead. Per 1,000 people the model has about 711 progression-free, 171 progressed and 118 dead after one year, against 700, 200 and 100 in the evidence.

3. The correct six-month matrix. The matrix is upper triangular, so its eigenvalues are its diagonal entries, 0.70, 0.60 and 1, and the square root $R$ has diagonal entries $r_{11} = \sqrt{0.70} = 0.836660$, $r_{22} = \sqrt{0.60} = 0.774597$ and 1. The PF to PD entry of $R \times R$ is $r_{12}(r_{11} + r_{22})$, which must equal 0.20, as follows.

$$r_{12} = \frac{0.20}{0.836660 + 0.774597} = \frac{0.20}{1.611257} = 0.124127$$

where $r_{12}$ is the six-month probability of moving from PF to PD. The PD row has one exit to an absorbing state, so $r_{23} = 1 - 0.774597 = 0.225403$, as in step 2, and the row-sum rule gives $r_{13} = 1 - 0.836660 - 0.124127 = 0.039213$. Squaring $R$ returns the annual matrix; the PF to Dead entry, for instance, is $r_{11} r_{13} + r_{12} r_{23} + r_{13} = 0.836660 \times 0.039213 + 0.124127 \times 0.225403 + 0.039213 = 0.100000$. The matrix logarithm has non-negative annual rates of 0.308 from PF to PD, 0.048 from PF to Dead and 0.511 from PD to Dead, so $P$ is embeddable and exponentiating half of it gives the same $R$.

4. Interpretation. The annual 10% death probability from PF includes people who progressed and then died within the year. The cell-by-cell method counts all of it as direct death, so it sets six-month death from PF too high (0.0513 against 0.0392) and progression too low (0.1056 against 0.1241). After six six-month cycles, three years, it has 0.221 in PD and 0.420 dead, against 0.254 and 0.403 in the annual model, understating time in the progressed state and its costs. Splitting the PF exits in proportion to the observed annual exits (0.20 and 0.10) gets PF right but still gives 0.175 in PD and 0.125 dead at one year, because it treats PD as absorbing.

Representing uncertainty with Dirichlet rows

In probabilistic sensitivity analysis the matrix must stay valid in every iteration, so the exits from a state are sampled together, usually from a Dirichlet distribution as Briggs, Ades and Price proposed. Each starting state with several destinations gets its own Dirichlet row, absorbing rows stay fixed and structural zeros stay zero; fitting and sampling are covered on the Dirichlet page.

Cycle-length conversion interacts with sampling. If the evidence gives an annual matrix and the model runs on shorter cycles, the root has to be taken for each sampled matrix, not once for the mean. Chhatwal and colleagues found that whether eigendecomposition gives a valid root depends on the probability values as well as the model structure, so the check for negative or complex entries belongs inside the sampling loop.

Checks before a matrix enters the model

Row sums and ranges are the basic checks, covered with the errors below. Two further checks are specific to a matrix that has been converted or that drives a long trace.

1. Conversions reproduce their source. A converted matrix raised to the right power returns the original matrix.
2. The trace is conserved and predictable. Proportions add to one in every cycle, and the ISPOR-SMDM report suggests setting parameters so the trace can be predicted, for example so that no one enters a given state.

Where the matrix sits among neighbouring concepts

Several pages describe parts of the same machinery, and the split between them is deliberate. Single entries, hazard ratios and survival curves belong to transition probability, the whole model to Markov model, and running it to cohort simulation; particular rows belong to absorbing state, tunnel state and Dirichlet distribution. What applies to the matrix as a whole, namely orientation and row rules, propagation, conversion of a full matrix between rates and probabilities, and the matrix root, is kept together here.

Where transition matrices go wrong

The basic errors are rows that do not sum to one within rounding tolerance, entries outside zero and one (including those produced by roots, logarithms or sampling), absorbing rows without 1 on the diagonal, disallowed transitions that are not zero, and living states with no route to death. Changing cycle length cell by cell is an error that row-sum checks miss, because, as the worked example shows, every row of the incorrect matrix still sums to one. Filling a row from separately sourced probabilities with the diagonal as the remainder can hide a negative diagonal or exits that describe different populations or intervals. Using one constant matrix when risk changes with age or time in a state calls for cycle-specific matrices or tunnel states instead.

Some limits no check repairs. The matrix describes average movement under the Markov property and carries no costs or utilities. A valid root need not be unique, and Chhatwal and colleagues note that different roots can lead to different conclusions about cost-effectiveness. Coherent arithmetic does not show that the states and evidence describe the disease well enough for the decision.

Sources

• Alarid-Escudero F, Krijkamp E, Enns EA, Yang A, Hunink MGM, Pechlivanoglou P, Jalal H. A tutorial on time-dependent cohort state-transition models in R using a cost-effectiveness analysis example. Medical Decision Making. 2023;43(1):21-41. https://doi.org/10.1177/0272989X221121747
• Briggs AH, Ades AE, Price MJ. Probabilistic sensitivity analysis for decision trees with multiple branches: use of the Dirichlet distribution in a Bayesian framework. Medical Decision Making. 2003;23(4):341-350. https://doi.org/10.1177/0272989X03255922
• Chhatwal J, Jayasuriya S, Elbasha EH. Changing cycle lengths in state-transition models: challenges and solutions. Medical Decision Making. 2016;36(8):952-964. https://doi.org/10.1177/0272989X16656165
• Jones E, Epstein D, García-Mochón L. A procedure for deriving formulas to convert transition rates to probabilities for multistate Markov models. Medical Decision Making. 2017;37(7):779-789. https://doi.org/10.1177/0272989X17696997
• Siebert U, Alagoz O, Bayoumi AM, Jahn B, Owens DK, Cohen DJ, Kuntz KM. State-transition modeling: a report of the ISPOR-SMDM Modeling Good Research Practices Task Force-3. Value in Health. 2012;15(6):812-820. https://doi.org/10.1016/j.jval.2012.06.014
• Sonnenberg FA, Beck JR. Markov models in medical decision making: a practical guide. Medical Decision Making. 1993;13(4):322-338. https://doi.org/10.1177/0272989X9301300409