37.05.08 · probability / 05-markov-chains

Continuous-Time Markov Chains I: Q-Matrices, Jump Chains, and Holding Times

shipped3 tiersLean: none

Anchor (Master): Norris 1997 *Markov Chains* (Cambridge) §2.1-2.8 (jump-chain/holding-time construction, explosion, the backward equation); Chung 1967 *Markov Chains with Stationary Transition Probabilities* 2e Ch. II; Anderson 1991 *Continuous-Time Markov Chains: An Applications-Oriented Approach* (Springer) Ch. 2

Intuition Beginner

A continuous-time Markov chain models a system that hops between a list of states, like a discrete-time chain, but now the clock runs continuously: the system sits in a state for a random length of time, then jumps to a new state, then waits again, and so on. The memoryless rule still holds, but it now has two parts. While the system sits in a state, only the current state decides how long the wait tends to be and where the next jump is likely to go. Nothing about the earlier history matters, and — this is the new ingredient — not even how long the system has already been waiting matters.

That last point forces the waiting times to be of one special kind. If the remaining wait should not depend on how long you have already waited, the wait must follow the "exponential" pattern: a continuous version of repeatedly flipping a coin to decide whether to jump now. Each state $i$ has a rate $q_{i}$ that sets how fast its exponential clock runs. A large rate means short stays and frequent jumps; a small rate means long, patient stays.

So a continuous-time chain is built from two ingredients you can picture separately. First, an ordinary discrete chain that says, "when you do jump out of state $i$ , here are the odds of where you land." This is the jump chain. Second, for each state, a single number — the rate $q_{i}$ — that runs the exponential waiting clock. Bundle the jump odds and the rates together and you get one table, the generator or $Q$ -matrix, that packages both the where and the when.

One subtlety gives the theory its only real surprise. If the rates keep getting bigger as the system wanders into faster and faster states, the waits can shrink so quickly that infinitely many jumps pile up into a finite stretch of time. The chain then "runs off the end of the clock," an event called explosion. Most chains do not explode, and there is a clean test telling them apart.

The one-sentence takeaway: a continuous-time chain waits an exponential time on each state, set by that state's rate, then jumps according to a discrete jump chain, and the rate-and-jump data is exactly the $Q$ -matrix — provided the jumps do not pile up into an explosion.

Visual Beginner

Picture three states drawn as circles, with the system tracing a step-like path in time: flat stretches where it waits, and sudden vertical hops where it jumps.

Left: the chain as a labeled graph, each circle carrying a rate that runs its exponential clock; the arrows out of a circle carry the jump-chain odds. Right: a sample path as a staircase in time — flat holding times set by the rates, vertical jumps set by the jump chain. The inset shows the one pathology, explosion, where shrinking waits crowd infinitely many jumps into a finite time.

Worked example Beginner

We follow a two-state chain. State $1$ has rate $q_{1} = 2$ (so its average wait is $1/2$ ), and state $2$ has rate $q_{2} = 1$ (average wait $1$ ). From state $1$ the only place to jump is state $2$ , and from state $2$ the only place to jump is state $1$ , so the jump chain just alternates $1, 2, 1, 2, \dots$ .

Step 1. Start in state $1$ . The wait is exponential with rate $2$ . The average wait is $1/ q_{1} = 1/2$ time unit. Say this particular wait comes out to $0.4$ .

Step 2. At time $0.4$ the system jumps. The jump chain from state $1$ sends it to state $2$ with chance $1$ , so it lands in state $2$ .

Step 3. Now in state $2$ , the wait is exponential with rate $1$ , average $1/ q_{2} = 1$ . Say this wait is $0.9$ . The system holds state $2$ from time $0.4$ until time $0.4 + 0.9 = 1.3$ .

Step 4. At time $1.3$ it jumps back to state $1$ , and the pattern repeats with a fresh exponential wait of rate $2$ .

Step 5. Read off the long-run fraction of time in each state. On average the system spends $1/2$ a unit in state $1$ and $1$ unit in state $2$ per round trip, so out of every $1.5$ units it spends $1$ in state $2$ . The fraction of time in state $2$ is $1/1.5 = 2/3$ , and in state $1$ it is $1/3$ .

What this tells us: the rates alone fixed the average waits, the jump chain alone fixed the order of visits, and combining them gave both a sample path and a long-run time split. The state with the slower clock (smaller rate) collects more of the time, which matches the picture of patient versus hurried states.

Check your understanding Beginner

Exercise (easy, multiple choice).

In a continuous-time Markov chain, why must the waiting time in each state follow the exponential pattern?

A. Because the remaining wait should not depend on how long the system has already waited B. Because exponential numbers are easy to add up C. Because every state must be visited equally often D. Because the rates are always whole numbers

Hint

The memoryless rule in continuous time says the clock forgets how long it has already been running.

Answer

A. The remaining wait does not depend on the elapsed wait. This memoryless requirement singles out the exponential pattern as the only continuous waiting law with that property. Feedback-correct: memorylessness in continuous time is exactly the lack-of-aging property of the exponential clock. Feedback-wrong: B, C, and D describe conveniences or unrelated facts, not the reason the wait must be exponential.

Formal definition Intermediate+

