What a Rate Table Must Record
A continuous-time Markov chain (CTMC) records a state that changes at random times. A rate table describes how quickly the process leaves each state and how that rate is distributed among possible destinations. Auditing such a table requires two separate checks: the rates must define a valid generator, and any proposed path must respect the holding-time and jump rules implied by that generator.
Let \((X_t)_{t\ge0}\) be a CTMC on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its generator is \(Q=(q_{ij})\). For distinct states \(i,j\), \(q_{ij}\) is the instantaneous rate of a jump from \(i\) to \(j\); \(q_{ii}\) is the diagonal entry. In this tutorial, the chain has no killing or unrecorded destination: all jumps remain in the stated state space.
The diagonal is not another destination rate. Its negative gives the total rate of leaving the state. When \(q_i>0\), the time spent in state \(i\) before the next jump has the exponential distribution with rate \(q_i\), and the probability that the next state is \(j\ne i\) is \(q_{ij}/q_i\). A destination with \(q_{ij}=0\) cannot be the next state. When \(q_i=0\), the process stays in \(i\) forever.
Generator Checks and Why They Are Necessary
Proof. For \(i\ne j\), the rate is defined by the small-time limit \(q_{ij}=\lim_{h\downarrow0}\mathbb{P}(X_h=j\mid X_0=i)/h\). Each probability in this limit is nonnegative, so \(q_{ij}\ge0\). For fixed \(i\), the transition probabilities over the finite state space sum to one. Subtracting the probability of remaining in \(i\), dividing by \(h\), and taking the generator limit gives \(\sum_{j\in S}q_{ij}=0\). Separating the diagonal term yields \(q_{ii}=-\sum_{j\ne i}q_{ij}\). The rates are finite for a finite-state generator. Conversely, a table satisfying these sign, finiteness, and row-sum conditions satisfies the stated definition of a conservative finite-state generator table. \(\square\)
In practice, check every row independently. First inspect all off-diagonal entries for negative values. Next add those entries to obtain the exit rate. The diagonal must be the negative of that sum. A row with all zero entries is a valid absorbing state. A row with a positive exit rate but a zero or positive diagonal is invalid.
Worked Example: Repairing a Row with the Wrong Diagonal
Consider states \(A,B,C\). A supplied table gives the following rates, with columns in the order \(A,B,C\):
Check the off-diagonal entries first. In row \(A\), the rates to \(B\) and \(C\) are \(2\) and \(1\), both nonnegative; the exit rate is \(2+1=3\). But the supplied diagonal is \(-2\), so the row sum is \(-2+2+1=1\), not zero. Row \(B\) has exit rate \(0+4=4\) and sum \(0-4+4=0\). Row \(C\) has exit rate \(0+0=0\) and sum \(0+0+0=0\).
Only the diagonal in row \(A\) needs correction. Set it to the negative exit rate, \(-3\). The corrected table is
Check: the row sums are \(-3+2+1=0\), \(0-4+4=0\), and \(0+0+0=0\). The exit rates are \(3,4,0\), respectively, and all off-diagonal rates are nonnegative. Thus \(C\) is absorbing, while \(A\) and \(B\) have positive exit rates.
Auditing Holding Times and Jumps
A path is usually reported as a sequence of visited states and the times at which the state changes. For a state \(i\) with \(q_i>0\), a completed sojourn of duration \(u\) must satisfy \(u>0\). Its holding-time density is \(q_i e^{-q_i u}\) for \(u>0\), so every strictly positive finite duration is compatible with the exponential model. It may be very unlikely, but it is not impossible merely because it is unusually short or long. The next state must also have a positive rate from \(i\).
Proof. If \(q_i>0\), the holding time \(H\) has exponential distribution with rate \(q_i\), so \(\mathbb{P}(H>u)=e^{-q_i u}\) for \(u\ge0\). Thus \(\mathbb{P}(H=0)=0\), \(\mathbb{P}(H<\infty)=1\), and its density \(q_i e^{-q_i u}\) is positive at every \(u>0\). Conditional on leaving \(i\), the probability of next entering \(j\) is \(q_{ij}/q_i\). This is zero exactly when \(q_{ij}=0\); when it is positive, the transition is allowed. If \(q_i=0\), the total rate of leaving is zero, so the holding time is infinite and there is no next jump. Finally, stopping observation at a finite horizon does not assert that the process jumped at that horizon: the observed last interval only says that no jump was recorded before observation ended. \(\square\)
There is an important qualification about the word “possible.” A continuous holding-time distribution assigns probability zero to any one exact numerical duration. Consequently, an exact fully specified sample path also usually has probability zero. In path checking, “compatible” means that the observed durations lie in the support of the appropriate distributions and that each recorded jump has positive rate. Durations in small intervals around compatible positive values have positive probability; a jump with rate zero does not.
Worked Example: Separating an Impossible Jump from a Valid Sojourn
Consider states \(0,1,2\), with rate table
Before using it, check the rows. Row \(0\) has exit rate \(2+0=2\) and sum \(-2+2+0=0\). Row \(1\) has exit rate \(1+3=4\) and sum \(1-4+3=0\). Row \(2\) has exit rate \(0+0=0\) and sum \(0+0+0=0\). All off-diagonal entries are nonnegative, so the table passes the generator checks.
Suppose a recorded path spends \(1/2\) time unit in state \(0\), then jumps to state \(1\). This jump is allowed because \(q_{01}=2>0\). The density of a completed \(1/2\)-unit holding time in state \(0\) is \(2e^{-2(1/2)}=2e^{-1}>0\). From state \(1\), a jump to state \(0\) is allowed because \(q_{10}=1>0\), and a jump to state \(2\) is allowed because \(q_{12}=3>0\). Their conditional probabilities are \(1/4\) and \(3/4\), since the exit rate is \(4\).
Now suppose the path instead records a jump from \(0\) to \(2\). That jump is impossible under this table: \(q_{02}=0\), so its conditional probability is \(0/2=0\). Changing the duration spent in state \(0\) cannot repair this inconsistency. The correction is to verify the recorded destination or, if the model specification requires a \(0\)-to-\(2\) jump, correct the rate table and recompute its diagonal so the row sum remains zero.
Check: a \(1/2\)-unit sojourn in state \(0\) is in the positive support of its exponential holding-time distribution, but the subsequent jump to state \(2\) is not in the support of its jump distribution. A path can therefore have a valid holding time and still be invalid because of its destination.
Zero Rates, Absorption, and Observation Endpoints
A zero exit rate has a stronger meaning than a very small positive rate. If \(q_i=0\), the chain cannot leave state \(i\). A reported positive-duration stay in \(i\) is compatible with absorption, but a completed jump out of \(i\) is not. In contrast, if \(q_i>0\), a long holding time has positive probability, even though its probability decreases as the duration increases.
Worked Example: Checking an Absorbing State and a Censored Endpoint
Let the states be \(A,B,C\), and suppose the table is
Row \(A\) has exit rate \(1+2=3\) and sum \(-3+1+2=0\). Row \(B\) has exit rate \(1+0=1\) and sum \(1-1+0=0\). Row \(C\) has exit rate \(0+0=0\) and sum \(0+0+0=0\). The table is valid; \(C\) is absorbing.
Suppose observation starts in \(A\), records a jump to \(B\) after \(1/3\) time unit, and then ends \(1\) time unit later with the chain still in \(B\). The first holding time is compatible: its density at \(1/3\) is \(3e^{-3(1/3)}=3e^{-1}>0\), and the conditional probability of jumping from \(A\) to \(B\) is \(1/3\). The final \(1\)-unit interval is censored, not a completed sojourn. The probability of no jump from \(B\) during that interval is \(e^{-1}>0\), so ending the observation there while the chain remains in \(B\) is compatible.
If the same record instead showed a completed jump from \(C\) to \(A\), it would be impossible because \(q_C=0\). It would not be repaired by assigning a positive holding duration in \(C\): the issue is the destination, not the length of time spent there.
Check: the observed rates used are \(q_A=3\), \(q_{AB}=1\), and \(q_B=1\), read directly from the table. The row sums are \(0,0,0\), and the final interval has survival probability \(e^{-1}\) under the stated rate in \(B\).
A Reliable Audit and a Common Mistake
For a supplied rate table and path, use the checks in this order:
- For each state, confirm every off-diagonal rate is nonnegative.
- Add the off-diagonal rates in that row. The diagonal must be the negative of this total, and the full row must sum to zero.
- For each completed stay in a state with positive exit rate, check that its duration is positive and finite.
- Check that every recorded destination has a strictly positive rate from the state just left.
- For a zero-exit-rate state, check that no later jump is recorded. Treat the final observation interval as censored unless a jump is explicitly observed.
Common mistake: treating the diagonal as an additional rate or “fixing” a row by changing its sign. For the first row in the repair example, the off-diagonal rates are \(2\) and \(1\), so the exit rate is \(3\). A wrong calculation is to keep the diagonal at \(-2\) and report an exit rate of \((-2)+2+1=1\). The diagonal is not a transition rate to be added; it is the negative total exit rate. The correct diagonal is \(-3\), and the row sum is \(-3+2+1=0\).
Another diagnostic error is to call a long positive holding time impossible simply because it seems too large. If the exit rate is positive and finite, every finite positive duration has positive exponential density. Conversely, a jump whose rate is zero is impossible, regardless of how plausible its timing looks. Separating support restrictions from relative likelihood is essential when reviewing simulated paths.
Check Your Understanding
For each question, distinguish algebraic validity from path compatibility.
- A row has off-diagonal rates \(2\) and \(5\). What must its diagonal entry be in a conservative generator?
- A state has exit rate \(4\). Is a completed holding time of \(0\) compatible with its exponential distribution? What about a duration of \(10\)?
- If \(q_{ij}=0\), can a path jump from \(i\) to \(j\) after an otherwise valid holding time?
- A path ends while the chain remains in a state with positive exit rate. Why is that final observed interval not necessarily a completed holding time?
- What does a row of all zeros imply about the state and any purported subsequent jump from it?