一句话：提出任意精度近似多维成本马尔可夫链总成本分位数的算法，并证明其判定版本属于计数层级。
许多概率系统会累积能量或成本等量，这类系统可建模为成本链：转移上标注数值成本向量的马尔可夫链。计算总累积成本分布的信息，例如总成本的中位数或高成本概率，是该模型的基本问题。本文研究所谓成本问题，即计算总成本的分位数。尽管这些概率是否总可计算甚至是否有理仍是开放问题，作者提出一种能以任意精度近似这些概率的算法。该算法表述和实现简单，并利用图论中的 BEST 定理来高效计算有向图中的欧拉回路数目。此外，该算法还用于证明成本问题的判定版本属于计数层级，该层级包含多项式时间层级且包含于 PSPACE。最后，作者通过实验评估了算法的适用性。
Probabilistic systems that accumulate quantities such as energy or cost are naturally modelled by cost chains, which are Markov chains whose transitions are labelled with a vector of numerical costs. Computing information on the probability distribution of the total accumulated cost is a fundamental problem in this model. In this paper, we study the so-called cost problem, which is to compute quantiles of the total cost, such as the median cost or the probability of large costs. While it is an open problem whether such probabilities are always computable or even rational, we present an algorithm that allows to approximate the probabilities with arbitrary precision. The algorithm is simple to state and implement, and exploits strong results from graph theory such as the so-called BEST theorem for efficiently computing the number of Eulerian circuits in a directed graph. Moreover, our algorithm enables us to show that a decision version of the cost problem lies in the counting hierarchy, a counting analogue to the polynomial-time hierarchy that contains the latter and is included in PSPACE. Finally, we demonstrate the applicability of our algorithm by evaluating it experimentally.