Tutorials › Stochastic Processes › Uniqueness From Holding Times and Jump Probabilities

Home  /  Tutorials  /  Continuous-Time Markov Chains and Generator Matrices

Continuous-Time Markov Chains and Generator Matrices · Tutorial 480 of 994

Uniqueness From Holding Times and Jump Probabilities

See why finite exit rates determine each holding time and next state, and how nonexplosion turns those successive choices into a unique path law.

Advanced 12 min read

What You'll Learn

  • Define a countable-state generator and its exit rates.
  • Derive exponential holding times from the Markov property and the generator.
  • Derive the conditional probabilities of each next destination.
  • Prove that the generator determines the path law when the chain is nonexplosive.
  • Identify what nonexplosion contributes to the uniqueness argument.
  • Compute path probabilities from holding times and jump destinations.

From Local Rates to an Entire Path

A generator records the instantaneous rates at which a continuous-time Markov chain leaves each state and moves to each other state. The uniqueness question is whether those local rates determine the chain’s whole law, not merely its behavior over a very short time. For a nonexplosive chain, the answer is yes once the initial distribution is specified: the generator fixes the distribution of each holding time and the conditional distribution of the next state, and these determine the successive path segments.

Let \(S\) be a finite or countable state space. A continuous-time Markov chain \((X_t)_{t\ge0}\) has state space \(S\), time index \(t\ge0\), and is defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). We use its natural filtration \((\mathcal{F}_t)_{t\ge0}\). The chain is assumed to have right-continuous paths and finite exit rates. Its generator is \(Q=(q_{ij})\), where, for \(i\ne j\), \(q_{ij}\ge0\), and

$$ q_i=\sum_{j\ne i}q_{ij}<\infty,\qquad q_{ii}=-q_i. $$

Thus every row of \(Q\) sums to \(0\). The generator entries are the infinitesimal transition rates: \(q_{ij}=\lim_{h\downarrow0}\mathbb{P}_i(X_h=j)/h\) for \(j\ne i\), where \(\mathbb{P}_i\) means the chain starts in state \(i\). A chain is nonexplosive if, with probability \(1\), it makes only finitely many jumps on every bounded time interval. The uniqueness claim below is conditional on nonexplosion: two such chains with the same \(Q\) and the same initial distribution have the same law.

Definition: Starting from state \(i\), let \(H_i\) be the time until the first jump, and let \(J_i\) be the state entered at that jump. When \(q_i>0\), the holding time is exponential with rate \(q_i\), and the jump-destination probabilities are \(r_{ij}=q_{ij}/q_i\) for \(j\ne i\). If \(q_i=0\), there is no jump from \(i\); we set \(H_i=\infty\).

These distributions are not additional free choices once \(Q\) is given. The exponential holding-time law follows from the Markov property and the total rate of leaving \(i\); the destination probabilities follow by separating the individual rates from that total. We establish both facts before using them in the uniqueness argument.

What the Generator Fixes at One Jump

Fix a starting state \(i\) with \(q_i>0\). Write \(G(t)=\mathbb{P}_i(H_i>t)\). Conditional on still being in \(i\) at time \(t\), the future evolution starts afresh from \(i\), by the time-homogeneous Markov property. Consequently \(G(t+s)=G(t)G(s)\) for \(s,t\ge0\). The generator’s total exit rate gives \(G(h)=1-q_i h+o(h)\) as \(h\downarrow0\). This multiplicative survival law and its small-time rate imply an exponential distribution.

Proof. For fixed \(t\ge0\), use the multiplicative identity with \(n\) equal intervals to get \(G(t)=G(t/n)^n\). As \(n\to\infty\), \(G(t/n)=1-q_i t/n+o(1/n)\). Therefore \(G(t)=\lim_{n\to\infty}(1-q_i t/n+o(1/n))^n=e^{-q_i t}\), the exponential limit. Thus \(H_i\) has survival function \(e^{-q_i t}\). \(\square\)

Next define \(r_{ij}=\mathbb{P}_i(J_i=j)\) for \(j\ne i\). The Markov property implies that, conditional on the chain remaining in \(i\) up to time \(s\), its subsequent evolution has the same law as a fresh chain started in \(i\). Hence the eventual destination distribution does not depend on how long the chain has already held in \(i\); the first holding time and its destination are independent. The probability of a first jump to \(j\) by time \(h\) is therefore \(r_{ij}(1-e^{-q_i h})\).

