37.05.10 · probability / 05-markov-chains

Recurrence, Invariant Distributions, and Convergence for Continuous-Time Chains

shipped3 tiersLean: none

Anchor (Master): Norris 1997 *Markov Chains* (Cambridge) §3.5-3.8; Asmussen 2003 *Applied Probability and Queues* 2e Ch. II §4-5; Liggett 2010 *Continuous Time Markov Processes* Ch. 2-3; Chung 1967 *Markov Chains with Stationary Transition Probabilities* 2e Ch. II (recurrence and the invariant measure)

Intuition Beginner

A continuous-time chain wanders among its states, holding each one for a random stretch of time before jumping to the next. Run it long enough and a striking regularity appears: the fraction of total elapsed time it has spent in each state stops drifting and settles to a fixed split. A small repair shop that cycles between idle, busy, and broken-down spends, over a year, some steady fraction of its hours in each condition, and that fraction does not depend on which condition it happened to start in. This unit is about that long-run split — when it exists, what fixes it, and how to compute it.

Two ideas from earlier units combine to pin the split down. The first is the jump chain: ignore the clock and just record the sequence of states visited. The second is the holding time: how long each visit lasts on average. The long-run time-fraction in a state is built from both — how often the jump chain visits the state, multiplied by how long it stays each time. A state visited rarely but held for a long while, and a state visited often but left quickly, can end up with the same share of the clock.

There is a second, more local way to find the same split, and it is the one practitioners reach for. In the long run the chain must enter and leave each state at equal rates, otherwise probability would pile up or drain away. Writing "rate of flow in equals rate of flow out" for every state gives a system of balance equations whose solution is exactly the long-run split. For many chains a stronger and simpler balance holds: between every pair of states the back-and-forth flow matches pair by pair, a condition called detailed balance, and when it holds the split can be read off almost by inspection.

Once the split is known, two convergence facts follow. The probability of finding the chain in a given state at a far-off time approaches that state's long-run share, with no parity worry that troubled the discrete-time version, because the random holding times smear out any rigid rhythm. And the time-average of any quantity along a single long run approaches the same share-weighted average — one path, watched long enough, samples the whole split.

The takeaway: a continuous-time chain has a long-run time-split among its states; you find it either by weighting jump-chain visits by holding times or by balancing the flow in and out of each state, and both the snapshot probabilities and the time-averages along one path converge to it.

Visual Beginner

Picture a single state of the chain as a tank with water flowing in from other states and out to other states; equilibrium is the level where inflow matches outflow.

The tanks are states; the pipes carry probability flow at the chain's rates. The long-run fill levels are the invariant split: they sit where every tank's inflow rate balances its outflow rate. The inset shows the special, easier situation of detailed balance, where each pipe-pair balances by itself. The timeline at the bottom is one run of the chain, blocks colored by state and as wide as the holding time; the long-run fraction of each color matches the fill levels.

Worked example Beginner

Take a machine that is either working or broken. While working it breaks down at rate $a = 1$ (per day). While broken it gets repaired at rate $b = 4$ (per day). We find the long-run fraction of time it is working.

Step 1. Read off the rates. From "working" the only move is to "broken," at rate $1$ . From "broken" the only move is to "working," at rate $4$ . So the chain leaves "working" at rate $1$ and leaves "broken" at rate $4$ .

Step 2. Balance the flow for the "working" tank. Let $w$ be the long-run fraction of time working and $1 - w$ the fraction broken. Flow out of "working" is $w \times 1$ . Flow into "working" comes from "broken" at rate $4$ , so it is $(1 - w) \times 4$ . Setting inflow equal to outflow: $w \times 1 = (1 - w) \times 4$ .

Step 3. Solve. The equation $w = 4 (1 - w) = 4 - 4 w$ gives $5 w = 4$ , so $w = 4/5 = 0.8$ . The machine works $80%$ of the time and is broken $20%$ of the time.

Step 4. Check with holding times. The average holding time in "working" is $1/ a = 1$ day; in "broken" it is $1/ b = 1/4$ day. The jump chain just alternates working, broken, working, broken, so it visits each equally often. Weighting equal visits by holding time gives working : broken $= 1 : 1/4 = 4 : 1$ , so the working fraction is $4/ (4 + 1) = 4/5$ . Same answer by a different route.

What this tells us: the long-run split came out two ways. Balancing flow in and out of a state gave $w = b / (a + b) = 4/5$ directly. Weighting how often the jump chain visits a state by how long it stays gave the same $4/5$ . The first method scales to many states as a system of balance equations; the second explains why those equations are right.

Check your understanding Beginner

Exercise (easy, multiple choice).

The long-run fraction of time a continuous-time chain spends in a state is determined by which two ingredients?

A. Only how often the jump chain visits the state B. Only how long each visit to the state lasts C. How often the jump chain visits the state, multiplied by how long each visit lasts D. The order in which the states were first visited

Hint

A state can have a large time-share by being visited often, or by being held for a long time, or both.

Answer

C. Visit frequency times holding time. The clock-share of a state is how often the chain lands there (a jump-chain fact) multiplied by how long it stays each time (a holding-time fact). Feedback-correct: rare-but-long and frequent-but-brief states can tie. Feedback-wrong: A and B each keep only half the story; D does not affect the long-run split at all.

Formal definition Intermediate+