Throughout, $I$ is a countable state space and time is continuous, indexed by $t \in [0, \infty)$ . All random objects live on a probability space $(Ω, F, P)$ 37.01.01. The discrete-time apparatus of stochastic matrices, the simple and strong Markov properties, and the finite-dimensional law from 37.05.01 is assumed.

Definition ( $Q$ -matrix; generator). A $Q$ -matrix (or generator) on $I$ is a family $Q = (q_{ij})_{i, j \in I}$ such that $0 \leq - q_{ii} < \infty for all i, q_{ij} \geq 0 for all i \neq = j, j \in I \sum q_{ij} = 0 for all i .$ Each row therefore sums to zero. Write $q_{i} := - q_{ii} = \sum_{j \neq = i} q_{ij}$ for the total jump rate (the holding rate) out of $i$ . A $Q$ -matrix with $q_{i} < \infty$ for every $i$ (built into the definition above) is stable; if moreover $sup_{i} q_{i} < \infty$ it is uniform or bounded. The matrix is conservative when the row sums are exactly zero, as imposed here; allowing $\sum_{j} q_{ij} < 0$ corresponds to an extra killing rate $q_{i} + q_{ii} \geq 0$ , excluded in this unit.

Definition (jump matrix). The jump matrix (or jump chain matrix) $Π = (π_{ij})_{i, j \in I}$ associated with $Q$ is the stochastic matrix $π_{ij} = \frac{q _{ij}}{q _{i}} for j \neq = i when q_{i} > 0, π_{ii} = 0 when q_{i} > 0, π_{ii} = 1, π_{ij} = 0 (j \neq = i) when q_{i} = 0.$ A state with $q_{i} = 0$ is absorbing: once entered, it is never left, and $Π$ keeps the chain there. For $q_{i} > 0$ the row $π_{i \cdot}$ is the conditional distribution of the next state given a jump out of $i$ , and $q_{ij} = q_{i} π_{ij}$ recovers the off-diagonal generator entries. Thus the pair $(Π, (q_{i})_{i})$ and the matrix $Q$ carry identical information.

Definition (minimal chain via jump chain and holding times). Let $(Y_{n})_{n \geq 0}$ be a discrete-time $Markov (λ, Π)$ chain 37.05.01, the jump chain. Independently, let $(E_{n})_{n \geq 1}$ be i.i.d. $Exp (1)$ random variables, and set the holding times $S_{n} = E_{n} / q_{Y_{n - 1}}$ (with $S_{n} = \infty$ if $q_{Y_{n - 1}} = 0$ ). The jump times are $J_{0} = 0$ , $J_{n} = S_{1} + \dots + S_{n}$ , and the explosion time is $ζ = sup_{n} J_{n} = \sum_{n \geq 1} S_{n}$ . The minimal continuous-time chain is $X_{t} = Y_{n} for J_{n} \leq t < J_{n + 1}, X_{t} = \partial for t \geq ζ,$ where $\partial$ is an adjoined cemetery state used only to define $X_{t}$ past explosion; before $ζ$ the path is right-continuous and piecewise constant with jumps at the $J_{n}$ . Conditional on $Y_{n - 1} = i$ , the holding time $S_{n}$ is $Exp (q_{i})$ and is independent of $Y_{n}$ and of the past, the defining structural fact of the construction.

Definition (explosion and non-explosion). The chain is non-explosive (or honest) from $i$ if $P_{i} (ζ = \infty) = 1$ , and explosive if $P_{i} (ζ < \infty) > 0$ for some $i$ . Non-explosion means $X_{t} \in I$ for all $t$ almost surely, so the cemetery $\partial$ is never reached and $X$ is a genuine $I$ -valued process for all time.

Counterexamples to common slips Intermediate+

The $Q$ -matrix is not a stochastic matrix. Its rows sum to $0$ , not $1$ , and its diagonal is non-positive. The associated transition semigroup $P (t) = e^{tQ}$ (when defined) is stochastic; $Q$ is its derivative at $t = 0$ , the continuous-time analogue of the discrete generator $P - I_{d}$ of 37.05.01, not of $P$ itself.
Holding times are exponential, not the increments of the jump chain. The randomness splits cleanly: the jump chain $(Y_{n})$ decides where, the exponentials decide when, and the two are independent given the visited states. Confusing the holding rate $q_{i}$ with a transition probability conflates the clock with the routing.
$π_{ii} = 0$ for a non-absorbing state. The jump chain never stays put when $q_{i} > 0$ ; self-transitions of the continuous chain are invisible because a jump from $i$ to $i$ would not change the path. Self-loops in $Q$ are therefore meaningless — only off-diagonal $q_{ij}$ carry information.
Explosion is genuine and rate-driven. A finite-state $Q$ -matrix, or any bounded one with $sup_{i} q_{i} < \infty$ , never explodes; explosion needs $q_{i} \to \infty$ along a path the jump chain can traverse fast enough. The Markov property alone does not rule it out.

Key theorem with proof Intermediate+

Theorem (jump chain and holding times $\Leftrightarrow$ $Q$ -matrix; the competing-exponentials law). Let $Q$ be a $Q$ -matrix on $I$ with jump matrix $Π$ and rates $(q_{i})$ . Construct $(X_{t})$ as in the minimal-chain definition. Then for a state $i$ with $q_{i} > 0$ , started at $X_{0} = i$ :

