Semi-Markov Transition Kernels

Why a Transition Kernel Is Joint

A transition probability over a fixed horizon answers where a process is at that horizon. A semi-Markov transition kernel describes a different piece of the path: which state is reached at the next transition and how long it takes to get there. Keeping destination and waiting time together matters because different destinations can be associated with different waiting-time distributions.

The kernel is defined at a state-entry time. It concerns the next transition from the state just entered, not the state occupied at an arbitrary later calendar time. The distinction is useful whenever holding times need not be exponential or when the timing of a transition may depend on its destination.

Definition: Let $J_n$ be the state entered at transition number $n$, let $S_n$ be its entry time, and let $W_{n+1}=S_{n+1}-S_n$ be the time spent there before the next transition. The semi-Markov kernel is $$ Q_{ij}(u)=P(W_{n+1}\leq u,\ J_{n+1}=j\mid J_n=i),\qquad u\geq 0. $$ It is the joint distribution of the next destination $j$ and the waiting time, conditional on entering state $i$. In particular, $Q_{ij}$ is a subdistribution in time: its total mass can be less than one.

The usual semi-Markov assumption is that, conditional on the state just entered, the joint law of the next destination and holding time does not depend on earlier states, earlier holding times, or calendar entry time. In other words, the kernel specifies the same next-transition law on each visit to state $i$. This assumption is about the transition at the next exit; it does not say that the state occupied at every calendar time is Markov.

Unless instantaneous transitions are part of the model, assume $W_{n+1}>0$, so $Q_{ij}(0)=0$. If every visit eventually ends in one of the modeled destinations, the row total mass is one. If there is a positive probability of remaining in state $i$ forever, the mass can be less than one; that possibility must be specified rather than silently treated as a transition to another state. An absorbing state is often handled separately, with no subsequent transition from it.

Marginal Components of the Kernel

For each pair $i,j$, the limit of $Q_{ij}(u)$ gives the probability of the destination, without regard to when it occurs. Summing over destinations gives the distribution of the total time in the current state. These are two different summaries of the same joint law.

p_{ij}=\lim_{u\to\infty}Q_{ij}(u) =P(J_{n+1}=j\mid J_n=i), \qquad F_i(u)=\sum_j Q_{ij}(u) =P(W_{n+1}\leq u\mid J_n=i).

If $p_{ij}>0$, the holding-time distribution conditional on next entering $j$ is $$ P(W_{n+1}\leq u\mid J_n=i,J_{n+1}=j) =\frac{Q_{ij}(u)}{p_{ij}}. $$ This ratio is a conditional CDF; $Q_{ij}(u)$ itself is not. When $F_i(u)>0$, the probability of destination $j$ among transitions that have happened by time $u$ is $Q_{ij}(u)/F_i(u)$. This is yet another conditional probability and should not be confused with $p_{ij}$, which conditions on eventually making the next transition.

A distribution need not have a density merely because it is continuous. The kernel can always be represented by a measure on waiting times: for a set $A$ of possible waiting times, define $$ \mu_{ij}(A)=P(W_{n+1}\in A,\ J_{n+1}=j\mid J_n=i). $$ Then $Q_{ij}(u)=\mu_{ij}([0,u])$. If, and only if, this subdistribution is absolutely continuous with respect to time, it has a density $q_{ij}(u)=dQ_{ij}(u)/du$ (almost everywhere), and its mass is recovered by integrating that density. Discrete atoms or singular-continuous components require the measure or CDF representation instead.

Worked Example: Reading Subdistributions From Completed Visits

Hypothetical data: Suppose 12 fully observed visits to state A end in either B or C. The seven waiting times for transitions A to B are 1, 2, 3, 4, 6, 7, and 8 days. The five waiting times for A to C are 2, 5, 6, 9, and 10 days. Treat the empirical proportions as estimates of the kernel for this example.

At $u=4$ days, four of the 12 visits have both ended by day 4 and gone to B. One has ended by day 4 and gone to C. Therefore, $$ \widehat Q_{AB}(4)=\frac{4}{12}=\frac{1}{3}, \qquad \widehat Q_{AC}(4)=\frac{1}{12}. $$ The total empirical probability of leaving A by day 4 is their sum: $$ \widehat F_A(4)=\widehat Q_{AB}(4)+\widehat Q_{AC}(4) =\frac{5}{12}=0.4167. $$

