Reconstructing Paths from Holding Times and Jumps

From Rates to a Random Path

A generator describes how quickly a continuous-time Markov chain leaves each state and where it goes when it leaves. To turn those rates into a path, we need two ingredients at each visit: a holding time in the current state and a destination for the next jump. The holding time is exponential, while the destination is chosen according to the relative sizes of the outgoing rates. Repeating these choices constructs the successive states and jump times.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $S$ a finite or countable state space, and $(X_t)_{t\ge0}$ a continuous-time process. Let $Q=(q_{ij})$ be a rate matrix: $q_{ij}\ge0$ for $j\ne i$, each exit rate $q_i=\sum_{j\ne i}q_{ij}$ is finite, and $q_{ii}=-q_i$, so every row sums to zero. When $q_i>0$, the embedded jump chain has transition probabilities $p^J_{ij}=q_{ij}/q_i$ for $j\ne i$, and $p^J_{ii}=0$. When $q_i=0$, the process has no outgoing jump from $i$; we call $i$ absorbing for this construction, and do not define a next-jump probability there.

Definition: At each visit to state $i$ with $q_i>0$, draw a holding time $H$ with exponential distribution of rate $q_i$, so $\mathbb{P}(H>u)=e^{-q_i u}$ for $u\ge0$. Independently draw the next state $j$ according to $p^J_{ij}$. Use fresh independent random draws at successive visits. At a state with $q_i=0$, set $H=\infty$, so the path stays there.

One explicit implementation uses independent unit-rate exponential variables and independent uniform variables. At a visit to $i$ with $q_i>0$, divide a unit-rate exponential variable by $q_i$ to obtain $H$. Use the uniform variable to select $j$ from the countable distribution $(p^J_{ij})_{j\in S}$, for example by cumulative sums in a fixed ordering of $S$. The holding time and destination are independent, and the fresh draws make the choices at different visits independent. Starting from a specified state, add each holding time to the preceding jump time; the state is constant between successive jump times.

The Path-Law Formula

Theorem: Suppose $X_0=i_0$ is fixed and the construction above is used. Consider a possible sequence of $m\ge1$ jumps through states $i_0,i_1,\ldots,i_m$, where $q_{i_{r-1}}>0$ and $i_r\ne i_{r-1}$ for each $r$. Write $0<t_1<\cdots<t_m<T$ for the jump times and $t_0=0$. The joint density for these successive states and jump times, together with no further jump before $T$, is $$ \left(\prod_{r=1}^{m}e^{-q_{i_{r-1}}(t_r-t_{r-1})}q_{i_{r-1},i_r}\right)e^{-q_{i_m}(T-t_m)}. $$ If $q_{i_m}=0$, the final survival factor is $1$. The formula is a density in the time coordinates $t_1,\ldots,t_m$; it is not the probability of the jump times being exactly those values.

Proof. Set $H_r=t_r-t_{r-1}$. At visit $r-1$, the holding-time density at $H_r>0$ is $q_{i_{r-1}}e^{-q_{i_{r-1}}H_r}$. Independently, the probability of choosing $i_r$ is $q_{i_{r-1},i_r}/q_{i_{r-1}}$. Multiplying these gives $e^{-q_{i_{r-1}}H_r}q_{i_{r-1},i_r}$, the density for that holding time and destination. The fresh independent draws at successive visits make the factors for the first $m$ jumps multiply. After the $m$th jump, the probability of no additional jump during the remaining time $T-t_m$ is $e^{-q_{i_m}(T-t_m)}$ when $q_{i_m}>0$, and is $1$ when $q_{i_m}=0$. Multiplying by this last survival probability gives the displayed density. $\square$

This formula records both parts of path reconstruction: the time spent in each visited state and the rate of choosing each next state. It also follows directly that the construction has the specified local jump rates. For a fixed state $i$ with $q_i>0$, the probability that the next jump occurs within $h>0$ and goes to $j\ne i$ is $(1-e^{-q_i h})q_{ij}/q_i$. As $h$ decreases to zero, this is $q_{ij}h+O(h^2)$, because $1-e^{-q_i h}=q_i h+O(h^2)$. The probability of no jump in that interval is $e^{-q_i h}=1-q_i h+O(h^2)$.

Proof of the local-rate statement. The exponential holding time gives $\mathbb{P}(H\le h)=1-e^{-q_i h}$, and the independent destination draw selects $j$ with probability $q_{ij}/q_i$. Multiplying yields the stated probability. The expansions follow from the Taylor expansion of the exponential at zero, with $q_i$ fixed and finite. For $q_i=0$, no jump occurs, which agrees with all off-diagonal rates being zero. $\square$

Worked Paths and Exact Probabilities

Worked Example: Choosing a Destination from Competing Rates

From state $A$, the rate to $B$ is $2$ and the rate to $C$ is $1$. Find the probability that the first jump occurs by time $\frac{\ln 2}{3}$ and goes to $B$.

