Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds
Bingqing Hu, Landon Taylor, Zhen Zhang
原文摘要
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.
cs.LO