(a) the holding time $S_{1} = in f {t > 0 : X_{t} \neq = i}$ is $Exp (q_{i})$ ;

(b) the first jump target $X_{S_{1}} = Y_{1}$ has law $π_{i \cdot}$ , i.e. $P_{i} (Y_{1} = j) = q_{ij} / q_{i}$ ;

Conversely, if a process holds $i$ for an $Exp (q_{i})$ time and then jumps to $j \neq = i$ with probability $π_{ij}$ , independently, its generator entries are $q_{ij} = q_{i} π_{ij}$ off-diagonal and $q_{ii} = - q_{i}$ , recovering $Q$ ^{[Norris 1997 §2.1-2.2]}.

Proof. Model the dynamics out of $i$ by a family of independent competing exponential clocks. For each $j \neq = i$ with $q_{ij} > 0$ , let $T_{j} \sim Exp (q_{ij})$ be independent across $j$ , and let the chain jump to whichever rings first.

Step 1 (the minimum of independent exponentials). Let $T = min_{j \neq = i} T_{j}$ . For $t \geq 0$ , independence gives $P_{i} (T > t) = j \neq = i \prod P (T_{j} > t) = j \neq = i \prod e^{- q_{ij} t} = exp (- t j \neq = i \sum q_{ij}) = e^{- q_{i} t},$ since $\sum_{j \neq = i} q_{ij} = q_{i}$ . Hence $T \sim Exp (q_{i})$ , proving (a) with $S_{1} = T$ .

Step 2 (which clock rings first). The probability that clock $j$ is the strict minimum is computed by conditioning on $T_{j} = s$ and requiring every other clock to exceed $s$ : $P_{i} (j rings first) = \int_{0}^{\infty} q_{ij} e^{- q_{ij} s} k \neq = i, j \prod e^{- q_{ik} s} d s = \int_{0}^{\infty} q_{ij} e^{- q_{i} s} d s = \frac{q _{ij}}{q _{i}} = π_{ij},$ using $q_{ij} + \sum_{k \neq = i, j} q_{ik} = q_{i}$ in the exponent. This proves (b): the jump target has law $π_{i \cdot}$ .

Step 3 (independence of when and where). Compute the joint law of the first-ring time and its identity. For the event that $j$ rings first and this happens after time $t$ , $P_{i} (j first, T > t) = \int_{t}^{\infty} q_{ij} e^{- q_{i} s} d s = \frac{q _{ij}}{q _{i}} e^{- q_{i} t} = π_{ij} P_{i} (T > t) .$ The joint probability factors into the marginal $π_{ij}$ of the target and the marginal $e^{- q_{i} t}$ of the time, so $Y_{1}$ and $S_{1}$ are independent, proving (c). The competing-exponentials model therefore produces exactly an $Exp (q_{i})$ holding time and an independent $Π$ -distributed jump, which is the minimal-chain construction; and the lack-of-memory of the exponential makes the resulting process Markov, with the same data $(Y_{n}, S_{n})$ regenerating at each jump by the strong Markov property of $(Y_{n})$ 37.05.01.

Converse. Given holding rate $q_{i}$ and jump law $π_{i \cdot}$ , set $q_{ij} = q_{i} π_{ij}$ for $j \neq = i$ and $q_{ii} = - q_{i}$ . Then $q_{ij} \geq 0$ off-diagonal and $\sum_{j} q_{ij} = - q_{i} + q_{i} \sum_{j \neq = i} π_{ij} = - q_{i} + q_{i} = 0$ , so $Q$ is a conservative $Q$ -matrix, and the construction run from $Q$ returns the given holding-and-jump dynamics. $□$

Bridge. This theorem builds toward the entire analytic theory of continuous-time chains and appears again in the forward and backward Kolmogorov equations, where $Q$ becomes the generator of the transition semigroup $P (t) = e^{tQ}$ . The foundational reason the construction is canonical is that the memoryless exponential is the unique continuous holding law compatible with the Markov property, so the only freedom left is the routing matrix $Π$ : this is exactly the split of the dynamics into a when (the rate $q_{i}$ ) and a where (the row $π_{i \cdot}$ ), and the identity $q_{ij} = q_{i} π_{ij}$ is the dictionary between them. The discrete jump chain $(Y_{n})$ is the embedded skeleton governed by the discrete theory of 37.05.01, so every recurrence, transience, and irreducibility question about $X$ reduces to one about $Y$ ; putting these together, the continuous-time chain is the jump chain with exponential clocks bolted on, and the $Q$ -matrix is dual to the diffusion generator $L$ of 02.15.03 — there the generator is a second-order differential operator on a continuum, here it is a row-zero-sum matrix on a countable set, the central insight being that both are the infinitesimal description of a Markov semigroup.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

A pure birth chain on $I = {0, 1, 2, \dots}$ has $q_{n, n + 1} = β_{n} > 0$ and no other off-diagonal entries. Write down its $Q$ -matrix, its jump matrix $Π$ , and the law of the holding time in state $n$ .

Hint

The only jump from $n$ is to $n + 1$ , so the routing is deterministic; the rate $q_{n} = β_{n}$ .