Throughout, $I$ is a countable state space, $Q = (q_{ij})$ a stable conservative $Q$ -matrix with jump matrix $Π = (π_{ij})$ and exit rates $q_{i} = - q_{ii}$ 37.05.08, $(X_{t})_{t \geq 0}$ the associated minimal right-continuous chain with explosion time $ζ$ , and $(P (t))_{t \geq 0}$ its transition semigroup, $P_{ij} (t) = P_{i} (X_{t} = j)$ , satisfying $P (0) = I_{d}$ , $P (s + t) = P (s) P (t)$ , and the backward/forward equations of 37.05.09. The embedded jump chain $(Y_{n})_{n \geq 0}$ is the discrete-time chain with matrix $Π$ ; its recurrence, invariant measures, and positive/null classification are as in 37.05.02 and 37.05.05. We assume $Q$ irreducible (equivalently $Π$ irreducible) and, unless stated, non-explosive, so $ζ = \infty$ a.s. and $P (t)$ is honest.

Definition (recurrence and transience). A state $i$ is recurrent for the continuous-time chain if $P_{i} ({t : X_{t} = i} is unbounded) = 1$ , and transient if this probability is $0$ . For a non-explosive irreducible chain, $i$ is recurrent iff $i$ is recurrent for the jump chain $Π$ ; recurrence and transience are class properties shared by all states. The return time to $i$ is $T_{i} := in f {t \geq J_{1} : X_{t} = i}$ , where $J_{1}$ is the first jump time. A recurrent state is positive recurrent if $E_{i} [T_{i}] < \infty$ and null recurrent if $E_{i} [T_{i}] = \infty$ .

Definition (invariant measure and invariant distribution). A measure $μ = (μ_{i})_{i \in I}$ , $μ_{i} \geq 0$ , is invariant for $Q$ if $μ Q = 0, i.e. i \in I \sum μ_{i} q_{ij} = 0 for every j \in I,$ equivalently $- μ_{j} q_{j} + \sum_{i \neq = j} μ_{i} q_{ij} = 0$ (outflow rate $=$ inflow rate at $j$ ). An invariant distribution $π$ is an invariant measure that is a probability vector, $\sum_{i} π_{i} = 1$ . For a non-explosive chain, $π Q = 0$ with $\sum_{i} π_{i} = 1$ holds iff $π P (t) = π$ for all $t \geq 0$ (time-stationarity of the semigroup).

Definition (the jump-chain bridge). If $μ$ is invariant for $Q$ , then $ν_{i} := μ_{i} q_{i}$ is invariant for the jump chain, $ν Π = ν$ ; conversely if $ν Π = ν$ then $μ_{i} := ν_{i} / q_{i}$ satisfies $μ Q = 0$ . Thus continuous-time invariance weights the jump-chain invariant measure by the mean holding time $1/ q_{i}$ : $π_{i} = \frac{ν _{i} / q _{i}}{\sum _{k} ν _{k} / q _{k}}, ν = ν Π.$

Definition (detailed balance / reversibility). The chain is in detailed balance with respect to a measure $μ$ if $μ_{i} q_{ij} = μ_{j} q_{j i} for all i, j \in I .$ A chain admitting a detailed-balance probability distribution $π$ is reversible: the stationary chain $(X_{t})_{0 \leq t \leq T}$ has the same law as its time-reversal $(X_{T - t})_{0 \leq t \leq T}$ .

Counterexamples to common slips Intermediate+

The continuous-time invariant is not the jump-chain invariant. $π Q = 0$ and $ν Π = ν$ are different equations; they agree only when all exit rates $q_{i}$ are equal. Forgetting the $1/ q_{i}$ holding-time weight is the most common error: a state the jump chain visits often but leaves quickly carries less clock-time than its visit count suggests.
Positive recurrence of the chain is not positive recurrence of the jump chain. The continuous-time chain is positive recurrent iff $Q$ admits an invariant distribution, which can hold even when the jump chain is null recurrent (slow-but-long visits), and can fail when the jump chain is positive recurrent (fast visits with $\sum_{k} ν_{k} / q_{k} = \infty$ ). The holding times decouple the two notions.
No aperiodicity is required for convergence. In discrete time, periodicity blocks $p_{ij}^{(n)} \to π_{j}$ 37.05.06. In continuous time the exponential holding times have no period, so $P_{ij} (t) \to π_{j}$ holds for every irreducible non-explosive positive-recurrent chain with no parity hypothesis.
Detailed balance is sufficient but not necessary for invariance. Summing $μ_{i} q_{ij} = μ_{j} q_{j i}$ over $i$ gives $\sum_{i} μ_{i} q_{ij} = μ_{j} \sum_{i} q_{j i}$ ; using $\sum_{i} q_{j i} = 0$ (conservativity, with the $i = j$ term) yields $(μ Q)_{j} = 0$ . The converse fails: a directed cycle $1 \to 2 \to 3 \to 1$ at equal rates has a uniform invariant distribution but no detailed-balance measure, since reverse rates vanish.

Key theorem with proof Intermediate+

Theorem (invariant distribution from the jump chain; convergence to equilibrium). Let $Q$ be irreducible and non-explosive on $I$ . Then $Q$ has an invariant distribution $π$ iff the chain is positive recurrent, in which case $π$ is unique and given by $π_{i} = \frac{1}{q _{i} E _{i} [ T _{i} ]} > 0, i \in I, (*)$ equivalently $π_{i} = (ν_{i} / q_{i}) / \sum_{k} (ν_{k} / q_{k})$ where $ν$ is the (essentially unique) invariant measure of the jump chain $Π$ . Moreover, for every $i, j$ and every initial distribution $λ$ , $P_{ij} (t) \to π_{j} and ∥ λ P (t) - π ∥_{TV} \to 0 (t \to \infty),$ with no aperiodicity hypothesis. ^{[Norris 1997 §3.5-3.8]}

