Deriving The Semi-Markov Renewal Equation

Why Condition on the First Transition?

In a semi-Markov model, the chance of leaving a state can depend on how long the process has been there. Consequently, occupancy probabilities generally cannot be obtained by treating the current state alone as sufficient for a Markov transition-probability calculation. A useful starting point is instead to separate paths according to whether the process has left its initial state by the time of interest, and, if it has, when and where its first transition occurred.

This conditioning argument produces a renewal equation: occupancy in a target state is the sum of (1) paths that have not yet left the initial state and (2) paths that first enter another state and then continue according to a new semi-Markov process. The equation applies whether the transition-time distributions are continuous or have atoms, provided the endpoint convention is stated and the process is well defined.

Definition: Consider a finite state space. The process starts in state $i$ at time 0, with a new sojourn in $i$ beginning at that time. Let $T$ be the time of its first transition and $J$ the destination state. For $j\ne i$, define the semi-Markov transition kernel $$ Q_{ij}(u)=P(T\le u,\ J=j\mid X(0)=i,\ \text{a new sojourn in }i\text{ starts at }0). $$ The first-sojourn survival function is $$ H_i(u)=P(T>u\mid X(0)=i)=1-\sum_{j\ne i}Q_{ij}(u). $$ The occupancy probability is $p_{ik}(t)=P(X(t)=k\mid X(0)=i,\text{ a new sojourn in }i\text{ starts at }0)$.

Each $Q_{ij}$ is a subdistribution function: its increase over an interval gives the probability that the first transition occurs in that interval and goes to $j$. The sum over destinations may be less than 1 if the sojourn can last forever. In this tutorial, assume $Q_{ij}(0)=0$ for all $j\ne i$, so there is no transition at time zero. Transitions at positive times may have atoms. We use the right-continuous state convention: if a transition occurs at time $u$, the process is in its destination state at $u$. Thus $p_{ik}(0)=1$ when $i=k$ and 0 otherwise under the no-zero-time-transition assumption.

The Renewal Equation

Assume that, on entering a state, the process follows the same state-specific semi-Markov kernel, with its sojourn clock reset. Conditional on the first transition time and destination, its future occupancy probabilities are therefore those of a process starting afresh in that destination state. Also assume that the process is non-explosive: it cannot make infinitely many transitions in a finite time interval. These assumptions make it possible to define the paths and apply the conditioning argument below.

Theorem: Under the conditions just stated, for $t\ge 0$, $$ p_{ik}(t)=\mathbf{1}\{i=k\}H_i(t)+\sum_{j\ne i}\int_{[0,t]}p_{jk}(t-u)\,dQ_{ij}(u). $$ The integral is a Lebesgue–Stieltjes integral, so it includes atoms of $Q_{ij}$, including an atom at the upper endpoint $t$. The first term is occupancy in $i$ when the first transition has not occurred by time $t$; each integral accounts for paths whose first transition is to $j$.

To justify the equation, partition the paths into the disjoint events $T>t$ and $\{T\le t,J=j\}$, one for each $j\ne i$. On $T>t$, the process remains in $i$, contributing $H_i(t)$ if $k=i$, and zero otherwise. Given $T=u$ and $J=j$, the process is in $j$ immediately after the transition and has $t-u$ time units to evolve under the process started afresh in $j$. Its conditional probability of being in $k$ at time $t$ is $p_{jk}(t-u)$. Integrating this conditional probability against the first-transition subdistribution $dQ_{ij}(u)$, then summing over destinations, gives the result.

The endpoint $u=t$ matters when the first-transition distribution has an atom there. The integrand then uses $p_{jk}(0)$, which assigns the process to the destination state at the transition time. For a continuous transition-time distribution, changing a single endpoint does not affect the integral, but that shortcut is not valid for distributions with atoms.

Separate survival from transition.
At time $t$, either the initial sojourn is still in progress, with probability $H_i(t)$, or the first transition has already occurred.

Resolve the first destination.
For each $j\ne i$, use $dQ_{ij}(u)$ for a first transition to $j$ at time $u$; do not combine destinations when the target state matters.

Continue from the new entry.
After that transition, the probability of occupancy in $k$ at time $t$ is $p_{jk}(t-u)$. Sum the integrated contributions and add the survival term when $i=k$.

Worked Example: Competing First Destinations That Are Absorbing

