标题： 找到马尔可夫链的最小可能精确聚合 显示英文标题

标题： Finding the Smallest Possible Exact Aggregation of a Markov Chain

摘要： 马尔可夫链是计算机科学、经济学、生物学和众多其他领域中建模和评估系统的重要工具。 因此，近似马尔可夫链是一种有用的工具，通过减少状态空间的大小来降低分析所需的计算工作量。 到目前为止，大多数近似算法专注于寻找再次为马尔可夫链的近似值。 我们消除了这一限制，并提出了一种使用Arnoldi迭代的算法。 此外，我们证明了如果这些近似值没有误差，它们的规模是最小的。 最后，我们实现了通过Arnoldi迭代的马尔可夫链算法。 如果另一种称为Exlump聚合的聚合类型可以为马尔可夫链找到精确的聚合，它们通常在运行时间大大降低的情况下产生相似或更小的误差。 相反，通过Arnoldi迭代计算的近似值可以在Exlump无法找到聚合的地方找到可用的聚合。 尽管如此，运行时间仍然是一个主要问题，因为我们的近似状态空间大小确定标准非常昂贵。 因此，需要进一步的工作来减少Arnoldi方法的运行时间。 显示英文摘要

摘要： Markov chains are an important tool for modelling and evaluating systems in computer science, economics, biology and numerous other fields. Thus, approximating Markov chains is a useful tool for decreasing the computational effort needed for analysis by reducing the size of the state space. So far, most approximative algorithms focused on finding approximations, which are, again, Markov chains. We remove this restriction and present an algorithm using the Arnoldi iteration. Further, we show that if these approximations are without error, they are of minimal size. Lastly, we implement the algorithm for Markov chains via the Arnoldi iteration. If another type of aggregation, so-called Exlump aggregations, can find an exact aggregation for a Markov chain, they usually yield similar or smaller errors at much lower runtime. On the contrary, approximations computed via the Arnoldi iteration can find usable aggregations where Exlump yields none. Still, runtime is a primary concern, as our criterion for determining the approximate state space size is exceptionally costly. As such, further work is needed to decrease the runtime of the Arnoldi approach.