Tutorials › Competing Risks and Multi-State Models › Transition Probabilities From A Semi-Markov Kernel

Home  /  Tutorials  /  Semi-Markov and Non-Markov Models

Semi-Markov and Non-Markov Models · Tutorial 322 of 699

Transition Probabilities From A Semi-Markov Kernel

Learn how a semi-Markov kernel determines state occupancy probabilities over time, including how to compute them by summing over all possible transition paths.

Advanced 12 min read

What You'll Learn

  • Distinguish the next-transition kernel from a state-occupancy transition probability
  • Derive the renewal equation by conditioning on the first transition
  • Expand the renewal equation as a sum over paths and holding-time distributions
  • Compute probabilities in a discrete two-state semi-Markov model
  • Recognize when exponential holding times permit a simpler Markov calculation
  • Check probability conservation and identify common modeling and computation errors

From the Next Transition to the State at Time \(t\)

A semi-Markov kernel describes what happens at the next transition: which state is entered and how long the process spends in the current state before that transition. A transition probability asks a different question: which state is occupied at a specified time \(t\)? Answering it requires accounting not only for the first transition, but also for every sequence of later transitions that can occur before \(t\).

The key operation is conditioning on the first transition. If no transition has occurred by \(t\), the process is still in its starting state. Otherwise, after the first transition, the probability of occupying a target state is the corresponding probability for the remaining time, starting from the newly entered state. Repeating this argument generates a sum over possible paths.

Definition: Let \(J_n\) be the state occupied immediately after the \(n\)th transition, and let \(T_{n+1}\) be the time spent in state \(J_n\) before the next transition. For distinct states \(i\) and \(k\), the semi-Markov kernel is $$ Q_{ik}(u)=P(J_{n+1}=k,\ T_{n+1}\leq u\mid J_n=i). $$ Thus \(Q_{ik}\) is a joint distribution for the next destination and the time of the next transition; it is not generally a transition probability at time \(u\). Define \(H_i(u)=\sum_{k\ne i}Q_{ik}(u)\) and \(\bar H_i(u)=1-H_i(u)\). Then \(\bar H_i(u)\) is the probability of no transition out of \(i\) by time \(u\). For an absorbing state, all outgoing \(Q_{ik}\) are zero and \(\bar H_i(u)=1\).

Write \(p_{ij}(t)=P(X(t)=j\mid X(0)=i,\ J_0=i)\), where the process starts in state \(i\) at time zero, at the beginning of a new sojourn. This starting-age condition matters: the kernel specifies a new sojourn, not the remaining time for someone already partway through one. Here the model is time-homogeneous, and each new transition follows the same kernel conditional on the state entered. We assume the kernel is proper, holding times are positive, and infinitely many transitions cannot occur in a finite time (nonexplosion).

The First-Transition Renewal Equation

Condition on whether the first transition out of \(i\) has occurred by time \(t\). If it has not, the process is in \(i\), contributing \(\bar H_i(t)\) when \(j=i\). If the first transition occurs at time \(u\) and enters \(k\), the process then has \(t-u\) time units in which to reach \(j\). The kernel increment \(dQ_{ik}(u)\) gives the probability of that destination and transition time in an infinitesimal interval around \(u\). In distributional form, including kernels with discrete atoms, this yields:

$$ p_{ij}(t)=\mathbf{1}\{i=j\}\bar H_i(t) +\sum_{k\ne i}\int_{[0,t]}p_{kj}(t-u)\,dQ_{ik}(u). $$

The integral is a Lebesgue–Stieltjes integral, so it also applies when holding times have point masses. If \(Q_{ik}\) has a density \(q_{ik}\), then \(dQ_{ik}(u)=q_{ik}(u)\,du\). Importantly, the kernel already gives the joint distribution of destination and holding time. In general one must not replace it by the product of a destination probability and a holding-time distribution unless that factorization is justified by the model.

This equation is a renewal equation: after the first transition, the same state-occupancy calculation begins again from the newly entered state. Iterating it gives the contribution of paths with one transition, two transitions, and so on. For a path \(i_0=i,i_1,\ldots,i_n=j\), its contribution is the probability of those successive destination-and-duration pairs, multiplied by the probability of remaining in the final state for the time left over.