The estimated eventual destination probabilities are $\widehat p_{AB}=7/12=0.5833$ and $\widehat p_{AC}=5/12=0.4167$. Among visits that eventually go to B, the proportion that have done so by day 4 is $4/7=0.5714$. Notice the different denominators: $\widehat Q_{AB}(4)=4/12$ is a joint proportion among all visits, while $4/7$ conditions on the destination being B.

A Two-State Kernel

In a two-state alternating model, the only possible next destination from state 0 is state 1, and the only possible next destination from state 1 is state 0. Thus each row has just one possible next destination. The destination probability in each row is one if the next transition occurs with probability one, but the waiting-time distribution can still differ between the two states.

Worked Example: Two States With Different Waiting-Time Distributions

Hypothetical model: A process alternates between state 0 and state 1. Time is measured in months. On entering state 0, the holding time has a Weibull distribution with shape 2 and scale 4 months; on entering state 1, it has an exponential distribution with mean 6 months. There are no other destinations, and each holding time is finite with probability one.

For state 0, the holding-time CDF is $1-\exp[-(u/4)^2]$, so the only nonzero kernel entry in that row is $$ Q_{01}(u)=1-\exp[-(u/4)^2],\qquad p_{01}=1. $$ For state 1, the exponential holding-time CDF gives $$ Q_{10}(u)=1-\exp(-u/6),\qquad p_{10}=1. $$ The diagonal entries $Q_{00}$ and $Q_{11}$ are zero because the model has no self-transitions.

After entering state 0, the probability that the next transition has occurred by month 4 is $$ Q_{01}(4)=1-\exp[-(4/4)^2]=1-e^{-1}=0.6321. $$ Since 1 is the only destination, this is also the probability of being in the joint event “next destination is 1 and waiting time is at most 4 months.” The probability that the transition occurs between months 2 and 4 is $$ Q_{01}(4)-Q_{01}(2) =0.6321-\{1-\exp[-(2/4)^2]\} =0.6321-0.2212 =0.4109. $$

The two-state setup does not force the two holding-time distributions to be alike. For instance, after entering state 1, the probability of leaving within 6 months is $Q_{10}(6)=1-e^{-1}=0.6321$, also within 6 months but from a different state. The kernel makes each state’s waiting-time law explicit.

Deriving and Checking Kernel Properties

The marginal formulas follow directly from the definition, rather than from an additional modeling approximation. For a fixed origin state $i$, the events $\{W_{n+1}\leq u,J_{n+1}=j\}$ are disjoint over distinct destinations $j$. Their union is the event that the next transition has occurred by $u$. Adding the probabilities therefore gives the holding-time CDF:

\sum_j Q_{ij}(u) =\sum_j P(W_{n+1}\leq u,J_{n+1}=j\mid J_n=i) =P(W_{n+1}\leq u\mid J_n=i).

Taking $u$ to infinity gives $\sum_j p_{ij}=1$ when a next transition occurs with probability one. If the row sum is less than one, the missing mass represents a modeled possibility of no finite next transition, not an unobserved destination to be allocated arbitrarily.

For any valid kernel, each $Q_{ij}(u)$ is nondecreasing and right-continuous in $u$, takes values between zero and one, and has a finite limit $p_{ij}$. At each $u$, the row sum $\sum_j Q_{ij}(u)$ must also be between zero and one and nondecreasing. These properties provide basic checks for a proposed formula or computed table.

Worked Example: A Kernel With an Atom

Hypothetical model: From state A, a transition goes to B with probability 0.6 and a waiting time uniformly distributed between 0 and 2 hours. It goes to C with probability 0.4 and then occurs exactly 3 hours after entry to A. There are no other destinations.

The kernel entries, for $u\geq 0$, are $$ Q_{AB}(u)=0.6\min(u/2,1), \qquad Q_{AC}(u)= \begin{cases} 0,&u<3,\\ 0.4,&u\geq 3. \end{cases} $$ At $u=1$, $Q_{AB}(1)=0.3$ and $Q_{AC}(1)=0$, so $F_A(1)=0.3$. At $u=3$, $Q_{AB}(3)=0.6$, $Q_{AC}(3)=0.4$, and $F_A(3)=1$. The limiting destination probabilities are $p_{AB}=0.6$ and $p_{AC}=0.4$.

