Analyzing Value Functions of States in Parametric Markov Chains
Kasper Engelen, Guillermo A. Pérez, Shrisha Rao · 2025
Read Analyzing Value Functions of States in Parametric Markov Chains by Kasper Engelen, Guillermo A. Pérez, Shrisha Rao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17020.txt.
Introduction
Kasper Engelen, Guillermo Pérez, and Shrisha Rao wrote this 2025 computer science paper on parametric Markov chains. These chains model systems whose chance of each step is not fully known, since some probabilities are left as parameters. Checking reachability claims for such systems is known to be very hard in theory.
One easier angle is monotonicity, asking whether raising a parameter never lowers a reachability chance. The authors first show that this question can be turned into a comparison of two states and their reachability chances. Recent results on that comparison then give a fast way to merge states that share the same value. They built the method and tested it on known and custom benchmarks. Merging shrank some known cases and cut custom cases by large amounts.
Catalog record
| CREATOR | Kasper Engelen, Guillermo A. Pérez, Shrisha Rao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17020
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Analyzing Value Functions of States in Parametric Markov Chains Thanks: Work supported by the Flemish (Belgium) inter-university (iBOF) “DESCARTES” and the Belgian F.R.S.-FNRS/FWO SynthEx (G0AH524N) projects. Kasper Engelen, Guillermo A. Pérez, Shrisha Rao Abstract Parametric Markov chains (pMC) are used to model probabilistic systems with unknown or partially known probabilities. Although (universal) pMC verification for reachability properties is known to be coETR-complete, there have been efforts to approach it using potentially easier-to-check properties such as asking whether the pMC is monotonic in certain parameters. In this paper, we first reduce monotonicity to asking whether the reachability probability from a given state is never less than that of another given state. Recent results for the latter property imply an efficient algorithm to collapse same-value equivalence classes, which in turn preserves verification results and monotonicity. We implement our algorithm to collapse “trivial” equivalence classes in the pMC and show empirical evidence for the following: First, the collapse gives reductions in size for some existing benchmarks and significant reductions on some custom benchmarks; Second, the collapse speeds up existing algorithms to check monotonicity and parameter lifting, and hence can be used as a fast pre-processing step in practice. Keywords— Markov chains, State-space reduction, Parameters. 1 Introduction Finite-state Markovian models are widely used as an operational model for the quantitative analysis of systems with probabilistic behavior. For state reachability in Markov chains, there are well known probabilistic model checkers such as Storm [ 13 ] and PRISM [ 20 ] . However, in practice, it is not guaranteed that the exact probabilities in the model are known. One way to circumvent this is by modeling unknown probabilities as parameters and known relations between probabilities as functions over shared parameters. Parametric Markov chains (pMCs, for short) [ 11 ] extend classical Markov chains with parameters, i.e. a finite set of real-valued variables, so that transition probabilities are now polynomials over these parameters. Applications of pMCs include model repair [ 5 , 8 , 9 , 16 , 25 ] , planning in POMDPs [ 18 ] , and optimizing randomized distributed algorithms [ 1 ] . Analysis of pMCs is supported by established probabilistic model checkers Storm, PRISM, as well as dedicated tools such as PARAM [ 17 ] and PROPhESY [ 12 ] . The pMC verification problem asks: Given \lambda\in[0,1] , is the probability of reaching the target state from the start state, for all valid parameter valuations, at least \lambda ? This problem is known to be coETR-complete [ 28 , 15 ] . Related to the verification problem, the concept of the never-worse relation (NWR) for pMCs has been introduced in [ 27 , 15 ] . Intuitively, a state is never worse than another if, for all valuations of the parameters, the probability of reaching the target state from the former state is at least as much as that from the latter. Another related notion is that of monotonicity: The (value from a) state is said to be monotonically increasing in a parameter if, for all valuations of the parameters, the probability of reaching the target state from it increases when the value of the parameter increases. Both the NWR and monotonicity turn out to be coETR-complete: Spel et al. [ 30 ] give a simple polynomial-time reduction from pMC verification to the monotonicity problem by first reducing it to the NWR problem and then reducing the NWR problem to the monotonicity problem. Since the NWR problem is coNP-hard even when parameterization is trivial (i.e., every transition is labeled with a unique variable) [ 27 ] , this implies that the monotonicity problem is also coNP-hard when the parameters are trivial. Despite the discouraging complexity lower bounds recalled above, efficiently-checkable sufficient conditions to establish monotonicity were given in [ 30 ] . Similarly, efficiently-checkable sufficient conditions for establishing never-worse relationships were studied in [ 15 ] . In particular, an efficient algorithm to compute equivalence classes of trivially parameterized MCs also follows from [ 15 ] . Contributions. In this work, we first give a quasi-polynomial-time construction of a pMC whose solution function is the derivative of the solution function of a given pMC. Interestingly, our construction relies on classical results from circuit complexity theory that also allow us to give a polynomial-sized representation of solution functions. Having access to this derivative pMC, we establish a reduction from monotonicity to the NWR problem. Then, we give an algorithm for collapsing some (not necessarily all) equivalence classes of the pMC using the techniques from [ 15 ] . We present an implementation in Storm and perform experiments. We evaluate our implementation on several benchmarks from the existing literature and some custom benchmarks, showing that the equivalence-class collapse runs very fast, even for larger benchmarks, and speeds up the monotonicity check in many cases. Finally, we also evaluate our tool as a pre-processing step before parameter lifting (a technique used for near-optimal parameter synthesis) [ 30 ] and observe that there too the equivalence-class collapse is sometimes useful. 2 Preliminaries In this section, we introduce the notation we will be using for polynomials, circuits, and Markov chains with parameters. For the latter, we follow as much as possible the notation used in [ 2 ] . Let x_{1},\dots,x_{m} be parameters that can take real values and write \boldsymbol{x}=(x_{1},\dots,x_{m}) . 2.1 Polynomials and rational functions By \mathbb{Q}[\boldsymbol{x}] , we denote the polynomial ring in \boldsymbol{x} over the rationals; by \mathbb{Q}(\boldsymbol{x}) , the analogue rational field . For an (exponent) vector \boldsymbol{\alpha}\in\mathbb{N}^{m} , we write \boldsymbol{x}^{\boldsymbol{\alpha}} to denote the monomial \prod_{i=1}^{m}x_{i}^{\alpha_{i}} . Now, every polynomial f\in\mathbb{Q}[\boldsymbol{x}] can be written as a sum of products \sum_{\boldsymbol{\alpha}\in I}c_{\boldsymbol{\alpha}}\boldsymbol{x}^{\boldsymbol{\alpha}} for I a finite subset of \mathbb{N}^{m} and where c_{\boldsymbol{\alpha}}\in\mathbb{Q} for all \boldsymbol{\alpha}\in I . The support of f is the subset of I with a nonzero coefficient, \mathop{\mathrm{supp}(f)}=\{\boldsymbol{\alpha}\in\mathbb{N}^{m}\mid c_{\boldsymbol{\alpha}}\neq 0\} . When \mathop{\mathrm{supp}(f)} is empty, we say f is the zero function and write f\equiv 0 . The degree and maximal coefficient component of f are \mathop{\mathrm{deg}(f)}=\max\{\sum_{i=1}^{m}\alpha_{i}\mid\boldsymbol{\alpha}\in\mathop{\mathrm{supp}(f)}\} and \mathop{\mathrm{coeff}(f)}=\max\{|a|,|b|\in\mathbb{N}:\boldsymbol{\alpha}\in\mathop{\mathrm{supp}(f)},\frac{a}{b}=c_{\boldsymbol{\alpha}}\text{ and is irreducible}\} , with the convention that \max\emptyset=0 . 2.2 Circuits for polynomials An (arithmetic) circuit over \mathbb{Q}[\boldsymbol{x}] is a labeled directed acyclic graph (DAG) \mathcal{C}=(V,E,\ell,o) . Vertices with indegree (a.k.a. fanin ) 0 are called input gates and they are labeled by \ell with some x_{i} or a constant from \{-1,0,1\} . The other vertices all have fanin 2 , are called computation gates , and are labeled by one of the operations from the ring, i.e. + and \times . The output gate is o\in V . The size |\mathcal{C}| of the circuit is |V| ; its depth , noted 0pt{\mathcal{C}} , is the length of a maximal path in \mathcal{C} . Every vertex v of the circuit computes a polynomial function defined inductively: If v is an input gate, its function is the expression with which it is labeled, i.e. [\![v]\!]=\ell(v) ; otherwise, [\![v]\!] is the application of the operation \ell(v) to all [\![u_{i}]\!] such that (u_{i},v)\in E . Finally, we write [\![\mathcal{C}]\!]=[\![o]\!] for the function computed by the output gate. Let f\in\mathbb{Q}[\boldsymbol{x}] be a polynomial. If f is given in its sum-of-products representation, one can construct a circuit \mathcal{C} of size O(|\mathop{\mathrm{supp}(f)}|\mathop{\mathrm{deg}(f)}\log(\mathop{\mathrm{coeff}(f)})) such