2025/08/04 by Patrick Sonnentag, Sonnentag, Patrick, Fabian Michel +3
Computer Science · Decision Sciences · #Aggregate (composite) #Bayesian Modeling and Causal Inference #FOS: Mathematics #Heuristic #Markov chain #Markov process #Probability (math.PR) #Simulation Techniques and Applications #State (computer science) #State space #Target Tracking and Data Fusion in Sensor Networks #Transient (computer programming)
paper · pdf · doi:10.48550/arxiv.2508.02078
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The paper proposes a new aggregation method, based on the Arnoldi iteration, for computing approximate transient distributions of Markov chains. This aggregation is not partition-based, which means that an aggregate state may represent any portion of any original state, leading to a reduced system which is not a Markov chain. Results on exactness (in case the algorithm finds an invariant Krylov subspace) and minimality of the size of the Arnoldi aggregation are proven. For practical use, a heuristic is proposed for deciding when to stop expanding the state space once a certain accuracy has been reached. Apart from the theory, the paper also includes an extensive empirical section where the new aggregation algorithm is tested on several models and compared to a lumping-based state space reduction scheme.