The B subdistribution is absolutely continuous: its density is 0.3 per hour for $0<u<2$ and zero after 2 hours. The C subdistribution has an atom of size 0.4 at 3 hours. It has no ordinary density that integrates to 0.4; describing it by a derivative and an ordinary integral would lose the atom. Its measure assigns probability 0.4 to the single waiting time of 3 hours. The kernel CDFs correctly represent both components.

How the Kernel Differs From Common Alternatives

A transition-probability matrix over a fixed time interval describes the state occupied after that interval, allowing for any number of transitions along the way. A semi-Markov kernel describes only the next transition after entry into a specified state, jointly with its waiting time. It is therefore not a fixed-horizon state-occupation probability.

A continuous-time Markov chain is a more restrictive model. In a state with a finite total exit rate, its holding time is exponential, and the destination is independent of the holding time conditional on the current state. The semi-Markov kernel permits non-exponential holding times and permits destination-specific waiting-time distributions. In the two-state example, the Weibull holding time in state 0 would not satisfy the exponential holding-time condition of a continuous-time Markov chain.

These differences are useful when deciding whether the kernel’s added flexibility is needed. The flexibility does not remove the need to define the state and entry event carefully, nor does it guarantee that data contain enough observed transitions to estimate every destination-specific distribution reliably.

Diagnostics, Limitations, and Common Mistakes

Check the row sums. For a model in which every visit ends in a modeled next transition, the limits $p_{ij}$ across destinations should sum to one. At any finite $u$, the row sum is the probability of having left by $u$, so it cannot exceed one.
Check monotonicity and limits. Each entry must be nondecreasing in waiting time and approach a finite destination probability. A decreasing entry or a row total above one signals a formula, coding, or data-construction problem.
Do not treat censoring as an observed transition. A visit whose next transition is not observed by the end of follow-up does not reveal its destination or its full waiting time. Estimation must account for such incomplete observation rather than count it as a completed transition at the censoring time.
Do not assume every kernel has a density. The derivative representation is available when the subdistribution is absolutely continuous. Atoms and singular-continuous distributions are valid possibilities and must be retained in a measure or CDF representation.
Do not confuse joint and conditional probabilities. $Q_{ij}(u)$ uses all visits to $i$ in its conditioning set. Dividing by $p_{ij}$ produces the waiting-time CDF conditional on destination $j$, when $p_{ij}>0$.

A common mistake is to see $Q_{ij}(u)$ as “the probability of waiting no more than $u$, given that the next state is $j$.” That reasoning omits the destination probability. The correct conditional waiting-time CDF is $Q_{ij}(u)/p_{ij}$; the kernel entry itself is the joint probability of the destination and the time bound, conditional only on the origin state.

Key takeaway: A semi-Markov kernel retains the joint information about the next destination and the holding time after entering a state. Its row sums give the holding-time CDF, its limiting entries give next-destination probabilities, and its conditional destination-specific timing distributions are obtained by normalizing entries with positive limiting mass.

Check Your Understanding

Answer each question, then compare with the solutions below.

If $Q_{12}(5)=0.24$ and $p_{12}=0.60$, what is the conditional probability that the waiting time is at most 5 time units given that the next destination is state 2?
In a model with three possible destinations from state A, what does $\sum_j Q_{Aj}(u)$ represent?
Why is an ordinary density not an adequate representation for a subdistribution that places positive mass at one waiting time?
In the two-state model above, what is the probability of a transition from state 1 by month 6?

Solutions. (1) Divide the joint subdistribution by the destination probability: $0.24/0.60=0.40$. (2) It is the probability, conditional on entering A, that the next transition has occurred by $u$, regardless of destination. (3) A point mass is not recovered by integrating an ordinary density with respect to time; it must be represented as an atom in the measure or as a jump in the CDF. (4) The only destination is state 0 and $Q_{10}(6)=1-e^{-6/6}=1-e^{-1}=0.6321$, or about 0.6321.

What You'll Learn