Answer

The generator has $q_{n, n + 1} = β_{n}$ , $q_{nn} = - β_{n}$ , all other entries zero; each row sums to zero. The jump matrix is deterministic, $π_{n, n + 1} = 1$ and $π_{nk} = 0$ otherwise, so the jump chain is the deterministic march $0, 1, 2, \dots$ . The holding time in state $n$ is $Exp (β_{n})$ , and the jump time to reach state $n$ is $J_{n} = \sum_{k = 0}^{n - 1} S_{k + 1}$ , a sum of independent exponentials with rates $β_{0}, \dots, β_{n - 1}$ . The explosion time is $ζ = \sum_{k \geq 0} S_{k + 1}$ , whose finiteness depends on $\sum_{k} 1/ β_{k}$ (Exercise 8).

Exercise 6 (medium, multiple choice).

Which statement correctly distinguishes the $Q$ -matrix $Q$ from the transition matrix $P$ of a discrete chain 37.05.01?

A. $Q$ has nonnegative entries and rows summing to $1$ B. $Q$ has nonpositive diagonal, nonnegative off-diagonal, and rows summing to $0$ C. $Q$ is always symmetric D. $Q$ equals $P$ minus the identity for every continuous chain

Hint

A $Q$ -matrix is a derivative of a semigroup at $t = 0$ , not a one-step probability table.

Answer

B. A $Q$ -matrix has $q_{ij} \geq 0$ for $j \neq = i$ , $q_{ii} \leq 0$ , and zero row sums. Option A describes a stochastic matrix. Option C fails in general — $Q$ is symmetric only for reversible chains with uniform stationary weight. Option D confuses the continuous generator with the discrete generator $P - I_{d}$ ; the relation is $P (t) = e^{tQ}$ , whose derivative at $0$ is $Q$ , not a fixed $P - I_{d}$ .

Exercise 7 (hard, symbolic).

For a chain with bounded rates $sup_{i} q_{i} =: \overset{q}{ˉ} < \infty$ , prove non-explosion: $P_{i} (ζ = \infty) = 1$ for every $i$ .

Hint

Each holding time $S_{n}$ stochastically dominates an $Exp (\overset{q}{ˉ})$ variable. Compare $ζ$ to a sum of i.i.d. $Exp (\overset{q}{ˉ})$ times.

Answer

Conditional on $Y_{n - 1}$ , the holding time $S_{n} \sim Exp (q_{Y_{n - 1}})$ with $q_{Y_{n - 1}} \leq \overset{q}{ˉ}$ , so $S_{n}$ stochastically dominates an independent $Exp (\overset{q}{ˉ})$ variable $\tilde{S}_{n}$ ; coupling gives $S_{n} \geq \tilde{S}_{n}$ almost surely with $(\tilde{S}_{n})$ i.i.d. $Exp (\overset{q}{ˉ})$ . Then $ζ = \sum_{n} S_{n} \geq \sum_{n} \tilde{S}_{n}$ . By the strong law of large numbers $\frac{1}{N} \sum_{n = 1}^{N} \tilde{S}_{n} \to 1/ \overset{q}{ˉ} > 0$ , so $\sum_{n} \tilde{S}_{n} = \infty$ almost surely, whence $ζ = \infty$ almost surely. (Equivalently, $E_{i} [ζ] = \sum_{n} E [S_{n}] \geq \sum_{n} 1/ \overset{q}{ˉ} = \infty$ and a Borel-Cantelli / SLLN argument upgrades this to $ζ = \infty$ a.s.) Bounded rates therefore forbid explosion; finite state spaces are the special case $\overset{q}{ˉ} = max_{i} q_{i} < \infty$ .

Exercise 8 (hard, symbolic).

For the pure birth chain of Exercise 5 with $π_{n, n + 1} = 1$ , show that the chain explodes from $0$ with probability one iff $\sum_{n} 1/ β_{n} < \infty$ , and is non-explosive iff $\sum_{n} 1/ β_{n} = \infty$ .

Hint

$ζ = \sum_{n} S_{n + 1}$ with $S_{n + 1} \sim Exp (β_{n})$ independent; use $E [ζ] = \sum_{n} 1/ β_{n}$ and a zero-one argument for sums of independent nonnegative variables.

Answer

The jump chain is deterministic, so $ζ = \sum_{n \geq 0} S_{n + 1}$ with $S_{n + 1} \sim Exp (β_{n})$ independent and $E [S_{n + 1}] = 1/ β_{n}$ . By Tonelli, $E [ζ] = \sum_{n} 1/ β_{n}$ . If $\sum_{n} 1/ β_{n} < \infty$ then $E [ζ] < \infty$ , so $ζ < \infty$ almost surely: the chain explodes. If $\sum_{n} 1/ β_{n} = \infty$ , consider $E [e^{- ζ}] = \prod_{n} E [e^{- S_{n + 1}}] = \prod_{n} \frac{β _{n}}{β _{n} + 1} = \prod_{n} (1 + β_{n}^{- 1})^{- 1}$ . This product is zero iff $\sum_{n} β_{n}^{- 1} = \infty$ (since $- lo g (1 + x) \sim - x$ forces $\sum lo g (1 + β_{n}^{- 1}) = \infty$ ). Hence $E [e^{- ζ}] = 0$ , forcing $e^{- ζ} = 0$ a.s., i.e. $ζ = \infty$ almost surely: the chain is non-explosive. The dichotomy is exactly the convergence of $\sum_{n} 1/ β_{n}$ , the classical criterion separating, e.g., $β_{n} = n$ (non-explosive, $\sum 1/ n = \infty$ ) from $β_{n} = n^{2}$ (explosive, $\sum 1/ n^{2} < \infty$ ).