To relate this probability to \(q_{ij}\), the difference between “the first jump is to \(j\) by time \(h\)” and “\(X_h=j\)” is bounded by the probability of at least two jumps by time \(h\). This probability is \(o(h)\). Indeed, after the first jump, the chain is at some \(k\ne i\); its probability of another jump within \(h\) is at most \(1-e^{-q_kh}\). Averaging this quantity over the first destination gives a term tending to \(0\) as \(h\downarrow0\), by bounded convergence on the countable destination distribution. The chance of a first jump by \(h\) is at most \(q_i h\), so the probability of two or more jumps is \(o(h)\). It follows that

$$ q_{ij} =\lim_{h\downarrow0}\frac{\mathbb{P}_i(X_h=j)}{h} =\lim_{h\downarrow0}\frac{r_{ij}(1-e^{-q_i h})+o(h)}{h} =q_i r_{ij}. $$

Since \(q_i=\sum_{j\ne i}q_{ij}>0\), summing \(r_{ij}=q_{ij}/q_i\) over \(j\ne i\) gives \(1\). Thus the generator fixes the full one-jump rule: the holding time has rate \(q_i\), and the next-state probabilities are \(q_{ij}/q_i\).

Theorem: Let two right-continuous, nonexplosive continuous-time Markov chains on the same finite or countable state space \(S\) have finite exit rates and the same generator \(Q\). If their initial distributions are the same, then their path laws are the same. Equivalently, given \(Q\) and the initial distribution, there is at most one nonexplosive chain law.

Proof. Denote the initial distribution by the row vector \(\mu\). For either chain, conditional on the current state being \(i\) and \(q_i>0\), the next holding time has survival \(e^{-q_i t}\), independently of the next state, and the next-state probability is \(q_{ij}/q_i\). These conditional distributions depend only on \(Q\). If \(q_i=0\), the chain stays in \(i\) forever, also as determined by \(Q\).

Starting with distribution \(\mu\), the two chains therefore have the same distribution for their initial state, first holding time and first destination. Applying the same conditional rule after that destination shows inductively that they have the same distribution for every finite sequence of visited states and holding times. This induction includes paths that stop making jumps at a state with zero exit rate.

For any fixed \(T<\infty\), nonexplosion says that the path on \([0,T]\) has finitely many jumps with probability \(1\). The path on that interval is determined by its initial state, its successive holding times and destinations up to \(T\). The common distributions of these data give the same distribution for the path on \([0,T]\): for each possible finite number of jumps, its event and path are specified by the corresponding finite sequence and the condition that the next holding time extends past \(T\). Taking the countable union over the possible numbers of jumps preserves equality of probabilities. Since this holds for every finite \(T\), the two chains have the same path law. \(\square\)

The theorem is a uniqueness statement, not an existence theorem: it says that at most one nonexplosive law can have the specified generator and initial distribution. In particular, it does not assert that every countable-state \(Q\)-matrix produces a nonexplosive chain.

Computing with the One-Jump Rule

Worked Example: A Two-State Path

Consider a chain on \(S=\{1,2\}\), with time \(t\ge0\), generator \(Q=\begin{bmatrix}-2&2\\3&-3\end{bmatrix}\), and initial state \(1\). Work on a probability space with the chain’s natural filtration. The row sums are \(-2+2=0\) and \(3-3=0\), as required. Find the probability that exactly one jump has occurred by time \(t\).

The first holding time in state \(1\) has rate \(q_1=2\), and the first jump must be to state \(2\). After that, the holding time in state \(2\) has rate \(q_2=3\). Exactly one jump by time \(t\) means the first jump occurs at time \(s\le t\) and the next holding time exceeds \(t-s\). The density of the first holding time at \(s\) is \(2e^{-2s}\), so

$$ \begin{aligned} \mathbb{P}_1(\text{exactly one jump by }t) &=\int_0^t 2e^{-2s}e^{-3(t-s)}\,ds\\ &=2e^{-3t}\int_0^t e^s\,ds\\ &=2(e^{-2t}-e^{-3t}). \end{aligned} $$

At \(t=\log 2\), this is \(2((1/2)^2-(1/2)^3)=2(1/4-1/8)=1/4\). The probability of no jumps is \(e^{-2\log2}=1/4\). Both probabilities are nonnegative, and the one-jump event requires the chain to be in state \(2\) at time \(t\), consistent with the specified transitions.

Worked Example: Splitting the First Exit Rate

