Markov Chain

Markov Chain as the Probability Model Behind Markov Cohort Models

Every Markov cohort model used in economic evaluation runs on a Markov chain, made up of health states, a starting distribution and the probabilities of moving between states each cycle. Treated as a mathematical object, the chain is separate from the costs, utilities and strategies that turn it into a Markov model for cost-effectiveness analysis. In the older medical decision-making literature "Markov chain" means a constant-probability process, which is not its meaning in probability theory. For an absorbing chain, the fundamental matrix gives expected time to absorption, which is life expectancy in the model. Markov chain Monte Carlo, a general simulation method used mainly for Bayesian estimation, has its own page.

The Markov property in a health state model

A Markov chain follows a cohort member who occupies exactly one of a finite set of states at each cycle boundary and moves between them at random. What makes it Markov is that the next state depends on the current state and on nothing earlier in the path. In symbols, the Markov property reads as follows.

$$\Pr(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = \Pr(X_{t+1} = j \mid X_t = i) = p_{ij}(t)$$

where $X_t$ is the state occupied at cycle $t$, $i$ and $j$ index the states, and $p_{ij}(t)$ is the transition probability from state $i$ to state $j$ in cycle $t$. Sonnenberg and Beck, in their practical guide to Markov models in medical decision making, put the consequence plainly. The process has no memory for earlier cycles, so everyone in a given state has the same prognosis whatever their history. A chain is fully defined by the distribution among the starting states and the probabilities of the allowed transitions, which for constant probabilities form an $n \times n$ transition matrix.

The property describes the model's states, and says nothing about whether the disease has a history. Sonnenberg and Beck noted that the assumption is not followed strictly in medical problems but is needed to model prognosis with a finite number of states, which is why the choice of states carries so much weight; the Markov assumption page covers how to judge it.

Two meanings of "Markov chain"

The term is used in two ways, and the difference matters when reading methods papers. In probability theory the general definition requires only the Markov property; many texts, Grinstead and Snell among them, then define or study only the time-homogeneous case, in which $p_{ij}(t) = p_{ij}$ for every cycle. Durrett's graduate probability text, for example, restricts its Markov chain chapter to temporally homogeneous chains and in an exercise describes a temporally inhomogeneous Markov chain. On this usage a chain whose mortality rises with age is still a Markov chain, a time-inhomogeneous model in the site's terms.

The medical decision-making literature drew the line differently. Sonnenberg and Beck called the general process, in which transition probabilities may change over time, a Markov process, and reserved "Markov chain" for the special type with constant transition probabilities, the case now called a time-homogeneous model. They tied the term to a practical advantage, since a Markov chain with an absorbing state can be solved exactly by matrix algebra, so in older sources the term usually signals that solution. More recent tutorials state the condition directly; Alarid-Escudero and colleagues describe the simplest cohort models as time-independent (time-homogeneous). Jones, Epstein and García-Mochón use "chain" for discrete-time and continuous-time processes alike.

This page follows the probability-theory usage and says "time-homogeneous" wherever constancy matters.

From chain to cost-effectiveness model

The chain and the model built on it answer different questions. The chain says where the cohort is expected to be at each cycle; the Markov model adds what that occupancy is worth, through costs and utilities, discounting, a time horizon and a separate chain for each strategy. Sonnenberg and Beck described three ways to evaluate the process, of which only the simulations allow probabilities that change over time; the usual one is cohort simulation.

Absorbing chains and expected time to absorption

Chains in lifetime health economic models are usually absorbing. In Grinstead and Snell's definition, a state is absorbing if it cannot be left, and a chain is absorbing if every state can reach an absorbing state, not necessarily in one step; the other states are transient. With death as the absorbing state, every living state is a transient state. For a time-homogeneous chain, ordering the transient states first gives the canonical form shown below.

$$P = \begin{pmatrix} Q & R \\ \mathbf{0} & I \end{pmatrix}$$

where $Q$ holds the transition probabilities among transient states, $R$ those from transient to absorbing states, $\mathbf{0}$ is a block of zeros and $I$ is an identity matrix for the absorbing states. Absorption is certain, so $Q^{n}$ shrinks towards zero as $n$ grows, and for the same time-homogeneous chain the fundamental matrix below collects the expected visits.

$$N = (I - Q)^{-1} = I + Q + Q^{2} + \cdots, \qquad \mathbf{t} = N \mathbf{c}, \qquad B = N R$$

where $N$ is the fundamental matrix, whose entry $n_{ij}$ is the expected number of cycles spent in transient state $j$ by a chain starting in transient state $i$ (the starting cycle counted), $I$ is here the identity matrix of the size of $Q$, $\mathbf{t}$ is the vector of expected cycles before absorption from each starting state, $\mathbf{c}$ is a column vector of ones, and $B$ gives the probability of ending in each absorbing state. $B$ matters when a model keeps several death states, which Sonnenberg and Beck allow when causes of death are tracked.

When death is the only absorbing state, $\mathbf{t}$ is life expectancy in cycles, counted at the start of each cycle, so Sonnenberg and Beck subtract half a cycle from the starting state.

Worked example with a three-state chain and recovery

The figures below are illustrative. A cohort moves each year between Well and Ill, with Dead absorbing. Unlike the progressive examples on neighbouring pages, people can recover, so they can fall ill more than once.

1. Split the matrix. $Q$ has rows (0.85, 0.10) and (0.20, 0.70), and $R$ is the column (0.05, 0.10) of death probabilities.

2. Invert $I - Q$. $I - Q$ has rows (0.15, −0.10) and (−0.20, 0.30), so $\det(I - Q) = 0.15 \times 0.30 - 0.10 \times 0.20 = 0.025$. Swapping the diagonal entries, changing the sign of the others and dividing by the determinant gives the inverse below.

$$N = \frac{1}{0.025} \begin{pmatrix} 0.30 & 0.10 \\ 0.20 & 0.15 \end{pmatrix} = \begin{pmatrix} 12 & 4 \\ 8 & 6 \end{pmatrix}$$

where the rows are the starting states Well and Ill, and the columns are expected cycles in Well and in Ill.

3. Sum the rows. Expected cycles before absorption are $t_{\mathrm{Well}} = 12 + 4 = 16$ and $t_{\mathrm{Ill}} = 8 + 6 = 14$. With one absorbing state, $B = NR$ is 1 from both, since 12 × 0.05 + 4 × 0.10 = 1 and 8 × 0.05 + 6 × 0.10 = 1.

4. Interpret. The 4 years Ill from a Well start decompose into episodes. A person spends 12 expected years at risk in Well, and 10% fall ill each year, giving 12 × 0.10 = 1.2 expected episodes; each episode lasts 1/(1 − 0.70) = 3.33 years on average, and 1.2 × 3.33 = 4. The probability of ever falling ill from Well is 0.10/(0.10 + 0.05) = 0.67, or two in three. Recovery shortens time Ill. If the 0.20 recovery probability were added to staying Ill, giving an Ill row of (0, 0.90, 0.10), a Well start would spend 6.67 years Ill. Subtracting half a cycle gives life expectancy of 15.5 years from Well and 13.5 years from Ill. With illustrative utilities of 0.85 for Well and 0.60 for Ill, quality-adjusted life expectancy from Well is 12 × 0.85 + 4 × 0.60 = 12.6, or 12.175 after subtracting 0.5 × 0.85.

5. Check and discount. A cohort run from Well for 3,000 cycles, counted at the start of each cycle, gives 12 years in Well and 4 in Ill. Sonnenberg and Beck wrote that discounting cannot be used with the fundamental matrix because of its time variance, but a geometric discount multiplies every cycle by the same factor, so it folds into $Q$. Counting membership at the start of cycle $k$ and discounting it by the factor $(1 + r)^{-k}$, so that the first cycle is undiscounted, gives $(I - Q/(1 + r))^{-1}$, where $r$ is the annual discount rate; with cycles of $\Delta$ years the factor per cycle is $(1 + r)^{\Delta}$. At an illustrative 3.5%, the Well row of $(I - Q/1.035)^{-1}$ sums to 10.73 discounted years without a half-cycle correction, matching a discounted cohort run, and to 10.23 years with it.

6. Long run. The proportion alive from Well is 0.95 after one year, 0.535 after 10 years and 0.036 after 50, and high powers of $P$ send every row towards (0, 0, 1).

The long run of an absorbing chain

A stationary distribution is a set of state proportions that one more cycle of a time-homogeneous chain leaves unchanged. For an absorbing chain the long-run distribution is everyone absorbed, (0, 0, 1) in the example, so the informative quantities in a lifetime model are $N$ and $\mathbf{t}$. Stationary distributions of chains without death are covered on the steady state page, and Markov chain Monte Carlo builds a chain whose stationary distribution is a chosen target.

Continuous-time chains and generator matrices

Jones, Epstein and García-Mochón distinguish discrete-time chains, described by probabilities, from continuous-time chains, described by rates, and note that medical decision models are usually analysed in discrete periods because that is more practical in spreadsheets. A time-homogeneous continuous-time chain is specified by a constant rate matrix, or generator, from which the cycle matrix follows as a matrix exponential; the transition matrix page, which writes the generator as $Q$, covers the conversion.

When the Markov property fails

The property fails whenever two people in the same state face different futures because of something the state does not record, and the usual fix is to enlarge the state space until the chain is Markov again. The two common fixes affect the chain differently. Tunnel states, which Alarid-Escudero and colleagues use for state-residence time dependence, keep the expanded matrix time-homogeneous when the other probabilities are constant, so the fundamental matrix still applies. Probabilities that change with age make the chain time-inhomogeneous, unless age or cycle is itself written into the states.

Common misreadings

Four errors recur. One is reading "Markov chain" as always meaning constant probabilities, or never, without checking the source's convention. Another is treating the fundamental matrix as exact for the disease rather than for the discrete-time chain. A third is expecting a lifetime model with death to settle into a meaningful steady state. The last is reading the Markov property as a claim that illness has no history, when it claims only that the chosen states carry the history that matters. A hidden Markov model, whose states are not observed, is a different object.

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
• Durrett R. Probability: Theory and Examples. 5th ed. Cambridge: Cambridge University Press; 2019. Chapter 5.
• Grinstead CM, Snell JL. Introduction to Probability. 2nd rev. ed. Providence, RI: American Mathematical Society; 1997. Chapter 11.
• 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
• 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