Advanced results Master

Beyond the pathwise construction, the theory organizes around the equivalence of the data, the embedded jump chain as the discrete skeleton, the explosion dichotomy with Reuter's analytic criterion, and the passage from $Q$ to the transition semigroup that places the matrix as the infinitesimal generator dual to the continuous-state operator of 02.15.03.

Theorem 1 (three equivalent descriptions). Let $X$ be the minimal right-continuous process on $I$ . The following data determine one another and determine the law of $X$ : (i) the conservative stable $Q$ -matrix $Q$ ; (ii) the pair consisting of the jump matrix $Π$ and the rate vector $(q_{i})$ , via $q_{ij} = q_{i} π_{ij}$ , $q_{ii} = - q_{i}$ ; (iii) the requirement that, started at $i$ with $q_{i} > 0$ , the first holding time is $Exp (q_{i})$ independent of the first jump, whose law is $π_{i \cdot}$ , and that the process restarts afresh at each jump (strong Markov at jump times). The equivalence (i) $\Leftrightarrow$ (ii) is algebraic; (ii) $\Leftrightarrow$ (iii) is the Key theorem together with the strong Markov property of the discrete jump chain 37.05.01.

Theorem 2 (the embedded jump chain governs the qualitative theory). The jump chain $(Y_{n})$ is a discrete-time $Markov (λ, Π)$ chain, and the continuous chain's irreducibility, recurrence, and transience are read off $(Y_{n})$ : $X$ is irreducible iff $Π$ is irreducible (on the non-absorbing states), and a state $i$ is recurrent for $X$ iff it is recurrent for $(Y_{n})$ . The continuous and discrete notions of visiting a state coincide because the holding times are almost surely positive and finite (for $q_{i} > 0$ ), so the set of states visited is identical for $X$ and $Y$ . The distinction between positive and null recurrence, however, involves the holding rates: positive recurrence of $X$ requires the expected return time $\sum_{i} (visits) / q_{i}$ to be finite, blending the routing of $Π$ with the rates.

