Why compute with a clock that sometimes does nothing?
A generator tells us how quickly a chain leaves each state. A transition matrix tells us where it will be after a specified amount of time. These answer different questions: knowing the next jump destination does not account for the possibility of no jumps, several jumps, or a return to the initial state before observation.
The earlier generator note introduced uniformization. Here we develop it as an exact construction and a practical calculation with a certified remainder. One common clock rings at every state; some rings merely retain the current state. This apparent extra work replaces many different holding rates by one independent Poisson count. Conditional on that count, the calculation becomes an ordinary power of a stochastic matrix.
Everything in this note concerns a finite state space. In particular, there is a finite bound on all departure rates, every matrix operation is finite-dimensional, and the constructed path exists at every finite time. The general unbounded-rate existence and embedded-occupation questions belong to the preceding notes.
The finite generator and the independent ingredients
Let with . A conservative generator is a real matrix satisfying
Thus , where is the column of ones. Probability distributions are row vectors throughout. Choose a number such that , and define
Every entry of is nonnegative and its rows sum to one. The off-diagonal entries of have units of inverse time; the entries of are probabilities.
Common mistake
(Choosing the clock slower than the fastest state)
A choice produces a negative diagonal entry , so is not a transition matrix and cannot define the construction. The algebraic identity survives, but its terms lose their probabilistic meaning; the counterexample after the Poisson-tail certificate shows the consequence.
Take a discrete Markov chain with transition matrix and a rate- Poisson process independent of the entire chain. For an initial law , choose with law , independent of the clock, and use fresh independent random choices for each transition of . Set
Independence is essential. A random index with a Poisson marginal is not enough: if its value depends on the future transitions of , conditioning on the index can change the chain's distribution. Our construction supplies independent ingredients before composing them.
There is a simple zero case. If the desired choice is , the inequality forces . Define and directly. There is no division by zero and no need to assign a meaning to . Alternatively, for this same zero generator any positive gives ; all clock events are virtual.
From virtual events to actual holding times
Suppose and , and let be the first genuine departure time. Until a genuine departure, each clock event retains state with probability . Conditional on , avoiding departure through time therefore has probability . Averaging gives
Common mistake
(Reading the clock wait as the holding time)
The actual holding time is exponential of rate , although a single waiting time between clock events is exponential of rate . They need not be the same random time, because the first ring may be virtual.
For a distinct state , summing over the possible number of virtual events before departure gives
The destination is independent of the departure time. To see this without inferring independence merely from two marginals, let be the index of the first successful departure event. The joint probability that and its destination is equals
The destination is consequently independent of and of the independent clock waiting times; the actual holding time is the sum of the first such waits. At departure, fresh transition choices and fresh exponential clock waits restart the argument. Hence the successive genuine holds have precisely the usual exponential construction, with independence conditional on the genuine visited states. If , the whole row has no outward rate, , and is absorbing.
There are finitely many Poisson events on every bounded interval almost surely, so there are finitely many genuine jumps there as well. This proves non-explosion directly. It does not prove anything about a countable generator with unbounded departure rates: such a generator may admit no finite common .
The transition law and its semigroup
Theorem 3.6.1
(Finite uniformization)
For the independent construction above and ,
The matrices are stochastic and satisfy , and
For a probability row vector , the three statements , and for every are equivalent. For every probability is stationary, including in the direct zero-clock construction.
Proof
(Poisson mixture, Markov property and semigroup)
Given , independence leaves the distribution of unchanged, so its transition matrix from is . This proves the Poisson mixture. Each summand is nonnegative and each row sums to its Poisson weight; the full row sum is one.
The construction is Markov: after time , the clock has independent increments, and the unused transition choices are fresh. Let contain the clock history through and . Conditional on this larger history, future transitions depend on the past only through , so . The natural history is contained in . The tower property of conditional expectation therefore gives the same formula conditional on , which is the required Markov property for itself.
There is also an instructive direct proof of the semigroup identity. Multiply the two series, group terms with , and use the binomial theorem:
Nonnegative entries justify regrouping; absolute convergence also follows in any finite matrix norm. Since and commutes with , the convergent matrix-exponential series gives . This proves the second formula and permits differentiation term by term on bounded time intervals. In particular .
Finally is equivalent to . The latter implies for every , so the mixture preserves . Conversely, differentiating at zero gives . Finite dimension justifies the derivative. No irreducibility assumption was needed for these equivalences.
Proof X-ray
What each assumption pays for
The proof has four steps, and each consumes a different hypothesis.
- The mixture formula conditions on . This is legitimate only because the clock is independent of the whole chain ; the condition makes each a transition matrix, so every term is a nonnegative matrix whose row sums equal its Poisson weight.
- The Markov property is first proved for the larger history , which contains the clock and the discrete path. The subtle move is the tower property: a formula valid given remains valid given the smaller history , because the right side is already -measurable.
- The semigroup law and are matrix algebra; nonnegativity justifies regrouping and the commutation of with justifies splitting the exponential.
- Finite dimension justifies differentiating at zero, which turns into .
The argument closes because the construction already defines a probability process; formal powers of a matrix alone do not supply that construction for an unbounded infinite-state model.
Why the arbitrary clock rate does not change the process
Different admissible positive choices of produce different matrices and different numbers of virtual events. They all produce the same . They also produce the same exponential genuine holds and destination laws derived above. Increasing adds work, not physical transitions.
The fixed-time kernels also determine the long-run behavior, and here finiteness gives a complete answer.
Theorem 3.6.2
(Stationary laws of a finite generator)
Every finite conservative generator has a stationary probability. If is irreducible, then every entry of is positive for each , the stationary probability is unique, and for every initial probability .
Proof
(Averaging for existence, a positive kernel for uniqueness)
No irreducibility is needed for existence. One finite-dimensional justification starts with the averages . A convergent subsequence exists in the compact probability simplex. Multiplying an average by shifts its integration interval; its difference is at most . Any subsequential limit is therefore stationary for each .
For uniqueness, now assume irreducibility and fix . Every pair is connected by a finite positive-rate path. Its corresponding power of has a positive entry, and its Poisson weight at time is positive. For , the zeroth power already contributes a positive diagonal entry. Thus every entry of is positive. If and , then . For , write , where is uniform and is stochastic. This contracts differences of probability laws in by at most . If , all rows already equal . Two stationary laws must coincide. The same contraction proves convergence along multiples of ; a remaining interval shorter than cannot increase the distance to stationarity. Even when genuine jumps alternate, fixed-time probabilities can converge.
Proof X-ray
Two different reasons for existence and uniqueness
Existence and uniqueness rest on different features. Existence uses only finiteness: the time averages lie in the compact simplex, and the window-shift estimate makes every subsequential limit invariant under each . Uniqueness needs irreducibility, which enters through positivity of every entry of ; the diagonal is positive for free because the zero-event term is present. The key move is the split . For laws one has , so the common part disappears and only the factor of the difference survives each step of length .
A complete two-state calculation
Worked example 3.6.3
(Two clocks, one transition matrix)
Use states in this example, with rates and . Choose . Then
Every row of equals , so . The zeroth power is still : it represents no clock events. Summing the remaining weights gives the entire transition matrix,
At this is . At , the first row is approximately . The matrix starts at , each row sums to one, its derivative at zero is , and its rows tend to . These are separate checks on the calculation.
Starting from zero, the probability of no genuine departure by time is ; the probability of no clock event is . Neither is : the endpoint can be zero after departing and returning. The genuine embedded chain has matrix and stationary visit law , whereas the uniformized chain has invariant law . A typical visit counts each state equally; a typical time gives more weight to the longer hold at zero. This finite example distinguishes , and without repeating the general occupation-conversion theorem.
Any admissible clock rate may be used, and a faster clock only adds virtual events.
Worked example 3.6.4
(Doubling the clock rate)
For the same generator take . Then , and by and . The Poisson mixture gives the coefficient , so again . Under stationarity the clock rings at rate while genuine jumps occur at rate , so only of the rings change the state; with the fraction was .
Concept lensStructural
Three different counts
The Poisson count records potential updates. The genuine-jump count records actual changes of state. A fixed-time observation records only the current state. In the two-state example, the first count has mean regardless of the starting law. Under stationarity, the second has mean . The third has law at every observation time. Treating all three as a single notion of “transition” loses the clock information that uniformization was designed to preserve.
A finite calculation with a rigorous remainder
For and a nonnegative integer , define
The convention at gives the identity matrix exactly. For , the omitted weights are the tail probability . Every row of sums to rather than one. It is a substochastic lower approximation, not an exact stochastic transition matrix.
Proposition 3.6.5
(Poisson-tail certificate)
Entrywise, and each row of the difference sums to . Consequently, for any initial probability and any set ,
For any real observable with ,
These are truncation bounds in exact arithmetic, with floating-point roundoff requiring separate control.
Proof
(The omitted terms are nonnegative)
The omitted terms are nonnegative matrices, each with row sum . Summing them proves the entry and row-sum claims. A set captures between zero and all of the omitted mass. For the observable, take absolute values and bound each omitted value of by .
The nonnegativity of the omitted terms is exactly where the condition enters.
Counterexample mode
A slow clock breaks the lower bound
Claim: since for every , the certificate holds for any clock rate. Take the two-state generator of the worked example and . Then has a negative entry, and . At the zero-term truncation is , while . So has a negative entry and is not a lower bound. The condition makes every nonnegative, which is what the proof uses.
One can instead normalize when . For initial law , this is the conditional endpoint law given . It is not generally an entrywise lower bound. Writing the true law as a mixture of that conditional law and the conditional law on proves that its total-variation distance from the normalized answer is at most , with total variation defined as .
To compute one initial distribution, there is no need to form every full matrix power. Start from , update , and accumulate . The exact identities and hold for every finite ; this forward recursion is numerically convenient for moderate . At large , beginning at zero can underflow; choosing a numerically stable weight routine is an additional numerical-analysis task, not part of the exact-arithmetic certificate.
A useful explicit tail bound follows from the ratios. If , then every ratio beyond the first omitted weight is at most , so
Worked example 3.6.6
(Certifying the two-state law at )
With and , . For the condition holds and
Since for , the approximate zero-to-one probability is , against the exact . Its actual error is , although the general certificate allows the full . A bound need not be exact to be valid.
Exercises
Exercise 3.6.7
(For the two-state generator above, use . Find , verify its invariant law, and recover from its powers. Why is a negative eigenvalue of harmless?)
Core
Solution(3)
- 1
Form and check invariance
, and direct multiplication gives .
- 2
Split into complementary projections
Because: and .
- 3
Average over the Poisson count
The mixture sends the second coefficient to , so as before. A stochastic matrix needs nonnegative entries, not nonnegative eigenvalues; the alternating factor of the discrete powers is averaged out by the random clock.
Exercise 3.6.8
(Consider and . Find , every stationary probability, and the law from initial state zero at . What changes if all rates are zero?)
Foundation
Solution(3)
- 1
Compute the powers of
satisfies for , so
- 2
Solve for stationary laws and evaluate
forces , so is the unique stationary law. At , and the law from zero is , which is not stationary.
- 3
Treat the zero generator
For both states are absorbing, and every probability law is stationary, whether one uses the direct zero clock or a positive clock with .
Exercise 3.6.9
(Prove the tail-ratio bound. For , find the smallest for which the bound certifies , and decide whether replacing by preserves the entrywise lower-bound property.)
Core
Solution(3)
- 1
Compare with a geometric series
Key step
The omitted sum is at most , which is the stated bound.
Because: For , .
- 2
Evaluate at
For the bound is , too large; for it is . So is the smallest certified choice.
- 3
Test the normalized truncation
Normalization does not preserve lower bounds. In the two-state example its zero-to-zero entry is , larger than the true because . The total-variation certificate still holds by the conditional-mixture argument.
Exercise 3.6.10
(In the two-state example, start from zero. Find the expected number of genuine jumps by time and compare it with the expected number of potential updates. Explain why counting only zero-to-one transitions gives a different answer.)
Synthesis
Solution(3)
- 1
Integrate the departure rate
The expected genuine-jump count is .
Because: On an interval of length started in state , exactly one clock event contributes expected genuine count , and two or more events contribute at most ; summing over a partition of and refining gives the rate integral.
- 2
Substitute the transition law
With ,
- 3
Compare the other counts
Potential updates have mean and include rejected self-updates. Zero-to-one transitions alone have mean , because they omit every one-to-zero jump. Each count is useful once the event being counted is stated.