Let \(S=\{1,2,3\}\), and take \(Q=\begin{bmatrix}-6&4&2\\3&-3&0\\0&0&0\end{bmatrix}\). Each row sums to zero: \(-6+4+2=0\), \(3-3+0=0\), and \(0+0+0=0\). Starting in state \(1\), find the probability that the first jump is to state \(3\) and occurs by time \(t\).

The total exit rate from state \(1\) is \(q_1=6\). The holding time is exponential with rate \(6\), while the probability of destination \(3\), conditional on a jump, is \(q_{13}/q_1=2/6=1/3\). Independence of holding time and destination gives

$$ \mathbb{P}_1(H_1\le t,\ J_1=3) =\frac{1}{3}(1-e^{-6t}). $$

For comparison, the corresponding probability of a first jump to state \(2\) by time \(t\) is \((4/6)(1-e^{-6t})=(2/3)(1-e^{-6t})\). Adding the two destination-specific probabilities gives \(1-e^{-6t}\), the probability of any first jump by time \(t\). This checks both the rate split and the destination probabilities.

Worked Example: Two Successive Holding Times

Consider \(S=\{1,2,3\}\), initial state \(1\), and generator \(Q=\begin{bmatrix}-1&1&0\\0&-1&1\\0&0&0\end{bmatrix}\). The row sums are \(-1+1+0=0\), \(0-1+1=0\), and \(0+0+0=0\). Find the probability that exactly two jumps have occurred by time \(t\).

The first two holding times are independent exponential random variables of rate \(1\), and the destinations are necessarily \(1\to2\to3\). State \(3\) has exit rate \(0\), so after the second jump no further jump is possible. The event in question is therefore that the sum of the first two holding times is at most \(t\). Conditioning on the first holding time \(s\), the probability that it occurs at \(s\) and the second jump occurs during the remaining time is \(e^{-s}(1-e^{-(t-s)})\,ds\). Integrating gives

$$ \begin{aligned} \mathbb{P}_1(\text{exactly two jumps by }t) &=\int_0^t e^{-s}\bigl(1-e^{-(t-s)}\bigr)\,ds\\ &=(1-e^{-t})-te^{-t}\\ &=1-(1+t)e^{-t}. \end{aligned} $$

At \(t=1\), the probability is \(1-2e^{-1}=1-2/e\). A check by complementation gives the same result: no first jump by time \(1\) has probability \(e^{-1}\), and exactly one jump by time \(1\) has probability \(e^{-1}\), since the two successive holding rates are both \(1\). Thus the probability of two jumps is \(1-e^{-1}-e^{-1}=1-2/e\).

Why Nonexplosion Matters

The proof uses nonexplosion at the point where it reconstructs a whole bounded-time path from successive jumps. If infinitely many jumps can occur before some finite time, an infinite sequence of holding times and destinations may accumulate at that time. The generator still specifies each individual holding-time and destination rule, but the path after the accumulation is not settled by the finite-jump reconstruction. Nonexplosion ensures that this gap occurs with probability zero.

Common mistake. The off-diagonal rate \(q_{ij}\) is not itself the probability that the next jump goes to \(j\). For the second example, saying that the next jump from state \(1\) goes to state \(3\) with probability \(2\) is invalid: probabilities cannot exceed \(1\), and the rates in that row sum to \(6\). The correction is to divide the individual rate by the total exit rate: \(q_{13}/q_1=2/6=1/3\). The holding-time rate remains \(6\), not \(1/3\).

The uniqueness result is useful whenever a chain is specified through a rate table or constructed by a different mechanism. If the resulting process has the same generator, the same initial law and no explosion, its path law is fixed; there is no additional freedom to choose different holding-time or jump-destination rules.

Check Your Understanding

Use the generator-to-path argument to answer each question. When computing probabilities, state whether the event concerns the first jump or the entire path up to a time.

  1. For a state \(i\) with \(q_i=5\), what is the probability that the chain remains in \(i\) for more than time \(t\)?
  2. If \(q_{i2}=3\) and \(q_i=5\), what is the conditional probability that the next jump from \(i\) is to state \(2\)?
  3. Why does the generator determine the distribution of the first holding time and first destination jointly?
  4. In the two-state example, verify the probability of exactly one jump at \(t=\log 2\) by substituting \(e^{-\log2}=1/2\) into the displayed formula.
  5. Where in the uniqueness proof is nonexplosion needed, and what issue can arise if infinitely many jumps accumulate in finite time?

Previous

Next

Back to Tutorials