  A cost Markov chain is a Markov chain whose transitions are labelled with
non-negative integer costs. A fundamental problem on this model, with
applications in the verification of stochastic systems, is to compute
information about the distribution of the total cost accumulated in a run. This
includes the probability of large total costs, the median cost, and other
quantiles. While expectations can be computed in polynomial time, previous work
has demonstrated that the computation of cost quantiles is harder but can be
done in PSPACE. In this paper we show that cost quantiles in cost Markov chains
can be computed in the counting hierarchy, thus providing evidence that
computing those quantiles is likely not PSPACE-hard. We obtain this result by
exhibiting a tight link to a problem in formal language theory: counting the
number of words that are both accepted by a given automaton and have a given
Parikh image. Motivated by this link, we comprehensively investigate the
complexity of the latter problem. Among other techniques, we rely on the
so-called BEST theorem for efficiently computing the number of Eulerian
circuits in a directed graph.
