The Possible Failure: Infinitely Many Jumps in Finite Time
A continuous-time Markov chain can revisit states, so a finite state space does not put a deterministic limit on the number of jumps. The relevant question is whether infinitely many jumps could accumulate before some finite time. The answer depends on how quickly the chain can leave its states: if there are only finitely many states and every exit rate is finite, those rates have a finite common upper bound. That bound prevents the holding times from becoming too short too often.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_t)_{t\ge0}\) be the minimal pure-jump continuous-time Markov chain on a finite state space \(S\), with generator \(Q=(q_{ij})\). For \(i\ne j\), \(q_{ij}\ge0\), and each row sums to zero. The exit rate from state \(i\) is \(q_i=-q_{ii}=\sum_{j\ne i}q_{ij}\), which is finite by assumption. The natural filtration is \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). In this construction, when the chain is in \(i\) with \(q_i>0\), its holding time is exponential with rate \(q_i\); its next state is \(j\ne i\) with probability \(q_{ij}/q_i\). If \(q_i=0\), it stays in \(i\) forever.
Let \(T_0=0\), and let \(T_n\) be the time of the \(n\)th jump, for \(n\ge1\), as long as that jump occurs. The explosion time is \(T_\infty=\lim_{n\to\infty}T_n\), with \(T_\infty=\infty\) if the chain makes only finitely many jumps. Explosion means \(T_\infty<\infty\). Thus, proving \(T_\infty=\infty\) almost surely proves that every bounded time interval contains only finitely many jumps.
A Common Lower Bound for Holding Times
Because \(S\) is finite, the maximum exit rate \(M=\max_{i\in S}q_i\) is finite. If \(M=0\), every \(q_i=0\), so no state can be left and there are no jumps. Suppose henceforth that \(M>0\).
The holding-time construction makes the role of this maximum precise. Use independent exponential random variables \(E_1,E_2,\ldots\), each with rate \(1\), to generate successive holding times. If the state during the \(n\)th holding time is \(Y_n\) and \(q_{Y_n}>0\), that time is \(H_n=E_n/q_{Y_n}\). This gives the required exponential distribution with rate \(q_{Y_n}\). Since \(q_{Y_n}\le M\), each such holding time satisfies \(H_n\ge E_n/M\). If the chain reaches a state with exit rate zero, it stops jumping, so it cannot explode after reaching that state.
The independent variables \(E_n\) do not have a positive lower bound individually. What matters is that they exceed \(1\) infinitely often, almost surely. Indeed, \(\mathbb{P}(E_n\ge1)=e^{-1}\). For a fixed integer \(r\ge1\), the probability that none of \(E_{r+1},\ldots,E_{r+m}\) is at least \(1\) is \((1-e^{-1})^m\), which tends to zero as \(m\to\infty\). Therefore the probability that there are no such exceedances after index \(r\) is zero. Taking the countable union over \(r\), the probability of only finitely many exceedances is zero.
Proof of the theorem. If \(M=0\), the chain makes no jumps, as already noted. Let \(M>0\). On any path with infinitely many jumps, every visited state has positive exit rate and the \(n\)th holding time is \(H_n=E_n/q_{Y_n}\ge E_n/M\). Consequently, for every \(m\ge1\), \(T_m=\sum_{n=1}^mH_n\ge M^{-1}\sum_{n=1}^m E_n\). Almost surely, infinitely many \(E_n\) are at least \(1\), so their partial sums diverge to infinity. It follows that \(T_m\to\infty\) on every path with infinitely many jumps, outside a probability-zero event. A path with finitely many jumps has \(T_\infty=\infty\) by definition. Thus \(T_\infty=\infty\) almost surely. For any finite \(t\), \(T_m\to\infty\) implies that only finitely many \(T_m\) can be at most \(t\); applying this to all positive integer \(t\) gives the assertion simultaneously for every bounded interval. \(\square\)
A Quantitative Bound on the Jump Count
The same comparison gives more than almost-sure non-explosion. Write \(N(t)\) for the number of jumps by time \(t\), and use the convention that \(N(t)\ge m\) means \(T_m\le t\). For \(M>0\), the holding-time comparison implies \(\{N(t)\ge m\}\subseteq\{\sum_{n=1}^mE_n\le Mt\}\). The sum of \(m\) independent rate-one exponential variables has density \(x^{m-1}e^{-x}/(m-1)!\) for \(x>0\). This follows by induction: the density for \(m=1\) is \(e^{-x}\); convolving the density for \(m\) with \(e^{-x}\) gives \(e^{-x}\int_0^x u^{m-1}/(m-1)!\,du=e^{-x}x^m/m!\). Integrating that density up to \(x\), or integrating by parts successively, gives the following bound.
Proof. The event inclusion above gives \(\mathbb{P}(N(t)\ge m)\le \mathbb{P}(\sum_{n=1}^mE_n\le Mt)\). Put \(x=Mt\). For \(m=1\), the latter probability is \(\int_0^x e^{-u}\,du=1-e^{-x}\). For a general \(m\), integrate the density just obtained. Repeated integration by parts yields \(\int_0^x u^{m-1}e^{-u}/(m-1)!\,du=1-e^{-x}\sum_{k=0}^{m-1}x^k/k!\). Substituting \(x=Mt\) proves the stated inequality. At \(t=0\), both sides are zero, so the bound also covers that endpoint. \(\square\)
This is an upper bound, not generally an equality: the actual rates can be strictly smaller than \(M\), and the chain’s route through the states affects its holding times. The bound is useful because it depends only on a common rate bound, not on a calculation of all possible paths.
Worked Example: A Two-State Chain
Consider \(S=\{0,1\}\) with generator \(Q=\begin{bmatrix}-2&2\\1&-1\end{bmatrix}\). Each row sums to zero: \(-2+2=0\) and \(1-1=0\). The exit rates are \(q_0=2\) and \(q_1=1\), so \(M=\max(2,1)=2\). Find an upper bound for the probability of at least three jumps by time \(t=1\).
Use the jump-count bound with \(m=3\), \(M=2\), and \(t=1\), so \(Mt=2\). Substitution gives $$ \mathbb{P}(N(1)\ge3)\le 1-e^{-2}\left(\frac{2^0}{0!}+\frac{2^1}{1!}+\frac{2^2}{2!}\right) =1-e^{-2}(1+2+2)=1-5e^{-2}. $$
Check: The bound is the probability that a sum of three independent rate-one exponential variables is at most \(2\): its distribution function is \(1-e^{-2}(1+2+2)=1-5e^{-2}\), as given by the formula. The chain’s two rates are both at most \(2\), which is the condition needed for the comparison.
Worked Example: A Three-State Chain With Unequal Rates
Let \(S=\{0,1,2\}\) and \(Q=\begin{bmatrix}-2&1&1\\1&-3&2\\2&1&-3\end{bmatrix}\). The rows sum to zero: \(-2+1+1=0\), \(1-3+2=0\), and \(2+1-3=0\). The exit rates are \(2,3,3\), respectively, so \(M=3\). Find an upper bound on the probability of at least two jumps by time \(1\).
Here \(m=2\) and \(Mt=3\). Therefore $$ \mathbb{P}(N(1)\ge2)\le 1-e^{-3}\left(\frac{3^0}{0!}+\frac{3^1}{1!}\right) =1-e^{-3}(1+3)=1-4e^{-3}. $$
Check: The comparison event is \(E_1+E_2\le3\). The sum of two rate-one exponential variables has distribution function \(1-e^{-x}(1+x)\); at \(x=3\) this is \(1-e^{-3}(1+3)=1-4e^{-3}\). The largest listed exit rate is \(3\), matching the value used in the bound.
Why Finiteness of the State Space Matters
Finite exit rates state by state are not enough on a countably infinite state space. The maximum of infinitely many finite rates need not be finite. The next example shows how a chain can then make infinitely many jumps in finite time.
Worked Example: A Countable Pure-Birth Chain That Explodes
Take \(S=\{0,1,2,\ldots\}\), with rate \(q_{n,n+1}=2^n\), diagonal rate \(q_{nn}=-2^n\), and all other rates zero. Each row sums to zero because \(2^n-2^n=0\), and each individual exit rate \(q_n=2^n\) is finite. Starting from \(0\), the chain moves successively from \(n\) to \(n+1\). Its holding times can be written \(H_n=E_n/2^n\), where the \(E_n\) are independent rate-one exponential variables.
The total time for all jumps is \(T_\infty=\sum_{n=0}^{\infty}E_n/2^n\). By the expectation rule for a nonnegative series (monotone convergence), $$ \mathbb{E}[T_\infty]=\sum_{n=0}^{\infty}\frac{\mathbb{E}[E_n]}{2^n} =\sum_{n=0}^{\infty}\frac{1}{2^n}=2. $$ A nonnegative random variable with finite expectation cannot be infinite with positive probability: if \(\mathbb{P}(T_\infty=\infty)>0\), then \(\mathbb{E}[T_\infty]\ge K\mathbb{P}(T_\infty=\infty)\) for every \(K>0\), contradicting finiteness as \(K\to\infty\). Hence \(T_\infty<\infty\) almost surely. The rates have no finite common upper bound, so the finite-state theorem does not apply.
A Common Mistake: A Finite State Space Does Not Limit the Number of Jumps
A mistaken argument says that a chain on \(r\) states can make at most \(r-1\) jumps, because there are only \(r\) states to visit. This confuses the number of distinct states with the number of visits. For a concrete correction, consider \(S=\{0,1\}\) and \(Q=\begin{bmatrix}-1&1\\1&-1\end{bmatrix}\). Each row sums to zero, and both exit rates equal \(1\). The chain alternates between the two states and can revisit them arbitrarily many times.
In fact, for any integer \(m\ge1\) and any \(t>0\), the event that each of the first \(m\) holding times is at most \(t/m\) implies \(T_m\le t\). Each holding time is exponential with rate \(1\), so this event has probability \((1-e^{-t/m})^m>0\). Thus there is positive probability of at least \(m\) jumps by time \(t\), for every fixed \(m\). This does not mean there is positive probability of infinitely many jumps by time \(t\): the theorem proves that probability is zero. Arbitrarily many jumps are possible across different paths, while almost every individual path has only finitely many jumps in each bounded interval.
The key condition in the proof is a finite uniform upper bound on exit rates, supplied automatically by a finite state space with finite rates. It lets each holding time dominate a common-rate exponential variable. If rates increase without bound along a path, as in the pure-birth example, that comparison disappears and explosion can occur.
Check Your Understanding
Use the definitions and bounds above to check each conclusion. For event comparisons, keep the convention \(N(t)\ge m\) if and only if \(T_m\le t\).
- For a finite chain with all \(q_i=0\), what is \(T_\infty\), and why?
- A finite chain has maximum exit rate \(M=4\). Apply the jump-count bound to write an upper bound for \(\mathbb{P}(N(1)\ge2)\).
- Why does the proof require an upper bound on the exit rates rather than merely requiring each individual exit rate to be finite?
- In the two-state alternating example, why does positive probability of at least \(m\) jumps by time \(t\) not contradict non-explosion?
- For the countable pure-birth example, compute the expected total jump time starting from state \(1\), using the same holding-time representation.