Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds
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.
| Quantity | C | Ĉ | Match |
|---|---|---|---|
| mean time to next event | 5/16 | 5/16 | yes |
| mean residence time in B | 11/32 | 5/12 | no |
| P(reach G), T→∞ | 7/8 | 5/6 | no |
| P(reach H), T→∞ | 1/8 | 1/6 | no |