Suppose a process starts in state 0. Its first-sojourn time is exponential with rate $0.5$ per day. At the first transition it enters absorbing state 1 with probability $0.6$, or absorbing state 2 with probability $0.4$. These destination choices are independent of the sojourn time. Find the occupancy probabilities at $t=2$ days.

The first-transition kernels and survival function are $$ Q_{01}(t)=0.6(1-e^{-0.5t}),\qquad Q_{02}(t)=0.4(1-e^{-0.5t}),\qquad H_0(t)=e^{-0.5t}. $$

For target 1, the survival term contributes zero because $0\ne1$. Once the process enters state 1 it stays there, so $p_{11}(v)=1$. It cannot reach state 1 after first entering state 2, so $p_{21}(v)=0$. Therefore $$ p_{01}(2)=\int_{[0,2]}p_{11}(2-u)\,dQ_{01}(u)+\int_{[0,2]}p_{21}(2-u)\,dQ_{02}(u) =Q_{01}(2)=0.6(1-e^{-1})\approx0.3793. $$

Similarly, $p_{02}(2)=Q_{02}(2)=0.4(1-e^{-1})\approx0.2528$. The process remains in state 0 with probability $p_{00}(2)=H_0(2)=e^{-1}\approx0.3679$. These probabilities sum to 1, up to rounding.

The first-transition contribution to target 1 is $Q_{01}(2)$, not $Q_{01}(2)+Q_{02}(2)$. That unrestricted sum is the probability of any first transition by day 2; it does not specify the destination. Even though both destinations are absorbing, only transitions to state 1 contribute to occupancy in state 1.

Using the Equation with Atoms and with Later Transitions

A transition kernel need not have a density. If it has an atom at $u_0>0$, its integral contribution is the atom size multiplied by the corresponding post-transition occupancy probability at the remaining time $t-u_0$. The following example makes the endpoint convention explicit.

Worked Example: A Deterministic Sojourn and an Endpoint Transition

There are two states, 0 and 1. A sojourn in state 0 lasts exactly 1 time unit and is followed by a transition to 1. A sojourn in state 1 lasts exactly 2 time units and is followed by a transition to 0. The process starts in a new sojourn in state 0. Find $p_{00}(2)$ and $p_{00}(3)$.

Here $Q_{01}(u)=\mathbf{1}\{u\ge1\}$ and $H_0(t)=0$ for $t\ge1$. At $t=2$, the renewal equation gives $$ p_{00}(2)=\int_{[0,2]}p_{10}(2-u)\,dQ_{01}(u)=p_{10}(1)=0. $$ The last equality holds because a process newly in state 1 remains there for its first 1 time unit. At time 2 the original process is also in state 1, as expected.

At $t=3$, the same first-transition atom gives $$ p_{00}(3)=\int_{[0,3]}p_{10}(3-u)\,dQ_{01}(u)=p_{10}(2)=1. $$ The transition from state 1 to state 0 occurs exactly 2 time units after entry to state 1, so the process is in state 0 at time 3 under the right-continuous convention. Excluding an atom at the upper endpoint would incorrectly omit this contribution.

The equation is recursive because $p_{jk}(t-u)$ may itself involve later transitions. This is the renewal structure: after each transition, a new sojourn starts, and the same type of conditioning can be applied again. The next example shows a direct path to the target alongside a route through an intermediate state.

Worked Example: A Direct Route and a Route Through an Intermediate State

A process starts in state A. Its first transition time from A is exponential with rate 1 per day; the destination is B with probability $0.4$ and absorbing state C with probability $0.6$, independently of that time. From B, the process waits an exponential time with rate $0.5$ per day and then enters C. Find $p_{AC}(2)$, $p_{AB}(2)$, and $p_{AA}(2)$.

The A-state terms are $H_A(t)=e^{-t}$, $dQ_{AB}(u)=0.4e^{-u}\,du$, and $Q_{AC}(t)=0.6(1-e^{-t})$. From B, the chance of reaching C within $v$ time units is $p_{BC}(v)=1-e^{-0.5v}$. The direct route to C contributes $Q_{AC}(2)$; the route through B contributes $$ \int_0^2 p_{BC}(2-u)\,dQ_{AB}(u) =0.4\int_0^2\left(1-e^{-0.5(2-u)}\right)e^{-u}\,du. $$