$$ \sum_{i_1,\ldots,i_{n-1}} \int_{\substack{u_1,\ldots,u_n>0\\u_1+\cdots+u_n\leq t}} \left\{\prod_{r=1}^{n}dQ_{i_{r-1},i_r}(u_r)\right\} \bar H_{i_n}\!\left(t-\sum_{r=1}^{n}u_r\right). $$

The sum is over allowed intermediate states, with \(i_0=i\) and \(i_n=j\). For zero transitions, the contribution is \(\mathbf{1}\{i=j\}\bar H_i(t)\). Adding the contributions for all possible numbers of transitions gives \(p_{ij}(t)\). Nonexplosion ensures that the process cannot make infinitely many transitions by time \(t\); the path expansion can therefore be interpreted as a sum of mutually exclusive histories. For calculations, one may either solve the renewal equations directly or evaluate enough terms of this expansion to meet a stated numerical tolerance.

Worked Examples

Worked Example: First Transitions to Two Absorbing States

Suppose the process starts in state \(A\). It leaves \(A\) at constant cause-specific rates \(0.2\) and \(0.3\) per month, entering absorbing states \(B\) and \(C\), respectively. The total rate of leaving \(A\) is \(0.5\) per month. The assumptions are constant rates during the sojourn and no return transitions from \(B\) or \(C\). Find the state probabilities after two months.

The survival probability in \(A\) is \(\bar H_A(t)=e^{-0.5t}\). The density for a first transition to \(B\) at time \(u\) is \(0.2e^{-0.5u}\): the process must remain in \(A\) until \(u\), then leave for \(B\). Since \(B\) is absorbing, entering it by time \(t\) means occupying it at time \(t\). Thus

$$ p_{AB}(2)=\int_0^2 0.2e^{-0.5u}\,du =0.4(1-e^{-1}) =0.2528. $$

Similarly, \(p_{AC}(2)=0.6(1-e^{-1})=0.3793\), while \(p_{AA}(2)=e^{-1}=0.3679\). The three probabilities sum to \(0.2528+0.3793+0.3679=1.0000\). This example has no paths with multiple transitions, but it makes clear why the probabilities of entering \(B\) and \(C\) are integrals of destination-specific transition densities, not simply the total probability of leaving \(A\).

Worked Example: Enumerating Paths in a Discrete Two-State Model

Consider two states, 0 and 1, with transitions alternating between them. Each sojourn in state 0 lasts one time unit with probability \(0.5\) or two time units with probability \(0.5\). Each sojourn in state 1 lasts one time unit with probability \(0.5\) or three time units with probability \(0.5\). Successive sojourns follow these distributions independently conditional on the state. Starting in state 0, calculate \(p_{01}(2)\) and \(p_{01}(3)\). Define the process to be in its post-transition state at an exact transition time.

At time 2, there are two possibilities for the first sojourn. If it lasts two units (probability \(0.5\)), the process enters state 1 at time 2, so it is in state 1 at that time. If it lasts one unit (probability \(0.5\)), the process enters state 1 at time 1. Its next sojourn lasts three units with probability \(0.5\), leaving it in state 1 at time 2, or one unit with probability \(0.5\), returning it to state 0 exactly at time 2. Therefore

$$ p_{01}(2)=0.5+(0.5)(0.5)=0.75. $$

At time 3, enumerate the paths. If the first sojourn lasts two units and the sojourn in state 1 lasts three units, the process is in state 1; this has probability \((0.5)(0.5)=0.25\). If the first sojourn lasts one unit and the sojourn in state 1 lasts three units, the process is also in state 1 at time 3, with probability \(0.25\). If those first two sojourns both last one unit, the process returns to state 0 at time 2. A one-unit sojourn there leads to state 1 at time 3, with probability \((0.5)^3=0.125\). A two-unit sojourn leaves it in state 0 at time 3, also with probability \(0.125\). Hence \(p_{01}(3)=0.25+0.25+0.125=0.625\), and \(p_{00}(3)=0.125+0.25=0.375\). The probabilities sum to one. The calculation requires paths with up to two transitions by time 3; the holding-time distributions are not exponential, so the probabilities cannot in general be obtained from a constant transition-rate matrix.

Worked Example: A Two-State Exponential Special Case

Now suppose transitions alternate between states 0 and 1, with exponential sojourn times at rates \(\lambda_0=0.4\) and \(\lambda_1=0.2\) per month. These are valid semi-Markov kernels, and the exponential assumption also makes the state process Markov. Starting in state 0, find the probability of state 1 after three months.