Theorem 3 (explosion dichotomy and Reuter's criterion). Let $Q$ be a stable conservative $Q$ -matrix. The minimal chain is non-explosive (honest) from every state iff the only bounded solution $z = (z_{i})_{i \in I}$ with $0 \leq z_{i} \leq 1$ to $Q z = z equivalently j \sum q_{ij} z_{j} = z_{i} for all i, i.e. (Q - I_{d}) z = 0,$ is $z \equiv 0$ . This is Reuter's criterion ^{[Reuter 1957]}. The quantity $z_{i} = E_{i} [e^{- ζ}]$ is the maximal such solution: it satisfies $Q z = z$ by a first-jump decomposition, and explosion ( $z_{i} > 0$ for some $i$ ) is equivalent to the existence of a non-zero bounded solution. Sufficient conditions follow at once: a bounded $Q$ -matrix ( $sup_{i} q_{i} < \infty$ ), or more generally any chain for which $\sum_{n} 1/ q_{Y_{n - 1}} = \infty$ almost surely, is non-explosive; the pure-birth criterion $\sum_{n} 1/ β_{n} = \infty$ is the one-dimensional instance.

Theorem 4 (from $Q$ to the transition semigroup; the generator). Define $p_{ij} (t) = P_{i} (X_{t} = j)$ for the minimal chain. Then $(P (t))_{t \geq 0}$ with $P (t) = (p_{ij} (t))$ is a sub-stochastic semigroup: $P (0) = I_{d}$ , $P (s + t) = P (s) P (t)$ (the continuous-time Chapman–Kolmogorov relation), and $\sum_{j} p_{ij} (t) \leq 1$ with equality iff the chain is non-explosive up to time $t$ . It satisfies the backward equation $P^{'} (t) = QP (t)$ and, under non-explosion and suitable regularity, the forward equation $P^{'} (t) = P (t) Q$ , with $P (t) = e^{tQ}$ when $Q$ is bounded. Thus $Q = P^{'} (0)$ is the infinitesimal generator: the matrix analogue, on a countable state space, of the second-order differential generator $L$ of a diffusion 02.15.03. The off-diagonal $q_{ij}$ is the instantaneous rate $lim_{t ↓ 0} p_{ij} (t) / t$ , and $- q_{ii} = q_{i} = lim_{t ↓ 0} (1 - p_{ii} (t)) / t$ is the instantaneous rate of leaving $i$ .

Synthesis. The foundational reason the subject coheres is that one conservative $Q$ -matrix encodes the entire law of the minimal chain, and putting these together, the jump-chain/holding-time data $(Π, (q_{i}))$ is exactly the same information presented as routing-plus-clock rather than as a single generator — this is the central insight that the when and the where decouple, with the memoryless exponential the unique clock the Markov property allows. The embedded jump chain is the discrete skeleton, so every recurrence and transience question generalises the discrete theory of 37.05.01 verbatim, while the rates re-enter only for positive recurrence and for the time-change between $Y$ and $X$ . The explosion dichotomy is dual to the analytic question of whether $(Q - I_{d}) z = 0$ admits a non-zero bounded solution: this is exactly Reuter's criterion, and the maximal solution $z_{i} = E_{i} [e^{- ζ}]$ is the bridge between the probabilistic event of explosion and the linear algebra of the generator. The passage $Q \mapsto P (t) = e^{tQ}$ shows the $Q$ -matrix is dual to the diffusion generator $L$ of 02.15.03 — both are $P^{'} (0)$ for their respective semigroups, one a row-zero-sum matrix on a countable set, the other a second-order elliptic operator on a continuum — so the $Q$ -matrix, the jump-and-hold construction, the explosion criterion, and the generator of the semigroup are four presentations of the single fact that an infinitesimal description determines a continuous-time Markov flow whenever its jumps do not pile up.

Full proof set Master

Proposition 1 (the jump matrix is stochastic). For any stable conservative $Q$ -matrix $Q$ , the associated $Π$ is a stochastic matrix.

Proof. For $i$ with $q_{i} > 0$ : $π_{ij} = q_{ij} / q_{i} \geq 0$ for $j \neq = i$ since $q_{ij} \geq 0$ , and $π_{ii} = 0$ ; the row sum is $\sum_{j \neq = i} q_{ij} / q_{i} = q_{i} / q_{i} = 1$ using $\sum_{j \neq = i} q_{ij} = q_{i}$ . For $i$ with $q_{i} = 0$ : $π_{ii} = 1$ and $π_{ij} = 0$ for $j \neq = i$ , a degenerate but valid stochastic row. Hence every row of $Π$ is a probability distribution, so $Π$ is stochastic. $□$

Proposition 2 (competing exponentials; full joint law). Let $(T_{j})_{j \in A}$ be independent with $T_{j} \sim Exp (α_{j})$ , $α := \sum_{j \in A} α_{j} < \infty$ . Let $T = min_{j} T_{j}$ and $K = ar g min_{j} T_{j}$ . Then $T \sim Exp (α)$ , $P (K = k) = α_{k} / α$ , $T$ and $K$ are independent, and the minimizer is almost surely unique.

Proof. For the tail, $P (T > t) = \prod_{j} P (T_{j} > t) = \prod_{j} e^{- α_{j} t} = e^{- α t}$ , so $T \sim Exp (α)$ . For the joint law of ${K = k} \cap {T > t}$ , condition on $T_{k}$ : $P (K = k, T > t) = \int_{t}^{\infty} α_{k} e^{- α_{k} s} j \neq = k \prod P (T_{j} > s) d s = \int_{t}^{\infty} α_{k} e^{- α s} d s = \frac{α _{k}}{α} e^{- α t} .$ Setting $t = 0$ gives $P (K = k) = α_{k} / α$ ; combined with $P (T > t) = e^{- α t}$ the joint factors as $P (K = k) P (T > t)$ , proving independence. Two continuous independent variables coincide with probability zero, so the minimizer is a.s. unique. $□$

Proposition 3 (memorylessness characterizes the exponential). A nonnegative random variable $S$ with $P (S > 0) = 1$ satisfies $P (S > s + t ∣ S > s) = P (S > t)$ for all $s, t \geq 0$ iff $S \sim Exp (q)$ for some $q \in [0, \infty)$ (with $q = 0$ meaning $S = \infty$ a.s.).

Proof. If $S \sim Exp (q)$ then $G (t) := P (S > t) = e^{- q t}$ gives $G (s + t) / G (s) = e^{- q t} = G (t)$ . Conversely the hypothesis is $G (s + t) = G (s) G (t)$ , the multiplicative Cauchy equation for the right-continuous non-increasing $G$ with $G (0) = 1$ . Right-continuous solutions of $G (s + t) = G (s) G (t)$ on $[0, \infty)$ with $0 \leq G \leq 1$ are $G (t) = e^{- q t}$ for some $q \in [0, \infty]$ : writing $g = - lo g G$ gives Cauchy's additive equation $g (s + t) = g (s) + g (t)$ , whose monotone solutions are linear $g (t) = q t$ . Hence $G (t) = e^{- q t}$ , i.e. $S \sim Exp (q)$ . $□$

Proposition 4 ( $Q z = z$ for the explosion functional). Let $z_{i} = E_{i} [e^{- ζ}]$ for the minimal chain, $0 \leq z_{i} \leq 1$ . Then $(Q - I_{d}) z = 0$ on the non-absorbing states, and $z$ is the maximal bounded solution in $[0, 1]$ .

Proof. Condition on the first holding time $S_{1} \sim Exp (q_{i})$ and the first jump $Y_{1} \sim π_{i \cdot}$ , independent by the Key theorem. After the first jump the residual explosion time is $ζ^{'} = ζ - S_{1}$ with law $E_{Y_{1}} [e^{- ζ^{'}}]$ by the strong Markov property at the jump time 37.05.01. Hence, for $q_{i} > 0$ , $z_{i} = E_{i} [e^{- S_{1}}] E_{i} [e^{- ζ^{'}}] = \frac{q _{i}}{q _{i} + 1} j \sum π_{ij} z_{j},$ using $E [e^{- S_{1}}] = q_{i} / (q_{i} + 1)$ for $S_{1} \sim Exp (q_{i})$ . Multiplying by $(q_{i} + 1)$ and rearranging with $q_{ij} = q_{i} π_{ij}$ , $q_{ii} = - q_{i}$ : $(q_{i} + 1) z_{i} = q_{i} j \sum π_{ij} z_{j} = j \neq = i \sum q_{ij} z_{j} ⟹ j \sum q_{ij} z_{j} = j \neq = i \sum q_{ij} z_{j} - q_{i} z_{i} = (q_{i} + 1) z_{i} - q_{i} z_{i} - z_{i} \cdot 0,$ which simplifies to $\sum_{j} q_{ij} z_{j} = z_{i}$ , i.e. $(Q - I_{d}) z = 0$ . Maximality: any $w \in [0, 1]^{I}$ solving the same equation satisfies $w_{i} = E_{i} [e^{- J_{n}} w_{Y_{n}}]$ for every $n$ by iterating the first-jump identity, and $e^{- J_{n}} w_{Y_{n}} \to e^{- ζ} \cdot (bounded)$ with $w \leq 1$ , giving $w_{i} \leq E_{i} [e^{- ζ}] = z_{i}$ by dominated convergence. $□$

Proposition 5 (Reuter's criterion). The minimal chain is non-explosive from every state iff $z \equiv 0$ is the only solution of $(Q - I_{d}) z = 0$ in $[0, 1]^{I}$ .

Proof. By Proposition 4, $z_{i} = E_{i} [e^{- ζ}]$ is the maximal bounded $[0, 1]$ -solution. Non-explosion from every state means $P_{i} (ζ = \infty) = 1$ for all $i$ , equivalently $e^{- ζ} = 0$ a.s., equivalently $z_{i} = 0$ for all $i$ . Since $z$ is maximal, $z \equiv 0$ forces every bounded $[0, 1]$ -solution to vanish; conversely if some $z_{i} > 0$ then $z$ itself is a non-zero solution and $P_{i} (ζ < \infty) > 0$ , i.e. explosion. Hence non-explosion $\Leftrightarrow$ the only solution is $z \equiv 0$ . $□$

Proposition 6 (bounded $Q$ gives $P (t) = e^{tQ}$ , a stochastic semigroup). If $sup_{i} q_{i} =: \overset{q}{ˉ} < \infty$ , the series $e^{tQ} = \sum_{n \geq 0} t^{n} Q^{n} / n!$ converges in operator norm on $ℓ^{\infty} (I)$ , defines a stochastic semigroup $P (t)$ with $P (t) 1 = 1$ , and equals the transition matrix of the minimal (non-explosive) chain.

Proof. On $ℓ^{\infty} (I)$ , $∥ Q ∥_{\infty} = sup_{i} \sum_{j} ∣ q_{ij} ∣ = sup_{i} 2 q_{i} = 2 \overset{q}{ˉ} < \infty$ , so $\sum_{n} t^{n} ∥ Q ∥^{n} / n! = e^{t ∥ Q ∥} < \infty$ and the series converges absolutely in operator norm; $P (t) := e^{tQ}$ then satisfies $P (0) = I_{d}$ , $P^{'} (t) = Q e^{tQ} = e^{tQ} Q$ , and $P (s + t) = P (s) P (t)$ by the functional equation of the matrix exponential. Conservativity $Q 1 = 0$ gives $P (t) 1 = e^{tQ} 1 = \sum_{n} t^{n} Q^{n} 1 / n! = 1$ since $Q^{n} 1 = 0$ for $n \geq 1$ ; nonnegativity of $P (t)$ follows by writing $P (t) = e^{- \overset{q}{ˉ}^{'} t} \sum_{n} (t)^{n} (Q + \overset{q}{ˉ}^{'} I_{d})^{n} / n!$ with $\overset{q}{ˉ}^{'} \geq \overset{q}{ˉ}$ chosen so $Q + \overset{q}{ˉ}^{'} I_{d} \geq 0$ entrywise, a convergent series of nonnegative matrices. Boundedness gives non-explosion (Exercise 7), and the forward/backward equations identify $e^{tQ}$ with the minimal chain's transition matrix. $□$

Connections Master

The discrete-time chain 37.05.01 supplies the embedded jump chain $(Y_{n})$ : it is a $Markov (λ, Π)$ chain in the exact sense of that unit, and its stochastic-matrix algebra, simple and strong Markov properties, and recurrence/transience dichotomy transfer verbatim to the qualitative theory of the continuous chain; the continuous-time content added here is only the exponential clock and the explosion phenomenon that the discrete skeleton cannot see.
The probability-space and extension foundations 37.01.01 underwrite the construction of the pair $((Y_{n}), (E_{n}))$ on one probability space: the jump chain is built from a consistent family of finite-dimensional laws and the holding-time exponentials are an independent i.i.d. sequence, the joint law assembled by the Kolmogorov/Ionescu–Tulcea machinery, and the explosion time $ζ = \sum_{n} S_{n}$ is a measurable functional of that data on path space.
The continuous-state diffusion generator 02.15.03 is the parallel theory on a continuum: the $Q$ -matrix is to the countable-state semigroup $P (t) = e^{tQ}$ what the second-order elliptic operator $L$ is to the diffusion semigroup $P_{t} = e^{t L}$ ; both are $P^{'} (0)$ , both run forward (Kolmogorov forward / Fokker–Planck) on measures and backward on observables, and the contrast is jumps on a discrete set versus continuous sample paths on $R^{n}$ , with explosion here mirroring the explosion of solutions to the SDE there.

Historical & philosophical context Master

The analytic theory of continuous-time Markov processes was founded by Andrei N. Kolmogorov in his 1931 Mathematische Annalen memoir ^{[Kolmogorov 1931]}, which introduced the transition function $p_{ij} (t)$ and derived the forward and backward differential equations governing it. Kolmogorov worked from the semigroup relation $p_{ik} (s + t) = \sum_{j} p_{ij} (s) p_{j k} (t)$ — the continuous-time Chapman–Kolmogorov equation — and obtained $Q = P^{'} (0)$ as the matrix of instantaneous rates, though the pathwise jump-and-hold construction was not yet his concern.

William Feller, in his 1940 Transactions of the American Mathematical Society paper on purely discontinuous Markov processes ^{[Feller 1940]}, analyzed the integro-differential equations of jump processes on countable state spaces and confronted the possibility that the backward equation does not determine a unique transition function — the analytic shadow of explosion and of boundary behaviour. The probabilistic resolution, separating the routing (jump matrix) from the timing (exponential holding times) and constructing the minimal process directly, is the modern synthesis presented here.

Gerd E. H. Reuter settled the existence and uniqueness question for denumerable chains in his 1957 Acta Mathematica paper ^{[Reuter 1957]}, characterizing non-explosion (honesty) of the minimal process through the vanishing of every bounded $[0, 1]$ -solution of $(Q - I_{d}) z = 0$ , the criterion stated above. The contraction-semigroup framework he used connects the matrix $Q$ to the Hille–Yosida generation theory for the transition semigroup on $ℓ^{1}$ , placing continuous-time chains within the general theory of Markov semigroups whose continuous-state instance is the diffusion generator of 02.15.03.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{Reuter1957,
  author  = {Reuter, Gerd E. H.},
  title   = {Denumerable {M}arkov processes and the associated contraction semigroups on $l$},
  journal = {Acta Mathematica},
  volume  = {97},
  year    = {1957},
  pages   = {1--46}
}

@article{Kolmogorov1931,
  author  = {Kolmogorov, Andrei N.},
  title   = {\"Uber die analytischen {M}ethoden in der {W}ahrscheinlichkeitsrechnung},
  journal = {Mathematische Annalen},
  volume  = {104},
  year    = {1931},
  pages   = {415--458}
}

@article{Feller1940,
  author  = {Feller, William},
  title   = {On the integro-differential equations of purely discontinuous {M}arkoff processes},
  journal = {Transactions of the American Mathematical Society},
  volume  = {48},
  year    = {1940},
  pages   = {488--515}
}

@book{Anderson1991,
  author    = {Anderson, William J.},
  title     = {Continuous-Time Markov Chains: An Applications-Oriented Approach},
  series    = {Springer Series in Statistics},
  publisher = {Springer},
  year      = {1991}
}

@book{Chung1967,
  author    = {Chung, Kai Lai},
  title     = {Markov Chains with Stationary Transition Probabilities},
  edition   = {2},
  publisher = {Springer},
  year      = {1967}
}

Prerequisites

37.05.01
37.01.01
02.15.03

Tier anchors

beginner: Norris 1997 *Markov Chains* (Cambridge) §2.1; informal picture of a particle that waits a random time on each state, then jumps, where only the current state sets the clock and the jump odds
intermediate: Norris 1997 *Markov Chains* (Cambridge) §2.1-2.6; Anderson 1991 *Continuous-Time Markov Chains* Ch. 2
master: Norris 1997 *Markov Chains* (Cambridge) §2.1-2.8 (jump-chain/holding-time construction, explosion, the backward equation); Chung 1967 *Markov Chains with Stationary Transition Probabilities* 2e Ch. II; Anderson 1991 *Continuous-Time Markov Chains: An Applications-Oriented Approach* (Springer) Ch. 2

References

Norris — Markov Chains · Cambridge University Press 1997, §2.1-2.8 (Q-matrices, jump chain and holding times, explosion, Reuter's criterion)
Reuter — Denumerable Markov processes and the associated contraction semigroups on l · Acta Mathematica 97 (1957), 1-46
Kolmogorov — Uber die analytischen Methoden in der Wahrscheinlichkeitsrechnung · Mathematische Annalen 104 (1931), 415-458
Feller — On the integro-differential equations of purely discontinuous Markoff processes · Transactions of the American Mathematical Society 48 (1940), 488-515
Anderson — Continuous-Time Markov Chains: An Applications-Oriented Approach · Springer 1991, Ch. 2 (the q-matrix, minimal process, explosion)

Estimated time

beginner: 18m
intermediate: 55m
master: 90m