From Rates to a Path
A rate specification describes the local behavior of a continuous-time Markov chain (CTMC), but it does not by itself display a sample path. To construct one, we need to determine how long the process stays at each state and where it jumps next. On a countable state space, this construction also makes a crucial global issue visible: even if every individual holding time is positive, infinitely many jumps might occur in a finite total time.
Let \(S\) be a countable state space. Suppose that for each pair of distinct states \(i,j\in S\) we are given a rate \(c_{ij}\ge 0\), and assume that the total rate out of each state is finite: \(q_i=\sum_{j\ne i}c_{ij}<\infty\). Set \(c_{ii}=0\); the diagonal entry of the generator is instead \(q_{ii}=-q_i\). Thus the generator \(Q=(q_{ij})\) has \(q_{ij}=c_{ij}\) for \(i\ne j\), \(q_{ii}=-q_i\), and every row sums to zero. Finiteness is a state-by-state condition; the rates need not be bounded uniformly over \(S\).
For \(q_i>0\), the jump probabilities are well-defined because \(\sum_{j\ne i}p_{ij}=\sum_{j\ne i}c_{ij}/q_i=1\). A zero exit rate means all off-diagonal rates in that row are zero, so treating \(i\) as absorbing is consistent with the specification. There are no self-transitions in the jump chain: a rate \(c_{ii}\) is not an extra jump rate.
Here is the recursive construction. On a probability space carrying independent random variables \(E_0,E_1,\ldots\), each exponential with rate \(1\), and independent uniform random variables \(U_0,U_1,\ldots\) on \((0,1)\), start at \(X_0=i_0\). If the state at the \(m\)th jump is \(i\) with \(q_i>0\), set the next holding time to \(H_m=E_m/q_i\), and choose the next state using \(U_m\) and the probabilities \((p_{ij})_{j\ne i}\). For example, enumerate the possible destinations and assign consecutive intervals of lengths \(p_{ij}\) in \((0,1)\). If \(q_i=0\), there is no next jump. Define jump times by \(S_0=0\) and \(S_{m+1}=S_m+H_m\) whenever the next jump is defined. The process holds at each visited state until its next jump time. If infinitely many jumps have a finite limiting time, the minimal process is sent to a cemetery state at that time and remains there.
The exponential survival formula gives \(\mathbb P(H_m>t\mid X_{S_m}=i)=e^{-q_i t}\) when \(q_i>0\). The destination choice is independent of this holding time. The natural filtration \((\mathcal F_t)_{t\ge0}\), generated by the constructed path, records its history up to time \(t\). The memoryless identity \(e^{-q_i(s+t)}/e^{-q_i s}=e^{-q_i t}\) shows that, conditional on still being at \(i\) at time \(t\), the remaining holding time has the same exponential law. Together with the independent variables used for later jumps, this gives the time-homogeneous Markov property, with the cemetery state absorbing.
Proof. Fix a starting state \(i\). If \(q_i=0\), the process stays at \(i\), and all the stated limits are zero, as required. Suppose \(q_i>0\). The probability that the first jump occurs by time \(h\) and goes to \(j\) is \((1-e^{-q_i h})p_{ij}\). For \(j\ne i\), this event contributes to \(\{X_h=j\}\) unless the process makes another jump by time \(h\). Conversely, if \(X_h=j\) but the first jump was not to \(j\), at least two jumps occurred by time \(h\). Thus the difference between \(\mathbb P_i(X_h=j)\) and \((1-e^{-q_i h})p_{ij}\) in absolute value is at most the probability of at least two jumps by time \(h\).
After the first jump, the process is in some state \(l\) with probability \(p_{il}\). Given that state, the chance of another jump within the next \(h\) time units is \(1-e^{-q_l h}\), interpreted as zero when \(q_l=0\). Therefore \[ \mathbb P_i(\text{at least two jumps by }h) \le (1-e^{-q_i h})\sum_l p_{il}(1-e^{-q_l h}) \le q_i h\sum_l p_{il}(1-e^{-q_l h}). \] After division by \(h\), the last expression tends to zero: for each \(l\), \(1-e^{-q_lh}\to0\), and each summand is bounded by \(p_{il}\), whose sum is \(1\). Dominated convergence for this countable probability distribution applies. Hence the two-or-more-jump probability is \(o(h)\), and \[ \lim_{h\downarrow0}\frac{\mathbb P_i(X_h=j)}h =\lim_{h\downarrow0}\frac{(1-e^{-q_i h})p_{ij}}h =q_i p_{ij}=c_{ij}. \] For the diagonal, the event of at least one jump by \(h\) has probability \(1-e^{-q_i h}\). The difference between this event and \(\{X_h\ne i\}\) can occur only if at least two jumps occur and the process returns to \(i\). The difference is therefore \(o(h)\). It follows that \(\mathbb P_i(X_h\ne i)=q_i h+o(h)\), and so \((\mathbb P_i(X_h=i)-1)/h\to-q_i\). This proves both limits. \(\square\)
The recursive rule also explains the word minimal: before explosion, each successive holding time and destination are sampled from exactly the distributions specified at the current state. Those rules determine the law of each finite sequence of jumps. The construction does not add any continuation in ordinary states after an accumulation of infinitely many jumps in finite time.
Worked Constructions
Worked Example: A Three-State Rate Specification
Take \(S=\{a,b,c\}\), with rates \(c_{ab}=2\), \(c_{ac}=1\), \(c_{ba}=4\), and all other off-diagonal rates zero. Thus \(c\) is absorbing. Compute the exit rates, jump probabilities, and holding-time laws.
At \(a\), \(q_a=c_{ab}+c_{ac}=2+1=3\). Its jump probabilities are \(p_{ab}=2/3\) and \(p_{ac}=1/3\), which sum to \(2/3+1/3=1\). At \(b\), \(q_b=c_{ba}=4\), and \(p_{ba}=4/4=1\). At \(c\), \(q_c=0\), so the process stays there. The holding times at \(a\) and \(b\) have exponential rates \(3\) and \(4\), respectively.
In the order \(a,b,c\), the generator is \[ Q=\begin{bmatrix}-3&2&1\\4&-4&0\\0&0&0\end{bmatrix}. \] The row sums are \(-3+2+1=0\), \(4-4+0=0\), and \(0+0+0=0\), as required. For instance, starting at \(a\), the probability that the first jump occurs by time \(h\) and goes to \(c\) is \((1-e^{-3h})/3\); divided by \(h\), this tends to \(1=c_{ac}\). The theorem’s two-jump bound justifies identifying this first-jump limit with the usual transition-rate limit.
Check: The exit rates equal the sums of the off-diagonal entries in their rows: \(3,4,0\). The jump probabilities at every nonabsorbing state sum to \(1\), and every generator row sums to \(0\).
Worked Example: A Pure-Birth Chain That Explodes
Let \(S=\{0,1,2,\ldots\}\), and from state \(n\) let the only possible jump be to \(n+1\), at rate \(c_{n,n+1}=2^n\). Start at \(0\). Determine whether infinitely many jumps occur in finite time.
At each \(n\), the exit rate is \(q_n=2^n\), so the generator row has \(-2^n\) in position \(n\), \(2^n\) in position \(n+1\), and zero elsewhere; its row sum is \(-2^n+2^n=0\). The jump probability to \(n+1\) is \(2^n/2^n=1\). If \(E_n\) are independent rate-one exponentials, the holding time in state \(n\) is \(E_n/2^n\), and the total time for infinitely many jumps is \[ \zeta=\sum_{n=0}^{\infty}\frac{E_n}{2^n}. \] By nonnegativity and monotone convergence, \(\mathbb E[\zeta]=\sum_{n=0}^{\infty}2^{-n}\mathbb E[E_n]=\sum_{n=0}^{\infty}2^{-n}=2\). Since a nonnegative random variable with finite expectation cannot equal infinity with positive probability, \(\zeta<\infty\) almost surely. Thus this minimal process explodes almost surely, despite every individual exit rate being finite and every holding time being positive almost surely.
Check: The geometric sum starts at \(1\), so \(\sum_{n=0}^{\infty}2^{-n}=1/(1-1/2)=2\). The expected explosion time is therefore finite, which verifies the conclusion rather than merely suggesting it.
Worked Example: A Pure-Birth Chain That Does Not Explode
Keep the same state space and jump destinations, but set \(c_{n,n+1}=1\) for every \(n\), starting again at \(0\). Show that the sum of holding times is infinite almost surely.
Every exit rate is \(q_n=1\), every jump probability to \(n+1\) is \(1\), and the generator row has \(-1\) at \(n\) and \(1\) at \(n+1\), with row sum \(-1+1=0\). The holding times are independent rate-one exponentials \(E_n\). For each \(n\), \(\mathbb P(E_n\ge1)=e^{-1}\). For fixed \(m\le N\), independence gives \[ \mathbb P(E_n<1\text{ for every }m\le n\le N)=(1-e^{-1})^{N-m+1}, \] which tends to zero as \(N\to\infty\). Hence the probability that \(E_n<1\) for every \(n\ge m\) is zero. Taking the countable union over \(m\), the probability that only finitely many \(E_n\) are at least \(1\) is zero. Almost surely infinitely many terms in \(\sum_n E_n\) are at least \(1\), so \(\sum_nE_n=\infty\). The process is nonexplosive.
Check: The calculation uses the same threshold \(1\) for every holding time. Infinitely many terms each at least \(1\) force the partial sums to grow without bound, so the jump times cannot accumulate at a finite time.
Explosion Is a Pathwise Question
Proof. Let \(H_m\) be the holding time before the \((m+1)\)st jump on a path that continues to jump. By construction, the time of the \(r\)th jump is \(S_r=\sum_{m=0}^{r-1}H_m\). These partial sums increase, and their limit is \(\sum_{m=0}^{\infty}H_m\), possibly infinite. Infinitely many jumps occur before a finite time exactly when \(S_r\) has a finite limit, which is equivalent to that series being finite. If a zero-exit-rate state is reached, the construction assigns no subsequent jump, so there cannot be infinitely many later jumps. \(\square\)
This criterion concerns the rates along the random jump path, not just a single row of the rate specification. A large exit rate makes a holding time short on average, but the sequence of visited states also matters. The two pure-birth examples isolate this point: both have finite exit rates at every state and certain upward jumps, yet one has a finite sum of holding times almost surely and the other an infinite sum almost surely. In more general chains, the destination choices are random, so the holding-time sum must be assessed along those random destinations.
Common mistake: using only the first-jump calculation. One might write \(\mathbb P_i(X_h=j)=(1-e^{-q_i h})p_{ij}\) and conclude that the transition rate is \(c_{ij}\). This is not an equality: the right side counts paths whose first jump is to \(j\), but it does not account for paths making two or more jumps before \(h\), including paths that arrive at \(j\) after an intermediate state. The correction is to bound those paths. In a countable-state model, it is not valid to use a global maximum exit rate, since \(\sup_l q_l\) may be infinite. Instead, use the first-state-specific bound \[ \mathbb P_i(\text{at least two jumps by }h) \le q_i h\sum_l p_{il}(1-e^{-q_l h})=o(h). \] The final equality follows by dominated convergence, because \(1-e^{-q_lh}\to0\) for each \(l\) and is bounded by \(1\). Only after this error is shown to be \(o(h)\) does the first-jump calculation establish the usual transition-rate limit.
To use a rate specification reliably, check the exit-rate sum at every state, normalize the jump probabilities only when the exit rate is positive, and handle zero-rate states separately. Then construct holding times and destinations in sequence. Finally, examine the accumulated holding times to decide whether the resulting minimal process is nonexplosive. Finite exit rates state by state are necessary for this construction, but they are not by themselves a guarantee against explosion.
Check Your Understanding
For each question, state the assumptions you use and verify any rate or probability calculation.
- At a state \(i\), the only outgoing rates are \(c_{ij}=3\) and \(c_{ik}=2\). Find \(q_i\), both jump probabilities, and the holding-time distribution.
- Why does a zero exit rate imply that the construction remains at that state forever?
- For the pure-birth rates \(c_{n,n+1}=3^n\), write the series for the explosion time and compute its expectation when the chain starts at \(0\).
- Explain why finite exit rates at every state do not rule out explosion.
- In the two-jump bound, identify the probability weights used for dominated convergence and the pointwise limit of the summand.