A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Probabilistic model checking verifies systems with stochastic behavior — nondeterministic choices and probabilistic events. Rather than asking "does this system have a property," it asks "what is the probability that this system has a property?" For example: "what is the probability the system reaches a goal state?" or "what is the expected time to recover from a failure?" Models include Markov chains (fully probabilistic: all transitions have fixed probabilities), Markov decision processes (MDP: mix of nondeterminism and probability, capturing systems controlled by both a scheduler and random events), and Markov automata (continuous-time systems with probabilistic and nondeterministic transitions). Properties are expressed in probabilistic temporal logic (PCTL, CSL) that quantifies probabilities: P(φ ≥ 0.95) means "the probability of φ is at least 95%." Probabilistic model checking computes the probability of properties or the expected values of reward measures, enabling quantitative verification of safety and liveness in systems with randomness.
Most formal verification assumes systems are deterministic: the same input always produces the same output. But real systems have stochastic behavior — randomness from the environment, probabilistic scheduling, or deliberate randomization in algorithms. A communication protocol may retry with some probability on failure; a distributed system may randomly choose a backup server; a hybrid system may have probabilistic transitions between modes. Probabilistic model checking extends traditional model checking to verify systems with randomness by computing the probability of properties rather than just checking yes/no.
Models and Properties
The most common model is a Markov chain: a transition system where each edge is labeled with a probability. From state s, the system transitions to state s' with probability p(s, s'). Properties are expressed in probabilistic temporal logic — extensions of LTL/CTL that quantify probabilities:
A simple property: P(◇goal) — "the probability of eventually reaching a goal state." Model checking computes this probability: the sum of probabilities of all paths leading to the goal, weighted by path probability.
Markov Decision Processes (MDPs)
Many systems are not purely probabilistic but combine nondeterminism and probability. A scheduling algorithm might nondeterministically choose which process to run, then probabilistically succeed. A network protocol might choose to retry or give up, and each choice has a probability of success. MDPs model this: states have multiple possible transitions (nondeterministic choices), each with its own probability distribution.
For MDPs, properties are interpreted with quantifiers over schedulers (entities making nondeterministic choices). P(φ ≥ 0.95) means: "does there exist a scheduler such that φ holds with probability at least 95%?" The model checker computes the maximum and minimum probabilities over all possible schedulers, answering: "what's the best we can do?" and "what's the worst that could happen?" This is essential for adversarial analysis (assuming the worst scheduler, like an attacker) or synthesis (finding a scheduler that achieves goals).
Computing Probabilities: The Equations
To compute the probability of reaching a goal from state s in a Markov chain:
```
P(reach goal from s) = 1 if s is goal
= sum over s' of p(s,s') * P(reach goal from s')
= 0 if no path from s reaches goal
```
This recurrence defines a system of linear equations: one equation per state. Solving this system in polynomial time (via Gaussian elimination or value iteration) gives exact probabilities. The linearity is a computational advantage: even though there are exponentially many paths, the recursive structure allows efficient solution.
For MDPs, the equations are:
```
P_max(reach goal from s) = max over actions of (sum over s' of p(action,s,s') * P_max(reach goal from s'))
```
This is a nonlinear equation system (max is nonlinear), making MDP solving harder (NP-hard in the worst case), but still polynomial for many practical systems.
Rewards and Quantitative Properties
Beyond probabilities, you can assign rewards (or costs) to transitions and states. Rewards might represent time, energy, money, or any quantitative measure. A transition might cost 0.5 seconds; a state might consume 10 milliwatts. The model checker computes expected total reward: the weighted sum of rewards on all paths, where weights are path probabilities.
For example: "the expected time to deliver a message is at most 100ms." You assign time costs to transitions, set up reward equations analogous to probability equations, and solve to compute expected time. This provides quantitative verification: not just "the system is reliable" but "the system is 99.9% reliable and recovers in an average of 5 seconds."
Practical Applications
Tools
Limitations
Probabilistic model checking faces challenges scaling to extremely large systems (millions of states require abstraction or approximation). The accuracy of results depends on model quality: if the probabilistic model doesn't match reality, verified properties may not hold. Current research focuses on: (1) abstraction techniques to reduce state space while preserving properties, (2) verification of systems with unknown probabilities (robust verification), (3) verifying economic/game-theoretic properties of systems with both probability and strategic agents.
The key insight is that randomness, properly handled, can make verification more tractable. Probabilistic model checking demonstrates that you can rigorously reason about systems with stochastic behavior, computing exact quantitative properties and providing formal assurance for probabilistic systems.
No topics depend on this one yet.