Evaluating the integral, $$ 0.4\left[(1-e^{-2})-e^{-1}\int_0^2 e^{-0.5u}\,du\right] =0.4\left[(1-e^{-2})-2e^{-1}(1-e^{-1})\right]\approx0.1598. $$ The direct contribution is $0.6(1-e^{-2})\approx0.5188$, so $p_{AC}(2)\approx0.6786$. The process is in B at time 2 if its first transition went to B and it has not yet left B: $$ p_{AB}(2)=0.4\int_0^2 e^{-0.5(2-u)}e^{-u}\,du =0.8e^{-1}(1-e^{-1})\approx0.1860. $$ Finally, $p_{AA}(2)=H_A(2)=e^{-2}\approx0.1353$. The three probabilities sum to approximately 1.000, providing a useful arithmetic and probability check.

Assumptions, Diagnostics, and Alternatives

The renewal equation is a representation of occupancy probabilities, not by itself an estimation method. Its validity depends on the model used to define the kernels. In particular, the future after entering $j$ must be represented by the same process used to define $p_{jk}$; resetting the sojourn clock alone does not justify ignoring relevant history. The semi-Markov assumption is that, conditional on the current state and its entry into a new sojourn, the distribution of the next sojourn and destination is governed by that state’s kernel, rather than by an unrecorded earlier path feature.

Several checks help identify a mistaken derivation or implementation:

Check the survival term. $H_i(t)$ is the probability of no first transition by $t$, not the probability of a transition. It appears only for target $k=i$.
Keep destinations specific. The integral for destination $j$ uses $dQ_{ij}$. Summing first-transition probabilities without retaining destination information is generally insufficient for a target-specific occupancy probability.
Check total probability. For a finite state space, $\sum_k p_{ik}(t)=1$ when the process remains in the state space. A discrepancy may indicate a missing destination, a survival term counted twice, or an endpoint atom omitted.
Check atom conventions. If a kernel jumps at $u$, include that mass when $u\le t$, and evaluate the post-transition process at $t-u$. A different convention must be stated consistently.
Check the time origin. The equation describes a process starting at entry to $i$. Applying it to someone already partway through a sojourn requires a different residual-time distribution.

A Markov model with transition intensities can offer a simpler product-integral route when the state alone is sufficient to describe the future. In a semi-Markov model, duration-dependent sojourns generally require the renewal representation or a related duration-aware calculation; substituting state-only Markov transition probabilities can give incorrect occupancy results. The renewal equation is also not a closed-form solution in general: its terms may need to be solved recursively or numerically, especially with many states or complicated kernels. Numerical implementations should preserve the kernel’s destination-specific mass and handle atoms and integration boundaries consistently.

Common mistake: “The process has left $i$ by time $t$, so the probability of any first transition is the contribution to occupancy in target $k$.” This confuses leaving the initial state with reaching a particular target. The correction is to retain the destination: the first-transition term for target $k$ is $\sum_{j\ne i}\int_{[0,t]}p_{jk}(t-u)\,dQ_{ij}(u)$. If $j$ is absorbing, its contribution is $Q_{ij}(t)$ only when $j=k$; otherwise it contributes zero to occupancy in $k$.

Check Your Understanding

Answer each question using the conditioning argument and the endpoint convention above. Short solutions follow.

In the renewal equation, why is the survival term multiplied by $\mathbf{1}\{i=k\}$?
Suppose $Q_{ij}$ has an atom of size 0.2 at time $u=1$. What contribution does this atom make to the integral for target $k$ at time $t=3$?
State the correct first-transition contribution to target 1 when states 1 and 2 are both absorbing and are possible destinations from state 0.
Why does the renewal equation use $p_{jk}(t-u)$ after a transition to $j$ at time $u$?

Solutions. (1) If no first transition occurs by $t$, the process remains in its initial state $i$, so this event contributes only when $k=i$. (2) The atom contributes $0.2p_{jk}(2)$, since the remaining time is $3-1=2$. (3) The contribution is $Q_{01}(t)$; transitions to absorbing state 2 do not occupy state 1. (4) At time $u$, entry to $j$ begins a new sojourn, so the conditional probability of occupying $k$ at time $t$ is the occupancy probability from $j$ over the remaining $t-u$ time units.

Deriving The Semi-Markov Renewal Equation

What You'll Learn