← All papers
First page of Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

Bingqing Hu, Landon Taylor, Zhen Zhang

cs.LO Nov 16, 2026 · v1
Formalizes harmonic-mean CTMC aggregation and its time-bounded reachability error bounds in Lean 4 using Mathlib, with source code released.
Abstracting a continuous-time Markov chain by grouping its states into blocks raises a fundamental question: which rates should the abstract chain use when states within a block have different exit rates and transition probabilities? We study harmonic-mean aggregation, which matches the mean waiting time and next-block distribution of a local experiment that uniformly selects a state within the block and observes its next jump. Equivalently, the abstract transition rates are averages of the concrete rates with inverse-exit-rate weights. Since the aggregation does not preserve reachability probabilities in general, we derive theoretical error bounds for time-bounded reachability. We decompose the error into a blockwise mean and centered-within-block deviations, and show that the rate mismatch has zero weighted mean. Exploiting this cancellation and differences between abstract reachability values, we obtain bounds valid at every time horizon through a linear comparison system with two quantities per block, without computing concrete reachability values. All results are formalized and proven in Lean 4.

When the states of a continuous-time Markov chain are grouped into blocks, the abstract chain needs transition rates, even though states within a block differ in exit rates and destinations. The aggregation also does not preserve reachability probabilities, so its error needs bounding.

Harmonic-mean aggregation chooses abstract rates that match the mean waiting time and the next-block distribution of a local experiment: pick a state uniformly in the block and observe its next jump. This makes the abstract rates inverse-exit-rate-weighted averages of the concrete rates. The time-bounded reachability error is split into a weighted block-mean part and centered within-block deviations, using the fact that the rate defect has zero weighted mean. Marked theorems and definitions are formalized in Lean 4 via Mathlib.

The paper obtains error bounds valid at every time horizon from a linear comparison system with two quantities per block, without computing concrete reachability values. On a running example, eventual reachability is 7/8 for the concrete chain and 5/6 for the abstraction. The paper states that all results are kernel-checked in Lean 4.

QuantityCĈMatch
mean time to next event5/165/16yes
mean residence time in B11/325/12no
P(reach G), T→∞7/85/6no
P(reach H), T→∞1/81/6no
Running example: concrete vs. abstract chain (uniform start)