Over a short interval, the probability flow into state 1 is approximately \(\lambda_0p_{00}(t)\) per month, and the flow out is \(\lambda_1p_{01}(t)\) per month. Since \(p_{00}(t)=1-p_{01}(t)\), the forward equation is

$$ \frac{d}{dt}p_{01}(t) =\lambda_0\{1-p_{01}(t)\}-\lambda_1p_{01}(t) =\lambda_0-(\lambda_0+\lambda_1)p_{01}(t), \qquad p_{01}(0)=0. $$

Solving this linear differential equation gives

$$ p_{01}(t)=\frac{\lambda_0}{\lambda_0+\lambda_1} \left(1-e^{-(\lambda_0+\lambda_1)t}\right). $$

At three months, the calculation is \(0.4/0.6\{1-e^{-0.6(3)}\}=(2/3)(1-e^{-1.8})=0.5565\). Thus the probability of occupying state 1 at three months, starting in state 0, is about \(0.557\). This concise formula relies on exponential holding times; it is not a general formula for a semi-Markov model.

Computing and Checking the Probabilities

For a small state space, write the renewal equation for each starting and target state, then solve the coupled equations. With continuous holding-time densities, numerical quadrature can approximate the integrals. With discrete kernels, sum over their possible duration values. For either approach, a practical calculation can be organized as follows:

1
Specify the kernel.
List each allowed next state and its joint holding-time distribution, including any atoms or absorbing states.
2
Include the no-transition term.
For a process started in \(i\), use \(\mathbf{1}\{i=j\}\bar H_i(t)\) for remaining in the initial state throughout the interval.
3
Add paths after the first transition.
Integrate over its time and destination, then apply the state-occupancy probability for the remaining time. Continue for later transitions.
4
Check the result.
For a closed model, verify that probabilities are nonnegative and \(\sum_j p_{ij}(t)=1\) for every starting state \(i\).

If the path expansion is truncated, report or assess the omitted probability mass rather than assuming it is negligible. Increasing the maximum number of transitions should stabilize the estimates, and a numerical integration grid should be refined to check sensitivity to discretization. If row sums are below one, possible causes include omitted destinations, omitted paths, or numerical integration error; row sums above one may indicate double-counted paths or incorrect kernel normalization.

The renewal calculation is distinct from the product-integral approach used for transition intensities. A product integral is appropriate when the model is specified through transition intensities; a semi-Markov kernel directly specifies next-transition time and destination and generally requires renewal calculations. When exponential holding times and state sufficiency hold, the semi-Markov calculation simplifies to the Markov transition-probability calculation. The general kernel method is more flexible, but its path sums or integral equations can be computationally demanding, especially with many states or long time horizons.

Common pitfall: Treating \(Q_{ik}(t)\) as \(p_{ik}(t)\). \(Q_{ik}(t)\) is the probability that the next transition from \(i\) is to \(k\) by time \(t\); it does not include paths that first enter another state and later reach \(k\). The correction is to condition on the first transition and include the subsequent state-occupancy probability, as in the renewal equation.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

  1. What event does \(Q_{ik}(t)\) describe, and how does it differ from \(p_{ik}(t)\)?
  2. A process starts in state \(A\), leaves at rate \(0.1\) per day, and can only enter absorbing state \(B\). What are \(p_{AA}(4)\) and \(p_{AB}(4)\)?
  3. Why does the renewal equation include a no-transition term when \(i=j\)?
  4. In a closed model, what two basic checks should be applied to the computed row of state-occupancy probabilities?

Solutions. (1) \(Q_{ik}(t)\) is the probability that the next transition from \(i\) enters \(k\) within \(t\); \(p_{ik}(t)\) is the probability of occupying \(k\) at time \(t\), including paths with intervening transitions. (2) The probability of no departure by day 4 is \(e^{-0.1(4)}=e^{-0.4}=0.6703\), so \(p_{AA}(4)=0.6703\) and \(p_{AB}(4)=1-e^{-0.4}=0.3297\). (3) If the process has not left its starting state by \(t\), it remains in that state; this contributes \(\bar H_i(t)\) to \(p_{ii}(t)\). (4) Each probability should be nonnegative, and the probabilities across all states should sum to one, up to numerical error.

Previous

Next

Back to Tutorials
Clinical Biostats