Motivation
A discrete chain records where a system goes after each update. It does not record the time spent between updates. Two systems can visit exactly the same sequence of states while spending very different fractions of real time in them. A continuous-time Markov chain adds state-dependent holding clocks. This extra layer matters whenever one state changes quickly and another persists for a long time.
Consider a machine that switches between two operating modes. If transitions out of the first mode are nine times faster than transitions out of the second, their alternating sequence contains equally many visits to each mode, but their time occupation is far from equal. Confusing the jump chain with the real-time chain would lose the very feature that the clocks were introduced to model.
We develop pure-jump chains on finite or countable spaces, then specialize to birth–death chains, where only neighboring states communicate in one jump. On an infinite space, the construction may perform infinitely many jumps before a finite time. We therefore state non-explosion assumptions before using stationary equations.
Definitions
Definition 3.1.1
(Rates, holding times and the embedded chain)
A conservative rate matrix on a countable space satisfies for and
At state with , wait an exponential time of rate , then choose the next distinct state with probability . Conditional on the sequence of visited states, holding times are independent. If , state is absorbing. The successive visited states form the embedded jump chain .
One concrete construction uses independent unit-rate exponentials and independent random choices for the jump destinations. If the state after jump is , its holding time is . Put and let be the sum of the first holding times. Before the limiting time , set for . Absorbing states stop further jumps. The process is non-explosive when almost surely, from every starting state. Until that property is checked, this construction defines only the minimal process before any explosion.
Concept lensAlgorithmic
Competing clocks give the same jump rule
Instead of one holding clock followed by a destination draw, start an independent exponential clock of rate for each and jump to the clock that rings first. Since , the first ring is almost surely attained, and
So the holding time is exponential of rate , the destination has law , and the two are independent, exactly as in the definition. Memorylessness lets all clocks restart after the jump. In this description each is the rate of one specific transition.
Definition 3.1.2
(Generator and birth–death rates)
For a non-explosive chain, write . The rate matrix describes the short-time limits
On , a birth–death chain has , for , and , with all other off-diagonal rates zero. A stationary probability distribution satisfies for every .
The diagonal is a nonpositive rate, not a transition probability; it is zero at an absorbing state. Its role is to balance total outward rate. The rows of sum to zero, whereas the rows of and sum to one. State zero in a birth–death model has no negative neighbor; inserting a death transition there changes the state space and invalidates the intended boundary condition.
Theorem/proposition
Theorem 3.1.3
(Bounded rates, uniformization and stationarity)
Suppose with . The chain is non-explosive. The matrix is stochastic and
For a probability row vector , is equivalent to stationarity. On a finite state space, ; if the chain is irreducible, it has a unique positive stationary distribution and .
For birth–death chains the stationary equations can be solved explicitly.
Theorem 3.1.4
(Birth–death equilibrium under bounded rates)
Assume for all , for all , and . Set
A stationary probability distribution exists exactly when . In that case it is unique and equals , satisfying detailed balance . If , these weights cannot be normalized; that fact alone does not distinguish null recurrence from transience.
The bounded-rate assumption is a sufficient condition chosen to keep existence and stationarity fully justified here. Many useful unbounded-rate models are also non-explosive, but need a separate argument. Writing a formal solution of on an infinite space does not automatically supply that argument or prove it is stationary for the intended process.
Proof sketch or proof idea
Proof
(A Poisson clock realizes the chain)
Use a Poisson clock of rate . At each clock event, move according to , allowing a move back to the same state. While at , each clock event leaves the state with probability . The probability of no genuine departure by time is
Conditional on a departure, destination has probability . Thus this construction has exactly the required holding times and destinations. There are finitely many Poisson clock events on any bounded interval, so genuine jumps cannot explode. Conditioning on the number of clock events proves the displayed formula for . The self-transitions in are virtual updates, not extra genuine jumps of the original process.
If , then and every term in the uniformization sum preserves . Conversely stationarity implies by differentiating at zero. Bounded rates justify this interchange even on a countable space: the generator acts as a bounded operator on summable row vectors. For finite matrices, the same series is . In the irreducible finite case choose so that every state has a positive virtual self-loop. The discrete chain is irreducible and aperiodic. Its convergence to a unique stationary law, combined with the Poisson count tending to infinity in probability, proves continuous-time convergence. There is no periodic obstruction from a deterministic alternation of genuine jumps because the holding clocks randomize the observation time.
Proof X-ray
Where the rate bound is used
The bound is used three times, each for a different purpose.
- It makes a stochastic matrix, so that the clock events can be realized by an actual discrete chain; the virtual self-loops absorb the unused rate .
- It reduces non-explosion to a property of one Poisson process: genuine jumps are a subset of clock events, which are finite on bounded intervals.
- It makes a bounded operator on summable row vectors, which justifies differentiating at zero on a countable space.
The key move is thinning: a geometric number of clock events, each an exponential wait of rate , sums to an exponential wait of rate . For the finite convergence statement the choice adds a second idea: positive self-loops make aperiodic, and the Poisson count tending to infinity transfers discrete convergence to continuous time.
The birth–death theorem needs only the stationary equations and the boundary at zero.
Proof
(Zero current across every edge)
For birth–death chains, at zero gives . At an interior state, rearranging its balance equation gives
The probability current across each edge is therefore constant, and the boundary forces that constant to zero. Iteration yields . If , normalization produces a probability vector; bounded-rate uniformization proves it is stationary. If , normalization is impossible unless , which would force every entry to vanish. This also proves uniqueness when normalization succeeds.
In the first theorem, the convergence statement needs irreducibility as well as finiteness.
Counterexample mode
A finite chain without irreducibility
Claim: every finite chain has a unique stationary law and . Take states with and all other off-diagonal rates zero, so and are absorbing. Then , so forces , and every with is stationary. From state one the chain leaves at rate and chooses each absorbing state with probability , so , while and . The limit depends on the starting state. Irreducibility is what forces all rows of toward one common vector.
Forward equations, backward equations and observables
Uniformization also explains which differential equation a transition matrix solves. Differentiate the absolutely convergent Poisson series, or differentiate the bounded matrix exponential. The result is
The forward equation considers a possible transition at the end of the time interval. The backward equation considers the first transition near its beginning. For an initial row law , the current law therefore obeys . Its coordinates balance inflow and outflow. In particular, setting that derivative to zero leads to the stationary equations, but the construction above is what makes those equations sufficient under the stated hypotheses.
A function of the state can be easier to interpret than the entire distribution. For a bounded real function , define
This is the instantaneous expected rate of change of the observable while the chain is at state . Under bounded rates, boundedness of justifies the sums and differentiation, giving . It does not mean an individual sample path has an ordinary derivative: a pure-jump path is constant between jumps and discontinuous at them. The derivative belongs to an expectation over many possible paths.
For the birth–death count, the formal drift of is at positive states and at zero. Since this function is unbounded, the bounded-function statement alone does not justify substituting it. One must first localize or establish the needed moment bounds. This small distinction is useful when checking equations returned by symbolic or numerical software: a correct-looking drift formula can still be used outside the assumptions of its proof.
Worked examples
Worked example 3.1.5
(Two modes: clocks change occupation)
Let and . Then
The embedded chain alternates deterministically, with stationary law . Yet the holding-time means are and , so the slower first state occupies the larger time fraction. Starting from zero, put . Its forward equation is with , yielding . This verifies convergence and illustrates why the embedded law is different from real-time equilibrium.
Worked example 3.1.6
(A single-server count with constant rates)
Let births occur at rate in every state, deaths at rate whenever the state is positive, and no death at zero. The total rate is at most , so existence and non-explosion follow. The weights are , , and
Detailed balance is checked by . More generally constant birth and positive-state death rates give . A stationary probability exists precisely when . At equality, constant weights cannot be summed; calling their formal equality an equilibrium probability would be an error.
Worked example 3.1.7
(Explosion despite finite rates at each state)
Consider a pure-birth chain with , starting at zero. Every individual holding rate is finite, but its successive independent holding times satisfy
Monotone convergence justifies this expectation. A nonnegative random variable with finite expectation is finite almost surely, so infinitely many births occur by a finite random time. The minimal process therefore explodes almost surely. Merely checking each row sum of is finite does not establish non-explosion. In contrast, the constant-rate Poisson birth process has holding-time sums tending to infinity by the strong law.
Common mistakes
Common mistake
(Confusing jump-chain weights with real-time weights)
The jump chain samples at transition times; the stationary continuous-time law samples at a typical fixed time. When the appropriate normalizations are finite and the chain is irreducible, the stationary jump-chain weights are proportional to , because visits to fast states occur more frequently. For example, rates and give real-time equilibrium , while the embedded chain still alternates with equal visit frequencies. Multiplying the real-time weights by gives equal weights, as expected. An absorbing state needs separate treatment because it has no next genuine jump.
Common mistake
(Treating detailed balance as the definition of equilibrium)
Detailed balance is stronger than stationarity in a general chain. A finite three-state directed cycle with rate one along each forward edge has uniform stationary law, because incoming and outgoing rates balance at every state. It does not satisfy detailed balance across an edge, since the reverse edge has rate zero. For the one-dimensional birth–death model, detailed balance arose from the nearest-neighbor structure and the reflecting boundary; it was derived, rather than imposed as a universal rule.
Common mistake
(Expecting truncation to create an equilibrium)
A numerical truncation also changes the boundary. Cutting a birth–death model at state and suppressing its last birth creates a finite reflecting model. Its stationary weights are the original weights only up to , renormalized by a finite sum. This computation can approximate an existing infinite-state equilibrium when the omitted tail is small, but cannot create an equilibrium for an infinite model whose diverges.
Summary
A rate matrix specifies exponential holding clocks and jump destinations. Bounded total rates allow a Poisson-clock construction that proves non-explosion, supplies the transition semigroup and justifies . Birth–death balance reduces to edgewise zero current, followed by a summability test. Infinite-state existence, real-time stationarity and jump-chain stationarity require separate checks.
Exercises
Quick check
(For rates and , find the stationary real-time law, the mean holding times and the embedded stationary law.)
Balance the flow across the single edge.
Solution · Answer
Balance is , so the law is . Mean holding times are and . The embedded chain alternates, giving ; weighting by the departure rates confirms equal jump weights.
Quick check
(A birth–death chain has for all and for . Find its stationary law, the probability of a positive state and the mean state.)
The weights are geometric with ratio .
Solution · Answer
With , the law is . The positive-state probability is , and the mean is . Total rates are bounded by , so the bounded-rate theorem applies.
Quick check
(For choose uniformization rate . Find , verify its row sums and stationary distribution, and explain why its self-transitions do not alter the model.)
Compute entry by entry.
Solution · Answer
. Both rows sum to one, and since both rows equal , that vector is preserved. Clock events that select the current state are not genuine departures; Poisson thinning gives departure rates and , so the original exponential holding laws are preserved.
Exercise 3.1.8
(A pure-birth chain has rates . Prove explosion from zero without computing the distribution of the explosion time.)
CoreProof
Solution(3)
- 1
Compute the expected holding times
Starting from zero, the -th holding time is exponential with mean .
- 2
Sum the expectations
Key step
.
Because: Monotone convergence applies to the nonnegative partial sums .
- 3
Conclude explosion
∎A nonnegative random variable with finite expectation is finite almost surely, so almost surely and infinitely many births occur before a finite time. No information about the density of is needed.