The generator row for $A$, in the order $A,B,C$, is $(-3,2,1)$, since $q_A=2+1=3$; its entries sum to $-3+2+1=0$. The embedded jump probabilities from $A$ are $p^J_{AB}=2/3$ and $p^J_{AC}=1/3$, which sum to $1$. The holding time has rate $3$, independently of the destination. Therefore, $$ \mathbb{P}\left(H\le\frac{\ln 2}{3},\ J=B\right) =\left(1-e^{-3(\ln 2/3)}\right)\frac{2}{3} =\left(1-\frac12\right)\frac23 =\frac13. $$

Check: The probability of a jump by the stated time is $1/2$; conditional on a jump, the chance of $B$ is $2/3$. Their product is $1/3$, as calculated. The complementary destination probability is $1/3$, so the two destination probabilities sum to $1$.

Worked Example: The Density of a Two-Jump Path

Let $S=\{A,B,C\}$, with generator, in that order, $$ Q= \begin{bmatrix} -3&2&1\\ 1&-1&0\\ 1&2&-3 \end{bmatrix}. $$ Starting from $A$, find the joint density for the path $A\to C\to B$, with jumps at $t_1=\frac13$ and $t_2=1$, and no further jump by $T=\frac43$.

Each generator row sums to zero: $-3+2+1=0$, $1-1+0=0$, and $1+2-3=0$. The exit rates are $q_A=3$, $q_B=1$, $q_C=3$. The embedded probabilities are: from $A$, $p^J_{AB}=2/3$ and $p^J_{AC}=1/3$; from $B$, $p^J_{BA}=1$; from $C$, $p^J_{CA}=1/3$ and $p^J_{CB}=2/3$. Each row of these jump probabilities sums to $1$.

The first holding interval has length $t_1-t_0=1/3$, and the jump rate from $A$ to $C$ is $q_{AC}=1$. The second holding interval has length $t_2-t_1=1-1/3=2/3$, and $q_{CB}=2$. The final interval in $B$ has length $T-t_2=4/3-1=1/3$. The formula gives $$ e^{-3(1/3)}(1)\,e^{-3(2/3)}(2)\,e^{-1(1/3)} =2e^{-1-2-1/3} =2e^{-10/3}. $$

This is a density with respect to the two jump-time coordinates, not a positive probability that jumps occur at exactly $1/3$ and $1$. A probability is obtained by integrating the density over a region of possible ordered times. Check: the three holding intervals total $1/3+2/3+1/3=4/3=T$, and the two jump-rate factors are $q_{AC}=1$ and $q_{CB}=2$, as used.

Worked Example: A Jump into a State with Zero Exit Rate

Let $S=\{1,2\}$, with generator $$ Q= \begin{bmatrix} -4&4\\ 0&0 \end{bmatrix}. $$ Starting at $1$, find the probability that the jump to $2$ has occurred by time $\frac{\ln 2}{4}$, and describe the path afterward.

The rows sum to zero: $-4+4=0$ and $0+0=0$. At $1$, $q_1=4$ and the only possible jump is to $2$, so $p^J_{12}=4/4=1$. At $2$, $q_2=0$, so there is no next jump and the path remains at $2$. The probability of jumping by the stated time is $$ \mathbb{P}_1\left(H\le\frac{\ln 2}{4}\right) =1-e^{-4(\ln 2/4)} =1-\frac12 =\frac12. $$

Check: The probability of still being at $1$ at time $\frac{\ln 2}{4}$ is $e^{-4(\ln 2/4)}=1/2$. Thus the probabilities of having jumped and not yet having jumped sum to $1$; once the jump occurs, the path stays at $2$.

Reading the Construction Correctly

A common mistake is to treat outgoing rates as though they were destination probabilities. In the first example, that would assign probability $2$ to jumping from $A$ to $B$ and probability $1$ to jumping to $C$. These are rates, and they sum to $3$, not to $1$; neither can be used as a probability. The correction is to divide each outgoing rate by the total exit rate: $2/3$ for $B$ and $1/3$ for $C$. The total exit rate $3$, not either individual destination probability, is the parameter of the holding-time distribution.

A second distinction is between a particular path’s density and the probability of a set of paths. Continuous holding times assign probability zero to any one exact jump time. The path-density formula gives a value that must be integrated over a time region to obtain a probability. For instance, the first example calculated an event probability by specifying a time interval, while the second evaluated a density at specified times.

The construction specifies successive jumps and the path between them. If infinitely many jumps accumulate in a finite time, further analysis is needed to define the path after that accumulation; this tutorial makes no claim that accumulation cannot occur for every countable-state rate matrix. Up to any such accumulation, the holding times and embedded transitions give the path segment and its law.

Check Your Understanding

For each question, distinguish holding-time rates from jump probabilities, and state whether the requested quantity is a probability or a density.

At a state with rates $q_{i1}=3$ and $q_{i2}=1$, what are the exit rate and the two embedded jump probabilities?
If the exit rate is $5$, what is the probability of no jump during an interval of length $u\ge0$?
For the two-jump formula, explain why the last exponential factor is a survival probability rather than another jump-rate factor.
At a state with exit rate zero, what holding time does the construction assign, and what does the path do?
Why does evaluating the path formula at fixed jump times give a density rather than the probability of those exact times?

Reconstructing Paths from Holding Times and Jumps

What You'll Learn