Proof. Existence and the formula. Suppose the chain is positive recurrent. The jump chain $Π$ is recurrent (recurrence is shared, since the chain visits a state unboundedly often in time iff $Y_{n}$ returns infinitely often), so by 37.05.05 it has an invariant measure $ν$ , unique up to scale, with $ν_{i} > 0$ . Set $μ_{i} = ν_{i} / q_{i}$ . Then for each $j$ , $(μ Q)_{j} = i \sum μ_{i} q_{ij} = - μ_{j} q_{j} + i \neq = j \sum \frac{ν _{i}}{q _{i}} q_{i} π_{ij} = - ν_{j} + i \neq = j \sum ν_{i} π_{ij} = - ν_{j} + (ν Π)_{j} = 0,$ using $q_{ij} = q_{i} π_{ij}$ for $i \neq = j$ , $μ_{j} q_{j} = ν_{j}$ , and $π_{j j} = 0$ . So $μ Q = 0$ . The total mass is $\sum_{i} μ_{i} = \sum_{i} ν_{i} / q_{i}$ , which is finite iff the chain is positive recurrent: by the renewal identity (Proposition 2 below) $E_{i} [T_{i}] = (\sum_{k} ν_{k} / q_{k}) / ν_{i}$ when $ν$ is normalized so that $ν_{i}$ counts mean jump-chain visits to $k$ per excursion from $i$ , whence $\sum_{k} μ_{k} = ν_{i} E_{i} [T_{i}]$ and $π_{i} = μ_{i} / \sum_{k} μ_{k} = (ν_{i} / q_{i}) / (ν_{i} E_{i} [T_{i}]) = 1/ (q_{i} E_{i} [T_{i}])$ , which is ( $*$ ). Normalizing $μ$ to total mass $1$ gives the invariant distribution $π$ . Uniqueness follows from uniqueness of $ν$ up to scale.

Conversely, if $Q$ has an invariant distribution $π$ , then $ν_{i} = π_{i} q_{i}$ is an invariant measure for $Π$ with finite weighted mass $\sum_{i} ν_{i} / q_{i} = \sum_{i} π_{i} = 1 < \infty$ , forcing positive recurrence.

Convergence to equilibrium. Fix a small $h > 0$ and consider the $h$ -skeleton, the discrete-time chain with one-step matrix $P (h)$ . Because $P (h) = e^{h Q}$ has strictly positive diagonal (a state can stay put over $[0, h]$ with probability $\geq e^{- q_{i} h} > 0$ ) and is irreducible (irreducibility of $Q$ gives $P_{ij} (h) > 0$ for all $i, j$ when the chain is irreducible and non-explosive, as a positive holding-then-jumping path has positive density), the skeleton is irreducible and aperiodic. Its invariant distribution is $π$ , since $π P (h) = π$ from $π Q = 0$ . By the discrete-time convergence theorem 37.05.06, $P_{ij} (nh) = (P (h)^{n})_{ij} \to π_{j}$ as $n \to \infty$ . To pass from the skeleton to continuous $t$ , note $t \mapsto P_{ij} (t)$ is uniformly continuous (it is Lipschitz with constant $\leq 2 q_{j}$ on bounded-rate skeleton steps, and in general uniformly continuous by the semigroup contraction $∥ μ P (s) - ν P (s) ∥_{TV} \leq ∥ μ - ν ∥_{TV}$ inherited from each row being a distribution), so a sequence along the lattice $nh$ that converges forces the continuous limit; varying $h$ over a rationally independent pair removes any lattice gap. Hence $P_{ij} (t) \to π_{j}$ , and $∥ λ P (t) - π ∥_{TV} \to 0$ by dominated convergence over the countable sum. The exponential holding times supply the aperiodicity for free: $P (h)$ has positive diagonal for every $h > 0$ , so no periodicity obstruction can arise. $□$

Bridge. This theorem builds toward the entire equilibrium theory of continuous-time Markov processes and appears again in queueing theory, where $π$ is the stationary queue-length law and ( $*$ ) is the mean-busy-cycle formula. The foundational reason the continuous-time invariant differs from the jump-chain invariant is the holding-time weight $1/ q_{i}$ : this is exactly the bridge $π_{i} = (ν_{i} / q_{i}) / \sum_{k} (ν_{k} / q_{k})$ that converts visit-frequency into clock-fraction, and it generalises the discrete reciprocal-return-time formula $π_{i} = 1/ E_{i} [T_{i}]$ of 37.05.05 by inserting the exit rate. The convergence half is dual to the discrete coupling theorem 37.05.06 but cleaner, because the random holding times erase periodicity; putting these together, the snapshot law $P_{ij} (t)$ and the invariant $π$ are linked by the same positive-recurrence input that the next result reads pathwise, and the central insight is that one continuous-time chain carries two stationary objects — the time-stationary $π$ with $π Q = 0$ and the jump-stationary $ν$ with $ν Π = ν$ — bridged by the mean holding time.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

A birth-death chain on ${0, 1, 2, \dots}$ has birth rates $q_{n, n + 1} = λ$ and death rates $q_{n, n - 1} = μ$ (with $λ < μ$ ). Find the invariant distribution via detailed balance and identify it.

Hint

Detailed balance reads $π_{n} λ = π_{n + 1} μ$ ; iterate from $π_{0}$ and normalize a geometric series.

Answer

Detailed balance between $n$ and $n + 1$ is $π_{n} q_{n, n + 1} = π_{n + 1} q_{n + 1, n}$ , i.e. $π_{n} λ = π_{n + 1} μ$ , so $π_{n + 1} = (λ / μ) π_{n}$ and $π_{n} = (λ / μ)^{n} π_{0}$ . Writing $ρ = λ / μ < 1$ , normalization $\sum_{n} ρ^{n} π_{0} = π_{0} / (1 - ρ) = 1$ gives $π_{0} = 1 - ρ$ , so $π_{n} = (1 - ρ) ρ^{n}$ , the geometric distribution — the stationary queue length of an M/M/1 queue. Since detailed balance holds, the chain is reversible. For $λ \geq μ$ the series diverges and no invariant distribution exists (the queue is transient or null recurrent).

Exercise 6 (medium, multiple choice).

Why does convergence $P_{ij} (t) \to π_{j}$ for continuous-time chains need no aperiodicity hypothesis, unlike the discrete-time case?

A. Continuous-time chains are always reversible B. The exponential holding times have no period, so the $h$ -skeleton $P (h)$ has positive diagonal and is aperiodic for every $h$ C. The generator $Q$ is always bounded D. Continuous-time chains never explode

Hint

Consider the diagonal entries $P_{ii} (h) \geq e^{- q_{i} h} > 0$ .

Answer

B. Each $h$ -skeleton matrix $P (h)$ has $P_{ii} (h) \geq e^{- q_{i} h} > 0$ , a positive self-loop, so it is aperiodic; the discrete convergence theorem then applies to every skeleton. The exponential holding times smear out any rigid rhythm. A is false (not all continuous chains are reversible), C and D are unrelated to the periodicity question.

Exercise 7 (hard, symbolic).

State and prove the continuous-time ergodic theorem for an irreducible positive-recurrent non-explosive chain: for bounded $f : I \to R$ , $\frac{1}{t} \int_{0}^{t} f (X_{s}) d s \to i \sum π_{i} f (i) a.s. as t \to \infty.$

Hint

Apply renewal-reward to the i.i.d. excursions of $X$ between successive visits to a fixed state $i$ ; the reward over a cycle is $\int f (X_{s}) d s$ across that excursion, and the cycle length has mean $E_{i} [T_{i}]$ .

Answer

Fix a reference state $i$ and let $0 = R_{0} < R_{1} < R_{2} < \dots$ be the successive return times to $i$ , so the excursions $(X_{s})_{R_{k - 1} \leq s < R_{k}}$ are i.i.d. by the strong Markov property at the return times, with cycle length $L_{k} = R_{k} - R_{k - 1}$ of mean $E_{i} [T_{i}] = 1/ (q_{i} π_{i})$ from ( $*$ ). The reward over cycle $k$ is $V_{k} = \int_{R_{k - 1}}^{R_{k}} f (X_{s}) d s$ ; these are i.i.d. with mean $E_{i} [V_{1}] = E_{i} [\int_{0}^{T_{i}} f (X_{s}) d s] = \sum_{j} f (j) E_{i} [time in j before T_{i}] = \sum_{j} f (j) π_{j} E_{i} [T_{i}]$ , the last step because the expected time spent in $j$ per excursion from $i$ is $π_{j} E_{i} [T_{i}]$ (the invariant law is exactly the long-run occupation fraction). By the strong law of large numbers, $\frac{1}{n} \sum_{k = 1}^{n} V_{k} \to E_{i} [V_{1}]$ and $\frac{1}{n} \sum_{k = 1}^{n} L_{k} \to E_{i} [T_{i}]$ a.s. Let $N (t) = max {n : R_{n} \leq t}$ , the number of completed cycles by time $t$ ; positive recurrence gives $N (t) \to \infty$ a.s. The renewal-reward ratio then gives $\frac{1}{t} \int_{0}^{t} f (X_{s}) d s = \frac{\sum _{k \leq N (t)} V _{k} + o ( R _{N (t)} )}{t} \to \frac{E _{i} [ V _{1} ]}{E _{i} [ T _{i} ]} = j \sum π_{j} f (j),$ the boundary partial-cycle term vanishing in the ratio because $R_{N (t)} / t \to 1$ a.s. and $f$ is bounded. This is the pathwise twin of the distributional limit $P_{ij} (t) \to π_{j}$ .

Exercise 8 (hard, symbolic).

Give an irreducible chain that is positive recurrent in continuous time but whose jump chain is null recurrent, exhibiting that the holding times decouple the two notions. (Construct the rates explicitly.)

Hint

Take a jump chain that is null recurrent (e.g. simple symmetric random walk on $Z$ is null recurrent but on $Z$ is not — use instead a null-recurrent jump chain on $N$ ) and choose exit rates $q_{i}$ so that $\sum_{i} ν_{i} / q_{i} < \infty$ even though $\sum_{i} ν_{i} = \infty$ .

Answer

