Quantitative Verification of Stochastic Systems

20 concepts20 papers1 proposal

When modeling complex, dynamic systems—such as a cellular signaling pathway, a DNA computing circuit, or an unfolding epidemic—we are forced to confront randomness. Traditionally, scientists turn to two main tools: Ordinary Differential Equations (ODEs) and stochastic simulations (such as Monte Carlo or Gillespie algorithms).

ODEs capture the average-case behavior of millions of components, but they completely smooth over the stochastic noise that can drive a system into radically different states. Stochastic simulations do capture this noise by rolling dice to generate individual trajectories. However, simulation is inherently non-exhaustive. If a critical event—such as a circuit failure, immune system collapse, or hospital saturation—is rare, a simulation might need to be run millions of times to observe it even once.

As highlighted by Ezio Bartocci et al. in Computational Modeling, Formal Analysis, and Tools for Systems Biology, treating these processes as concurrent reactive systems allows us to move beyond limited simulation runs. Instead of guessing via sampling, we can use Probabilistic Model Checking (PMC) to mathematically prove how a system will behave across all possible execution paths.

From Trajectories to State Spaces

How do we transition from running individual simulations to analyzing an entire universe of possibilities? The core idea is to represent the system as a formal state-transition graph where transitions are governed by probabilities or rates.

Depending on the nature of the system, it can be modeled as:

  • A Discrete-Time Markov Chain (DTMC), where steps occur at fixed intervals.
  • A Continuous-Time Markov Chain (CTMC), where transitions happen at continuous stochastic rates (ideal for biochemical reactions).
  • A Markov Decision Process (MDP) or Partially Observable MDP (POMDP), which blends probabilistic uncertainty with non-deterministic choices or control strategies, as demonstrated by Luigi Palopoli et al. in A Markovian Model for the Spread of the SARS-CoV-2 Virus.

Once the system is framed as a state space, we can query it using formal probabilistic logics, such as Probabilistic Computation Tree Logic (PCTL). Instead of asking a binary question ("Will the system fail?"), we ask a quantitative one: "What is the exact probability that the system reaches a failure state within $T$ time steps?" As Fawad Ali Mangi et al. note in Advancing verification of process mining models with quantitative model checking in stochastic environment, this shifts the paradigm from binary success/failure verification to precise quantitative metrics over a finite state space.

Exact Computation via Linear Algebra

The magic of probabilistic model checking is that it does not rely on random sampling to find these probabilities. Instead, it converts temporal logic queries into exact mathematical operations over the state transition matrix.

Consider a simple reachability query: finding the probability of eventually reaching a target state $S_{\text{target}}$. The model checker partitions the state space into three distinct sets:

  1. States that can never reach $S_{\text{target}}$ (probability = 0).
  2. States that are already in $S_{\text{target}}$ or will inevitably reach it (probability = 1).
  3. The remaining states, where the probability is strictly between 0 and 1.

For this third set, the exact probabilities are calculated by setting up a system of linear equations. If $x_i$ is the probability of reaching the target from state $i$, then:

$$x_i = \sum_{j} P_{ij} \cdot x_j$$

where $P_{ij}$ is the transition probability from state $i$ to state $j$.

As explained by Vojtěch Forejt et al. in Automated Verification Techniques for Probabilistic Systems, tools solve these systems using exact or highly accurate numerical methods like value iteration, interval iteration, or linear programming. By leveraging symbolic data structures (like Binary Decision Diagrams) and model reduction strategies, as discussed by Sebastian Junges et al. in Scalable Analysis of Probabilistic Models and Programs (Dagstuhl Seminar 23241), model checkers compress and analyze massive state spaces that would be impossible to navigate via brute-force simulation.

Applications Across Domains

This mathematical machinery allows researchers to exhaustively verify complex real-world systems across diverse fields:

The same underlying principles extend to analyzing user interaction friction in software analytics (Oana Andrei et al. in Probabilistic Model Checking of DTMC Models of User Activity Patterns), verifying the reliability and maintenance costs of smart building HVAC systems (Carlos E. Budde et al. in Modelling Smart Buildings Using Fault Maintenance Trees), and validating hybrid biological models that combine discrete and continuous processes (Masao Nagasaki et al. in Simulation-based model checking approach to cell fate specification during Caenorhabditis elegans vulval development by hybrid functional Petri net with extension; Md. Ariful Islam et al. in Model Checking Tap Withdrawal in C. Elegans).

Key Foundational Work

Probabilistic Methods in Verification and Planning (Dagstuhl Seminar 03201) (2003) — contributed 1 concept elements to this direction.
Symbolic Model Checking for Probabilistic Timed Automata (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_model_checking_5914ce1e,
  title = {probabilistic model checking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-model-checking/rdr_5914ce1e49724727aa1a85b33a98da38},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_probabilistic_model_checking_5914ce1e_v1,
  title = {probabilistic model checking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-model-checking/rdr_5914ce1e49724727aa1a85b33a98da38/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake