From a Rate Table to a Random Path
A Q-matrix specifies the instantaneous rates of leaving each state and choosing each possible destination. It does not, by itself, describe how to continue a path after infinitely many jumps have occurred in finite time. The minimal construction makes this distinction explicit: it uses the rates to build a path up to its explosion time, and makes no assignment at or after that time.
Let \(S\) be a finite or countable state space. A Q-matrix is an array \(Q=(q_{ij})_{i,j\in S}\) such that \(q_{ij}\ge 0\) when \(j\ne i\), and, for every \(i\), the exit rate \(q_i=\sum_{j\ne i}q_{ij}\) is finite and \(q_{ii}=-q_i\). Thus each row sums to zero. The case \(q_i=0\) means that every off-diagonal rate in row \(i\) is zero. For \(q_i>0\), define the jump probabilities \(r_{ij}=q_{ij}/q_i\) for \(j\ne i\), and \(r_{ii}=0\). These probabilities sum to one because \(\sum_{j\ne i}q_{ij}=q_i\).
One way to realize the construction is to use independent unit-rate exponential random variables \(E_n\), independent random variables for the jump choices, and an initial draw \(Y_0\), all on a probability space \((\Omega,\mathcal F,\mathbb P)\). If \(q_{Y_n}>0\), set \(H_n=E_n/q_{Y_n}\); if \(q_{Y_n}=0\), set \(H_n=\infty\). At a positive exit rate, choose \(Y_{n+1}\) according to \((r_{Y_nj})_{j\in S}\). At a zero exit rate, set \(Y_{n+1}=Y_n\); its infinite holding time means this choice never creates another jump. This convention avoids dividing by zero.
Each \(H_n\) is strictly positive almost surely when it is finite. Consequently the jump times increase strictly until they reach a possible finite limit \(\zeta\). If \(t<\zeta\), there is a finite \(n\) with \(S_n\le t<S_{n+1}\); otherwise the increasing sequence \(S_n\) would have limit at most \(t\). Thus the definition assigns exactly one state to every time before explosion. The resulting paths are right-continuous and constant between successive jump times. A zero exit rate gives \(H_n=\infty\), so the process remains forever in that state and \(\zeta=\infty\).
Why the Construction Has the Specified Rates
Proof. If \(q_i=0\), the process stays at \(i\), \(\zeta=\infty\), and both statements hold exactly: the first probability is zero and the second is one. Suppose \(q_i>0\). The first holding time is exponential with rate \(q_i\), so the probability of a first jump by time \(h\) is \(1-e^{-q_i h}=q_i h+o(h)\). Its destination is \(k\) with probability \(r_{ik}\), independently of that holding time.
It remains to control paths with two or more jumps. For \(k\) with \(r_{ik}>0\), the probability of a further jump within any remaining time of length at most \(h\), after reaching \(k\), is at most \(1-e^{-q_kh}\); this is zero if \(q_k=0\). Define $$ A(h)=\sum_{k:r_{ik}>0}r_{ik}(1-e^{-q_kh}). $$ For each \(k\), the summand factor \(1-e^{-q_kh}\) tends to zero as \(h\downarrow0\), and it is bounded by one. Since the \(r_{ik}\) sum to one, dominated convergence gives \(A(h)\to0\). Conditioning on the first jump time and destination now yields $$ \mathbb P_i(\text{at least two jumps by }h) \le (1-e^{-q_i h})A(h)=o(h). $$ This bound also covers paths that explode by time \(h\), since such paths have at least two jumps.
The probability that the first jump occurs by \(h\) and has destination \(j\) is \(r_{ij}(1-e^{-q_i h})=q_{ij}h+o(h)\). Removing paths with at least two jumps changes this probability by at most \(o(h)\). On the remaining paths, \(X_h=j\) and \(h<\zeta\). This proves the first expansion. The event of no jump by \(h\) has probability \(e^{-q_i h}=1-q_i h+o(h)\) and implies \(X_h=i\), \(h<\zeta\). Any additional paths counted by \(\{X_h=i,\ h<\zeta\}\) must have made at least two jumps, so their probability is \(o(h)\). This proves the second expansion. \(\square\)
The estimate for multiple jumps is important even when every exit rate is finite. After the first jump, the process may be at a state with a very large exit rate. It is not enough to observe that the conditional chance of another jump tends to zero for each fixed destination: the probability of the first jump must also be included. The factor \(1-e^{-q_i h}=O(h)\) supplies precisely that factor.
Worked Example: Alternating Between Two States
Take \(S=\{0,1\}\) and $$ Q=\begin{bmatrix}-2&2\\3&-3\end{bmatrix}. $$ The first row sums to \(-2+2=0\), and the second to \(3-3=0\). The exit rates are \(q_0=2\) and \(q_1=3\), both finite and positive. Each state has only one possible destination: \(r_{01}=2/2=1\) and \(r_{10}=3/3=1\).
Starting at \(0\), the first holding time is \(H_0=E_0/2\), where \(E_0\) is unit-rate exponential, so \(H_0\) is exponential with rate \(2\). The first jump is to \(1\). The next holding time is \(H_1=E_1/3\), exponential with rate \(3\), followed by a jump to \(0\). The path therefore alternates, with holding rates \(2,3,2,3,\ldots\). For a direct rate check, \(1-e^{-2h}=2h+o(h)\) is the probability of a first jump from \(0\) by time \(h\), and that jump goes to \(1\) with probability one. The probability of at least two jumps by \(h\) is \(o(h)\) by the proposition, so \(\mathbb P_0(X_h=1,\ h<\zeta)=2h+o(h)\). From state \(1\), the corresponding first-jump probability is \(1-e^{-3h}=3h+o(h)\), giving \(\mathbb P_1(X_h=0,\ h<\zeta)=3h+o(h)\).
Check: The destination probabilities in both rows sum to one, and the rates recovered from the two small-time probabilities are \(2=q_{01}\) and \(3=q_{10}\), as required.
Worked Example: An Absorbing State
Let \(S=\{0,1,2\}\) and $$ Q=\begin{bmatrix}-2&2&0\\1&-2&1\\0&0&0\end{bmatrix}. $$ The row sums are \(-2+2+0=0\), \(1-2+1=0\), and \(0+0+0=0\). The exit rates are \(q_0=2\), \(q_1=2\), and \(q_2=0\). From state \(0\), the jump probability to \(1\) is \(r_{01}=2/2=1\). From state \(1\), the probabilities are \(r_{10}=1/2\) and \(r_{12}=1/2\). State \(2\) has no possible jump.
Start at state \(1\). The first holding time has exponential rate \(2\). At its end, the chain chooses state \(0\) or \(2\), each with probability \(1/2\). If it chooses \(2\), its next holding time is infinite, so the path stays there for all later times. If it chooses \(0\), the next holding time has exponential rate \(2\), after which the chain jumps to \(1\). In particular, for small \(h\), the probability of a first jump from \(1\) to \(0\) by time \(h\) is $$ \tfrac12(1-e^{-2h})=h+o(h), $$ and the probability of a first jump from \(1\) to \(2\) by time \(h\) is also \(h+o(h)\). These are the off-diagonal rates \(q_{10}=1\) and \(q_{12}=1\). Once at \(2\), the holding time is infinite and the path never explodes.
Check: The two possible destinations from \(1\) have probabilities \(1/2+1/2=1\), and their rates add to \(1+1=2=q_1\). At \(2\), the total rate is zero, matching its zero row.
Explosion and the Meaning of “Minimal”
Write \(N_t\) for the number of jumps completed by time \(t\), when \(t<\zeta\). The explosion time is the limit of the successive jump times, \(\zeta=\lim_{n\to\infty}S_n\). If \(\zeta=\infty\), the construction supplies a state at every finite time. If \(\zeta<\infty\), infinitely many jumps occur before that finite limit; the construction supplies states only for \(t<\zeta\). It does not specify a state at \(\zeta\), nor does it describe what happens afterward. In this sense the construction is minimal: it records only the path determined by the rates before explosion. Any additional convention after explosion is extra information, not part of this construction.
Worked Example: A Pure-Birth Q-Matrix That Explodes
Let \(S=\{0,1,2,\ldots\}\), with \(q_{n,n+1}=2^n\), \(q_{nn}=-2^n\), and all other entries zero. Each row has finite exit rate \(q_n=2^n\), and its sum is \(-2^n+2^n=0\). The jump probability from \(n\) to \(n+1\) is \(2^n/2^n=1\). Starting at \(0\), the holding time at \(n\) is exponential with rate \(2^n\), so its mean is \(1/2^n\). The explosion time is the sum of these holding times: $$ \zeta=\sum_{n=0}^{\infty}H_n, \qquad \mathbb E[\zeta]=\sum_{n=0}^{\infty}\mathbb E[H_n] =\sum_{n=0}^{\infty}\frac{1}{2^n}=2. $$ The expectation identity follows by applying monotone convergence to the increasing finite partial sums. Since \(\zeta\ge0\) and has finite expectation, \(\mathbb P(\zeta=\infty)=0\): if that probability were positive, the expectation would be infinite. Thus this path reaches infinitely many states in finite time almost surely, even though every individual exit rate is finite.
Check: The geometric sum is \(1+\tfrac12+\tfrac14+\cdots=2\). The conclusion is that \(\zeta\) is finite almost surely, not that its value is exactly \(2\); \(2\) is its expectation.
Common mistake. A jump probability is not the same quantity as a jump rate. In the two-state example, the rate from \(0\) to \(1\) is \(q_{01}=2\), but the probability that the next jump goes to \(1\) is \(r_{01}=2/2=1\), not \(2\). Substituting \(2\) as a destination probability would give probabilities in a row summing to \(2\), which is impossible. The rate determines the holding-time distribution; dividing by the total exit rate gives the destination probabilities.
A second related error is to write \(\mathbb P_i(X_h=j)\) without qualification when the construction has stopped at explosion. For the minimal process, the stated small-time formula concerns the killed event \(\{X_h=j,\ h<\zeta\}\). In the pure-birth example, a post-explosion value has not been assigned, so an unqualified probability involving \(X_h\) need not be defined. Keeping the survival condition in the formula makes both the construction and its rate calculation precise.
Check Your Understanding
Use the construction and distinguish rates, jump probabilities, and the lifetime of the minimal process.
- For a state with \(q_i=5\), what is the distribution of its holding time, and how are its jump probabilities obtained from the row of \(Q\)?
- A row has \(q_{ij}=3\), \(q_{ik}=1\), and no other off-diagonal rates. Find \(q_i\), \(q_{ii}\), and the two destination probabilities.
- What holding time and destination rule does the construction use when \(q_i=0\)?
- Why must the small-time probability of at least two jumps include the probability of a first jump by time \(h\)?
- In the pure-birth example, what does \(\mathbb E[\zeta]=2\) imply, and what does it not imply about the exact value of \(\zeta\)?