Let the jump chain $Π$ be a null-recurrent irreducible chain on $I = {0, 1, 2, \dots}$ with invariant measure $ν_{i}$ satisfying $ν_{i} > 0$ and $\sum_{i} ν_{i} = \infty$ (null recurrence of $Π$ means its invariant measure has infinite total mass). For instance a reflecting random walk tuned so that $ν_{i} \sim 1$ for all $i$ , giving $\sum_{i} ν_{i} = \infty$ . Now choose exit rates $q_{i} = 2^{i}$ . The continuous-time invariant measure is $μ_{i} = ν_{i} / q_{i} \sim 2^{- i}$ , with $i \sum μ_{i} = i \sum ν_{i} / q_{i} \sim i \sum 2^{- i} = 2 < \infty,$ so $μ$ normalizes to an invariant distribution $π$ and the continuous-time chain is positive recurrent, while $Π$ remains null recurrent. The fast-growing exit rates make far-out states held for vanishingly short times, so they contribute finite total clock-time despite being visited with infinite aggregate frequency. (One checks non-explosion separately; bounding the chain to keep $\sum 1/ q_{i}$ along any path infinite, e.g. by a confining drift in $Π$ , secures it.) The construction shows positive recurrence of $Q$ is governed by $\sum_{i} ν_{i} / q_{i}$ , a holding-time-weighted sum that the jump-chain classification alone cannot see.

Advanced results Master

The long-run theory rests on four facts: recurrence is inherited from the jump chain but positive recurrence is a holding-time-weighted refinement; the invariant distribution solves $π Q = 0$ and is the mean-holding-time reweighting of the jump-chain invariant measure; convergence to equilibrium holds with no periodicity hypothesis because exponential holding times carry no phase; and detailed balance is the reversible special case in which the invariant measure is read off pairwise.

Theorem 1 (recurrence dichotomy and the invariant measure). Let $Q$ be irreducible and non-explosive. The chain is recurrent iff its jump chain $Π$ is recurrent, and then $Q$ has an invariant measure $μ$ , unique up to scalar, with $μ_{i} = ν_{i} / q_{i} > 0$ where $ν Π = ν$ . The chain is positive recurrent iff $\sum_{i} μ_{i} < \infty$ , iff an invariant distribution exists, iff $E_{i} [T_{i}] < \infty$ for one (equivalently every) $i$ ; then $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ . Positive and null recurrence are class properties, but the continuous-time class can differ from the jump-chain class: $Π$ positive recurrent with $\sum_{i} ν_{i} / q_{i} = \infty$ gives a null-recurrent $Q$ , and $Π$ null recurrent with $\sum_{i} ν_{i} / q_{i} < \infty$ gives a positive-recurrent $Q$ .

