# Are Parametric Markov Chains Monotonic?

arXiv: https://arxiv.org/abs/1907.08491 · HTML: https://mlsanity.com/paper/1907.08491/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2019.

## Built on by (most cited first, 6 of 6)

- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [Fine-Tuning the Odds in Bayesian Networks](https://mlsanity.com/paper/2105.14371/) (2021)
- [Graph-Based Reductions for Parametric and Weighted MDPs](https://mlsanity.com/paper/2305.05739/) (2023)
- [Best-Effort Policies for Robust Markov Decision Processes](https://mlsanity.com/paper/2508.07790/) (2025)
- [Finding an ε-close Variation of Parameters in Bayesian Networks](https://mlsanity.com/paper/2305.10051/) (2023)
- [Analyzing Value Functions of States in Parametric Markov Chains](https://mlsanity.com/paper/2504.17020/) (2025)

## Abstract (arXiv)

This paper presents a simple algorithm to check whether reachability probabilities in parametric Markov chains are monotonic in (some of) the parameters. The idea is to construct - only using the graph structure of the Markov chain and local transition probabilities - a pre-order on the states. Our algorithm cheaply checks a sufficient condition for monotonicity. Experiments show that monotonicity in several benchmarks is automatically detected, and monotonicity can speed up parameter synthesis up to orders of magnitude faster than a symbolic baseline.