When Nonexponential Holding Times Break the Markov Property

Why the Current State May Not Be Enough

In a continuous-time Markov chain, the current state contains all the information needed to describe the future. This is closely connected to exponential holding times: after spending time in a state, the remaining wait until the next jump has the same law as it had on entry. If holding times are not exponential, that remaining wait will generally depend on how long the process has already stayed. The state alone then omits information relevant to prediction.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_t)_{t\ge0}\) be a right-continuous, piecewise-constant process on a finite or countable state space \(S\). Write \(\mathcal{F}_t^X=\sigma(X_s:0\le s\le t)\) for its natural filtration. The process is time-homogeneous Markov if, for every \(u\ge0\), the conditional law of \(X_{t+u}\) given \(\mathcal{F}_t^X\) depends on the observed past only through \(X_t\), and the resulting transition probabilities depend on \(u\), not on \(t\). A stronger and useful formulation asks the same of the conditional law of the future path.

In the usual semi-Markov construction, each time the process enters state \(i\), it draws a fresh holding time with distribution \(F_i\), then chooses its next state according to probabilities \(r_{ij}\). Assume holding times are strictly positive and finite almost surely, jump choices are independent of holding times, and the construction is nonexplosive. For each state, the jump probabilities satisfy \(r_{ij}\ge0\), \(r_{ii}=0\), and \(\sum_{j\in S}r_{ij}=1\). Nonexplosion means that only finitely many jumps occur on every bounded time interval.

The Memoryless Criterion

The key condition is that the residual holding-time law not depend on age. For a holding time \(H\) with survival function \(S\), this means \(S(a+u)/S(a)=S(u)\) whenever \(S(a)>0\). Equivalently, \(S(a+u)=S(a)S(u)\). The next result identifies the proper continuous holding-time laws with this property.

Proof. Since \(H>0\) almost surely, \(S(0)=1\), and \(S(t)\to1\) as \(t\downarrow0\). First, \(S(t)>0\) for every finite \(t\). If \(S(t_0)=0\) for some \(t_0>0\), repeated use of the identity gives \(S(t_0)=S(t_0/n)^n\) for every positive integer \(n\), so \(S(t_0/n)=0\). This contradicts \(S(t)\to1\) as \(t\downarrow0\). We may therefore define \(g(t)=-\log S(t)\). The identity for \(S\) gives \(g(a+u)=g(a)+g(u)\). Also \(g(t)\ge0\), and \(g(t)\to0\) as \(t\downarrow0\). Additivity gives \(g(q)=qg(1)\) for every nonnegative rational \(q\). For real \(t\ge0\), choose nonnegative rationals \(q_n\to t\). A survival function is nonincreasing, so \(g\) is nondecreasing; rational values approaching \(t\) from below and above then imply \(g(t)=tg(1)\). Set \(\lambda=g(1)\). If \(\lambda=0\), then \(S(t)=1\) for all \(t\), contradicting that \(H\) is finite almost surely. Hence \(\lambda>0\), and \(S(t)=e^{-\lambda t}\). Conversely, \(e^{-\lambda(a+u)}=e^{-\lambda a}e^{-\lambda u}\), proving the identity. \(\square\)

Thus, in a state-based holding-time model, exponential holding is precisely the case in which survival to age \(a\) leaves the same residual waiting-time distribution as at age zero. If a holding law is not exponential, its residual survival probability varies with age for at least some \(a\) and \(u\). When the history reveals that age, prediction based on the state alone loses relevant information.

For a state-only time-homogeneous Markov description, the probability of remaining in a state throughout a future interval cannot depend on how long the process has already occupied that state. In a holding-time model, this path event has probability \(S_i(a+u)/S_i(a)\) given age \(a\). If these ratios vary with age, the conditional future path law varies with information in the history that is absent from \(X_t\). The criterion concerns the holding-time component; to conclude that the entire process is a CTMC, the jump choices must also be made from the current state according to the specified state-dependent probabilities.

A Concrete Failure of State-Only Prediction

It is useful to see the failure at a fixed observation time, rather than just compare residual laws at two possible ages. In the following process, the path history at time \(3\) reveals two different ages while the current state is the same.

This example also illustrates why one should specify which Markov property is intended. A single nonexponential sojourn beginning at time zero may have age determined by the absolute time, so a time-inhomogeneous state-only description can sometimes predict it. That does not make the process time-homogeneous Markov, nor does it resolve the problem when different histories at the same time produce different ages, as in the example. The age-augmented formulation below keeps the relevant information explicitly.

Adding Age Restores Markovian Prediction

Define \(A_t\) to be the time elapsed since the most recent entry into \(X_t\); at a jump, the new state’s age is set to \(0\). The pair \((X_t,A_t)\) records both the state and its current sojourn age. Between jumps, age increases at unit speed. The next jump law from \((i,a)\) is determined by the holding-time law in \(i\), conditional on survival to age \(a\); after that jump, fresh holding and destination choices are made according to the new state.

Proof. Fix \(t\ge0\), and condition on the history \(\mathcal{F}_t^X\) together with the ages observed up to \(t\). On the event \((X_t,A_t)=(i,a)\), the current holding time has exceeded \(a\), and the next holding time and jump choice were drawn freshly on entry to \(i\), independently of earlier visits. Thus its conditional residual survival probability for \(u\ge0\) is \(S_i(a+u)/S_i(a)\), which depends on the observed history only through \((i,a)\). The destination choice at the next jump has probabilities \(r_{ij}\), independent of this residual holding time. At that jump, age resets to zero and the construction draws fresh variables independently of the history so far. Consequently the conditional law of the first future jump and the pair immediately after it is determined by the present pair. Repeating this argument determines the conditional law of each finite sequence of future jumps and intervening holding times from the present pair alone. Nonexplosion ensures that on bounded time intervals these jumps define the whole future path, so its conditional law depends on the past only through \((X_t,A_t)\). The rules use elapsed age and state, not absolute time, so the augmented process is time-homogeneous Markov. \(\square\)

When the holding time in state \(i\) is exponential with rate \(\lambda_i>0\), its survival function is \(S_i(a)=e^{-\lambda_i a}\). The age-aware residual probability is then

independent of \(a\). In a model with state-dependent jump probabilities, this is the familiar state-based continuous-time Markov chain construction: the present state suffices because neither the residual wait nor the destination choice requires the elapsed age.

A Common Pitfall

Common mistake: Treating the probability of surviving a further \(u\) time units as \(S_i(u)\) even after the process has already survived to age \(a\). For the Weibull survival function \(S_i(t)=e^{-t^2}\), that incorrect calculation at age \(1\) for a further unit gives \(S_i(1)=e^{-1}\). The correct conditional probability is \(S_i(2)/S_i(1)=e^{-4}/e^{-1}=e^{-3}\). The missing denominator accounts for the conditioning event: the process is already known to have survived to age \(1\).

In applications, this distinction affects prediction and model choice. If the risk of leaving a state changes with time spent there, a state-only CTMC may misrepresent the process. Recording elapsed time gives a Markov state description; alternatively, one can use a model designed to represent general holding-time distributions. The important diagnostic is not simply whether holding times are “nonexponential,” but whether the conditional residual law changes with the observed age.