The Arnoldi Aggregation for Approximate Transient Distributions of Markov Chains
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913974203711488 |
|---|---|
| author | Sonnentag, Patrick Michel, Fabian Siegle, Markus |
| author_facet | Sonnentag, Patrick Michel, Fabian Siegle, Markus |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02078 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Arnoldi Aggregation for Approximate Transient Distributions of Markov Chains Sonnentag, Patrick Michel, Fabian Siegle, Markus Probability 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. |
| title | The Arnoldi Aggregation for Approximate Transient Distributions of Markov Chains |
| topic | Probability |
| url | https://arxiv.org/abs/2508.02078 |