Theorem 2 (the two stationary measures and Asmussen's bridge). An irreducible recurrent $Q$ carries two distinct stationary objects: the time-stationary measure $μ$ with $μ Q = 0$ , governing $μ P (t) = μ$ and the long-run clock-occupation $\frac{1}{t} \int_{0}^{t} 1_{X_{s} = i} d s \to μ_{i} / \sum_{k} μ_{k}$ ; and the jump-stationary measure $ν$ with $ν Π = ν$ , governing the long-run jump-count frequency $\frac{1}{n} # {m < n : Y_{m} = i} \to ν_{i} / \sum_{k} ν_{k}$ . They are related by $ν_{i} = μ_{i} q_{i}$ , the rate-conversion identity ^{[Asmussen 2003]}: visit-frequency times holding-time is clock-fraction. The PASTA principle and the rate-conservation law of queueing theory are corollaries — a Poisson arrival sees the time-stationary law $μ$ , not the embedded jump law $ν$ .

Theorem 3 (convergence with no aperiodicity; spectral form on finite $I$ ). For irreducible non-explosive positive-recurrent $Q$ , $P_{ij} (t) \to π_{j}$ for all $i, j$ , and $∥ λ P (t) - π ∥_{TV} \to 0$ for every $λ$ , with no parity hypothesis. On a finite state space, $P (t) = e^{tQ} = \sum_{r} e^{μ_{r} t} v_{r} u_{r}^{⊤}$ 37.05.09 with $μ_{0} = 0$ supplying the rank-one stationary projection $1 π^{⊤}$ and the remaining eigenvalues having strictly negative real part for an irreducible $Q$ , so convergence is exponential with rate the spectral gap $min_{r \geq 1} ∣ Re μ_{r} ∣$ . There is no imaginary-axis obstruction analogous to the discrete unit circle's roots of unity: irreducibility alone forces $0$ to be a simple eigenvalue and all others into the open left half-plane.

Theorem 4 (detailed balance, reversibility, and the cycle condition). $Q$ admits a detailed-balance measure $μ$ ( $μ_{i} q_{ij} = μ_{j} q_{j i}$ ) iff Kolmogorov's cycle condition holds: for every finite cycle $i_{0}, i_{1}, \dots, i_{n} = i_{0}$ , $k = 0 \prod n - 1 q_{i_{k} i_{k + 1}} = k = 0 \prod n - 1 q_{i_{k + 1} i_{k}} .$ When it holds, $μ$ is invariant (Exercise 4) and the stationary chain is reversible: $(X_{t})_{0 \leq t \leq T} = d (X_{T - t})_{0 \leq t \leq T}$ . Reversibility makes $Q$ self-adjoint on $ℓ^{2} (π)$ , so its spectrum is real, the convergence rate is the spectral gap of a symmetric operator, and the powerful variational (Dirichlet-form) machinery applies. Birth-death chains are automatically reversible (every cycle is a back-and-forth, so the cycle condition is vacuous), which is why their invariant law ( $π_{n} = π_{0} \prod_{k < n} λ_{k} / μ_{k + 1}$ ) is computed by inspection.

Synthesis. The foundational reason continuous-time long-run behaviour splits cleanly is the embedding: the chain is the jump chain $Π$ run on a clock with exponential holding times, and every long-run quantity factors into a jump-chain part and a holding-time part. This is exactly why recurrence is inherited from $Π$ while positive recurrence is the holding-time-weighted refinement $\sum_{i} ν_{i} / q_{i} < \infty$ , and the bridge $ν_{i} = μ_{i} q_{i}$ generalises the discrete reciprocal-return-time formula by inserting the exit rate — visit-frequency is dual to clock-fraction through the mean holding time. Putting these together, the invariant distribution $π Q = 0$ , the convergence $P_{ij} (t) \to π_{j}$ , and the ergodic average $\frac{1}{t} \int_{0}^{t} f (X_{s}) d s \to \sum_{i} π_{i} f (i)$ are three readings of the single positive-recurrence input $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ : the first is its existence, the second its distributional pull, the third its pathwise law of large numbers via renewal-reward over excursions. The central insight is that the random clock buys two things the discrete theory cannot have for free — periodicity disappears, so convergence needs no aperiodicity, and reversibility, when Kolmogorov's cycle condition holds, makes $Q$ self-adjoint on $ℓ^{2} (π)$ , so the same invariant $π$ that the renewal argument produces also organises the spectral theory, and the bridge between the analytic semigroup $e^{tQ}$ of 37.05.09 and the pathwise excursion structure of 37.05.08 is complete.

Full proof set Master

Proposition 1 (invariance is equivalent to time-stationarity). For a non-explosive chain, a probability vector $π$ satisfies $π Q = 0$ iff $π P (t) = π$ for all $t \geq 0$ .

Proof. If $π P (t) = π$ for all $t$ , differentiate at $t = 0$ : $\frac{d}{d t}_{0} π P (t) = π P^{'} (0) = π Q = 0$ , the derivative existing by 37.05.09. Conversely, suppose $π Q = 0$ . The forward equation 37.05.09 gives $\frac{d}{d t} (π P (t)) = π P^{'} (t) = π P (t) Q$ (using $P^{'} (t) = P (t) Q$ , valid for the honest non-explosive chain). Set $g (t) = π P (t)$ , a probability vector for each $t$ ; then $g^{'} (t) = g (t) Q$ with $g (0) = π$ . The constant function $h (t) \equiv π$ also solves $h^{'} = h Q = 0 = π Q$ with $h (0) = π$ . By uniqueness of the bounded solution of the forward system with given initial data (the $ℓ^{1}$ -contraction estimate $∥ g (t) - h (t) ∥_{1} \leq \int_{0}^{t} ∥ (g - h) (s) Q ∥_{1} d s$ with Grönwall when $Q$ is bounded, and the minimal-solution uniqueness of 37.05.09 in general), $g \equiv h$ , so $π P (t) = π$ . $□$

Proposition 2 (the renewal identity for the return time). For an irreducible positive-recurrent chain with jump-chain invariant measure $ν$ normalized by $ν_{i} = 1$ (so $ν_{k} = E_{i} [jump-chain visits to k before returning to i]$ ), the mean return time is $E_{i} [T_{i}] = \sum_{k} ν_{k} / q_{k}$ , and hence $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ .

Proof. Decompose the excursion from $i$ back to $i$ by the states the jump chain visits. Over one excursion the chain visits state $k$ a mean number $ν_{k}$ of times (the regeneration formula for the jump chain's invariant measure 37.05.05), and each visit lasts an independent $Exp (q_{k})$ holding time of mean $1/ q_{k}$ , independent of the visit count by the strong Markov property 37.05.08. By Wald's identity the total expected time of the excursion is $E_{i} [T_{i}] = \sum_{k} ν_{k} \cdot \frac{1}{q _{k}} = \sum_{k} ν_{k} / q_{k}$ . The invariant distribution is $π_{k} = μ_{k} / \sum_{j} μ_{j}$ with $μ_{k} = ν_{k} / q_{k}$ , so $π_{i} = (ν_{i} / q_{i}) / \sum_{j} (ν_{j} / q_{j}) = (1/ q_{i}) / E_{i} [T_{i}]$ , giving $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ . $□$

Proposition 3 (the $h$ -skeleton is irreducible and aperiodic). If $Q$ is irreducible and non-explosive, then for every $h > 0$ the matrix $P (h)$ is irreducible and aperiodic, with invariant distribution $π$ whenever $π Q = 0$ .

Proof. Irreducibility of $Q$ gives, for each ordered pair $(i, j)$ , a path $i = k_{0} \to k_{1} \to \dots \to k_{m} = j$ of positive jump probabilities; the event of taking these jumps within $[0, h]$ with all holding times summing to less than $h$ has positive probability, so $P_{ij} (h) > 0$ . Hence $P (h)$ is irreducible. For aperiodicity, $P_{ii} (h) \geq P_{i} (J_{1} > h) = e^{- q_{i} h} > 0$ , a positive self-loop, so the period of $i$ in $P (h)$ divides $1$ and equals $1$ . Finally $π P (h) = π e^{h Q}$ when $Q$ is bounded equals $π$ by Proposition 1's series argument; in the unbounded case $π P (h) = π$ follows from $π P (t) = π$ (Proposition 1). $□$

Proposition 4 (convergence to equilibrium). For irreducible non-explosive positive-recurrent $Q$ with invariant $π$ , $P_{ij} (t) \to π_{j}$ for all $i, j$ and $∥ λ P (t) - π ∥_{TV} \to 0$ for every $λ$ .

Proof. By Proposition 3 the skeleton $P (h)$ is irreducible aperiodic with invariant $π$ , so the discrete convergence theorem 37.05.06 gives $P_{ij} (nh) \to π_{j}$ as $n \to \infty$ , for each fixed $h$ . The map $t \mapsto P_{ij} (t)$ is uniformly continuous: for $s \leq t$ , $∣ P_{ij} (t) - P_{ij} (s) ∣ = ∣ (P (s) (P (t - s) - I_{d}))_{ij} ∣ \leq \sum_{k} P_{ik} (s) ∣ P_{k j} (t - s) - δ_{k j} ∣$ , and $\sum_{k} P_{ik} (s) P (a jump in [0, t - s]) \leq 1 - e^{- s u p}$ tends to $0$ uniformly as $t - s ↓ 0$ on any set where exit rates are bounded; in general uniform continuity follows from the total-variation contraction $∥ μ P (δ) - μ ∥_{TV} \to 0$ as $δ ↓ 0$ for each row. Given $ε$ , pick $h$ with the modulus of continuity below $ε$ over $[0, h]$ and $n_{0}$ with $∣ P_{ij} (nh) - π_{j} ∣ < ε$ for $n \geq n_{0}$ ; then for $t \in [nh, (n + 1) h]$ , $∣ P_{ij} (t) - π_{j} ∣ < 2 ε$ . Hence $P_{ij} (t) \to π_{j}$ . Summing, $∥ λ P (t) - π ∥_{TV} = \frac{1}{2} \sum_{j} ∣ \sum_{i} λ_{i} P_{ij} (t) - π_{j} ∣ \to 0$ by dominated convergence (each term $\to 0$ , dominated by $π_{j} + \sum_{i} λ_{i} P_{ij} (t) \leq π_{j} + (λ P (t))_{j}$ summable to $2$ ). $□$

Proposition 5 (continuous-time ergodic theorem). For irreducible positive-recurrent non-explosive $Q$ and bounded $f : I \to R$ , $\frac{1}{t} \int_{0}^{t} f (X_{s}) d s \to \sum_{i} π_{i} f (i)$ a.s.

Proof. As in Exercise 7, the successive returns to a fixed state $i$ cut the path into i.i.d. excursions by the strong Markov property 37.05.08. The cycle length has mean $E_{i} [T_{i}] < \infty$ (positive recurrence) and the reward $V = \int_{0}^{T_{i}} f (X_{s}) d s$ has mean $E_{i} [V] = \sum_{j} f (j) E_{i} [time in j per cycle] = \sum_{j} f (j) π_{j} E_{i} [T_{i}]$ , the occupation identity from Proposition 2. The renewal-reward theorem gives $\frac{1}{t} \int_{0}^{t} f (X_{s}) d s \to E_{i} [V] / E_{i} [T_{i}] = \sum_{j} π_{j} f (j)$ a.s., the partial last cycle negligible because $f$ is bounded and $R_{N (t)} / t \to 1$ . $□$

Proposition 6 (detailed balance characterises reversibility). A probability $π$ with $π_{i} > 0$ satisfies detailed balance $π_{i} q_{ij} = π_{j} q_{j i}$ for all $i, j$ iff the stationary chain $(X_{t})_{0 \leq t \leq T}$ has the same finite-dimensional laws as its time-reversal $(X_{T - t})_{0 \leq t \leq T}$ .

Proof. The reversed stationary process is Markov with generator $\overset{q}{^}_{ij} = π_{j} q_{j i} / π_{i}$ (the reversed rates: $\overset{q}{^}_{ij} π_{i} = π_{j} q_{j i}$ is the stationary flux $j \to i$ relabelled). The reversal equals the forward chain in law iff $\overset{q}{^}_{ij} = q_{ij}$ for all $i, j$ , i.e. $π_{j} q_{j i} / π_{i} = q_{ij}$ , i.e. $π_{i} q_{ij} = π_{j} q_{j i}$ — exactly detailed balance. (One checks $\hat{Q}$ is a conservative $Q$ -matrix: $\sum_{j} \overset{q}{^}_{ij} = \sum_{j} π_{j} q_{j i} / π_{i} = (π Q)_{i} / π_{i} \cdot (- 1)$ -corrected $= 0$ since $π Q = 0$ , using that $π$ is invariant, which detailed balance guarantees by Exercise 4.) Detailed balance further makes $Q$ self-adjoint on $ℓ^{2} (π)$ : $⟨ Q f, g ⟩_{π} = \sum_{i, j} π_{i} q_{ij} f_{j} g_{i} = \sum_{i, j} π_{j} q_{j i} f_{j} g_{i} = ⟨ f, Q g ⟩_{π}$ , so the spectrum of $Q$ is real and the convergence rate is the spectral gap of a symmetric operator. $□$

Connections Master

The Q-matrix, jump chain, and holding-time construction 37.05.08 is the substrate of every result here: recurrence is inherited from the jump chain $Π$ , the mean holding time $1/ q_{i}$ is the weight converting the jump-stationary $ν$ into the time-stationary $μ$ , and the i.i.d. excursion structure that the strong Markov property at return times produces is exactly what powers the renewal-reward proof of the ergodic theorem — the continuous-time return time $T_{i}$ and its finiteness are the positive-recurrence datum read pathwise.
The transition semigroup and Kolmogorov equations 37.05.09 supply the analytic side: $π Q = 0$ is the infinitesimal form of time-stationarity $π P (t) = π$ , the forward equation gives the uniqueness argument identifying the two, and the matrix exponential $P (t) = e^{tQ}$ on finite state spaces furnishes the spectral form $\sum_{r} e^{μ_{r} t} v_{r} u_{r}^{⊤}$ whose $μ_{0} = 0$ term is the stationary projection and whose gap is the exponential convergence rate.
The discrete invariant-measure and positive/null-recurrence theory 37.05.05 is the template this unit reweights: the reciprocal-return-time formula $π_{i} = 1/ E_{i} [T_{i}]$ becomes $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ , the regeneration construction of the jump-chain invariant measure $ν$ is imported wholesale, and the positive/null dichotomy is refined by the holding-time-weighted sum $\sum_{i} ν_{i} / q_{i}$ that can flip the classification between the chain and its jump chain.
The discrete convergence-to-equilibrium and coupling theory 37.05.06 is applied to the $h$ -skeleton to drive the continuous-time convergence, but with the periodicity hypothesis removed: the exponential holding times make every skeleton $P (h)$ aperiodic, so the coupling theorem's aperiodicity requirement is automatically met, and the meeting-time tail there becomes the spectral-gap decay here.

Historical & philosophical context Master

The systematic theory of stationary and limiting distributions for continuous-time chains grew from Kolmogorov's analytic foundations of the 1930s, but the reversibility strand has a sharper origin. Andrei N. Kolmogorov's 1936 Mathematische Annalen note on the theory of Markov chains ^{[Kolmogorov 1936]} isolated the condition under which a chain's stationary process is statistically indistinguishable from its time-reversal, proving that reversibility is equivalent to the cycle condition on transition rates now called Kolmogorov's criterion. This converted a probabilistic symmetry into a checkable algebraic identity on the rate matrix.

The probabilistic computation of the invariant distribution through the embedded jump chain and the holding times — the bridge $π_{i} = (ν_{i} / q_{i}) / \sum_{k} (ν_{k} / q_{k})$ and the return-time formula $π_{i} = 1/ (q_{i} E_{i} [T_{i}])$ — is the form given in Norris ^{[Norris 1997]}, following the renewal-theoretic tradition of Feller and Chung. The distinction between the time-stationary measure $μ$ with $μ Q = 0$ and the jump-stationary measure $ν$ with $ν Π = ν$ , and its consequences for queueing networks (PASTA, rate conservation), is developed systematically by Asmussen ^{[Asmussen 2003]}. Frank Kelly's monograph on reversibility and stochastic networks ^{[Kelly 1979]} made detailed balance the organizing principle for product-form equilibrium distributions of interacting queueing systems, where the cycle condition's failure or success determines whether a network has a tractable stationary law.

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{Kolmogorov1936,
  author  = {Kolmogorov, Andrei N.},
  title   = {Zur {T}heorie der {M}arkoffschen {K}etten},
  journal = {Mathematische Annalen},
  volume  = {112},
  year    = {1936},
  pages   = {155--160}
}

@book{Asmussen2003,
  author    = {Asmussen, S{\o}ren},
  title     = {Applied Probability and Queues},
  edition   = {2},
  series    = {Stochastic Modelling and Applied Probability},
  publisher = {Springer},
  year      = {2003}
}

@book{Liggett2010,
  author    = {Liggett, Thomas M.},
  title     = {Continuous Time Markov Processes: An Introduction},
  series    = {Graduate Studies in Mathematics},
  volume    = {113},
  publisher = {American Mathematical Society},
  year      = {2010}
}

@book{Kelly1979,
  author    = {Kelly, Frank P.},
  title     = {Reversibility and Stochastic Networks},
  publisher = {Wiley},
  year      = {1979}
}

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

Prerequisites

37.05.08
37.05.09
37.05.05
37.05.06

Tier anchors

beginner: Norris 1997 *Markov Chains* (Cambridge) §3.5-3.8; informal picture of a continuous-time chain whose long-run fraction of time in each state settles to a fixed split, recoverable either by balancing the flow rates in and out of each state or by watching the jump chain and weighting by how long each visit lasts
intermediate: Norris 1997 *Markov Chains* (Cambridge) §3.5-3.8 (recurrence via the jump chain, the invariant equation πQ=0, convergence to equilibrium and the ergodic theorem, detailed balance); Anderson 1991 *Continuous-Time Markov Chains* Ch. 5-6
master: Norris 1997 *Markov Chains* (Cambridge) §3.5-3.8; Asmussen 2003 *Applied Probability and Queues* 2e Ch. II §4-5; Liggett 2010 *Continuous Time Markov Processes* Ch. 2-3; Chung 1967 *Markov Chains with Stationary Transition Probabilities* 2e Ch. II (recurrence and the invariant measure)

References

Norris — Markov Chains · Cambridge University Press 1997, §3.5-3.8 (recurrence via the jump chain, πQ=0, convergence to equilibrium, the ergodic theorem, detailed balance)
Asmussen — Applied Probability and Queues, 2e · Springer 2003, Ch. II §4-5 (stationarity and the embedded jump chain, time-stationary vs jump-stationary measures)
Liggett — Continuous Time Markov Processes: An Introduction · American Mathematical Society 2010, Ch. 2-3 (recurrence, stationary distributions, ergodic theorem)
Kolmogorov — Zur Theorie der Markoffschen Ketten · Mathematische Annalen 112 (1936), 155-160 (reversibility and the stationary measure of a Markov chain)
Kelly — Reversibility and Stochastic Networks · Wiley 1979, Ch. 1 (detailed balance and reversibility for continuous-time chains)

Estimated time

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