💻 computer science

Stability Checking of Markov Jump Linear Systems via Probabilistic Temporal Logic (Extended Version)

This paper proposes a model checking framework for Markov jump linear systems that utilizes probabilistic computation tree logic (PCTL) to formally specify and verify moment-based stability properties relative to specific sets of initial conditions, offering a less conservative alternative to classical asymptotic stability analysis.

Original authors: Lena Becker, Holger Hermanns

Published 2026-06-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lena Becker, Holger Hermanns

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the weather for a city, but the city has a strange rule: every hour, the laws of physics governing the wind and rain might suddenly change. One hour, the wind blows gently; the next, it might howl like a hurricane. These changes happen randomly, like flipping a coin. This is what the paper calls a Markov Jump Linear System (MJLS). It's a mathematical model for things that move and change, but where the rules of the game switch randomly.

The Old Way: "Is the Whole City Safe?"

Traditionally, scientists check if such a system is "stable." Think of stability as asking: "If I drop a ball anywhere in this city, will it eventually stop rolling and settle down?"

The old methods looked at the entire city at once. They asked, "Does every single possible starting point lead to a safe stop?"

The Problem: This approach is often too strict. Imagine a tiny, unreachable corner of the city (like a spot inside a solid rock) where a ball would roll forever. Because of that one impossible spot, the old method would say, "The whole city is unstable!" and throw away the system, even though 99.9% of the city is perfectly safe and the ball stops rolling everywhere else.

The New Idea: "Is This Neighborhood Safe?"

The authors of this paper wanted a smarter way to check. Instead of asking about the whole city, they asked: "If I start in this specific neighborhood, will the ball stop?"

They did this by borrowing a language called PCTL (Probabilistic Computation Tree Logic). Think of PCTL as a very precise way to write instructions or questions about the future.

The Innovation: They taught this language to talk about moments. In math, the "first moment" is like the average position of the ball, and the "second moment" is like how much the ball wobbles or spreads out.
The New Question: They created new symbols in their language that say things like: "Does the average position of the ball, starting from this specific spot, eventually settle into a calm pattern?"

How They Solved It: The "Magic Calculator"

To answer these new questions, the authors had to build a special kind of calculator.

The Map: They realized that even though the ball moves in a continuous space (like a smooth floor), the random switching of rules creates a pattern that can be described using big grids of numbers (matrices).
The Trick: They used advanced algebra (linear algebra) to predict the long-term average behavior. Instead of simulating the ball rolling step-by-step forever, they looked at the "fingerprint" of the system (its eigenvalues).
The Result: They created an algorithm that can take a specific starting point (or a specific shape of starting points, like a safe zone) and tell you: "Yes, if you start here, the system will eventually calm down," or "No, if you start here, it will go wild."

The Catch: The "Unsolvable" Puzzle

The paper admits there is a limit to their magic.

If you ask a simple question like "Will the ball reach this specific point?" the answer is easy.
But if you ask a complex question about the ball reaching a specific shape or area after an infinite amount of time, the math hits a wall. The authors point out that this specific type of question is linked to a famous, unsolved math problem called the Skolem problem.
Translation: They can check if the system stabilizes on average (which is what they care about), but they cannot build a perfect, automatic machine that answers every possible question about the system's future. Some questions are just too hard for any computer to solve right now.

Summary

In short, this paper introduces a new way to check if complex, randomly switching systems are safe. Instead of failing the whole system because of one weird, impossible starting point, their new method lets you zoom in and check specific, realistic starting points. They built a mathematical tool to do this using averages and algebra, but they also warned that some very complex questions about the future of these systems remain unsolved mysteries in mathematics.

Technical Summary: Stability Checking of Markov Jump Linear Systems via Probabilistic Temporal Logic

Problem Statement
Markov Jump Linear Systems (MJLSs) model dynamical phenomena subject to random switching among multiple linear modes, governed by an underlying discrete-time Markov chain. Classical stability analysis for MJLSs relies on global notions such as mean stability (MS) and mean-square stability (MSS), which characterize the asymptotic behavior of the first and second moments of the system state. These classical approaches typically require stability guarantees for all initial conditions. The authors argue that this global perspective can be overly conservative or misleading in practice. Specifically, instability might arise only for a negligible subset of initial states (e.g., physically unreachable configurations), while the system remains stable for all practically relevant states. Conversely, a system might converge for all initial states but to different limit values, failing the strict definition of stability (which requires convergence to a common value, typically the origin) despite exhibiting desirable convergence behavior.

The paper addresses the gap in the literature regarding the verification of stability properties relative to specific, prescribed sets of initial states. This is framed as a model-checking problem, where the goal is to determine if specific temporal properties regarding moment convergence hold for a given subset of the state space.

Methodology
The authors approach the problem by embedding stability analysis into the framework of Probabilistic Computation Tree Logic (PCTL).

Formalization of PCTL on MJLSs:
The paper first formalizes standard PCTL for MJLSs. The state space is defined as $S_J = \mathbb{R}^n \times \{1, \dots, m\}$ , combining continuous state variables with discrete Markov modes. Atomic propositions are defined over convex polytopes for continuous states and specific modes for discrete states. The satisfaction relation is defined over infinite paths, with probabilities calculated over cylinder sets derived from the underlying Markov chain.
Limitations of General PCTL Model Checking:
The authors analyze the decidability of the full PCTL logic (including the unbounded "until" operator) on MJLSs. They establish that MJLSs can be embedded into General Markov Processes (GMPs). By leveraging the fact that Linear Dynamical Systems (LDSs) are a deterministic special case of MJLSs, they demonstrate that the reachability problem for PCTL on MJLSs inherits the undecidability results associated with the Skolem problem. Specifically, determining reachability for sets of dimension four or higher in LDSs is an open problem, implying that the general model-checking problem for PCTL on MJLSs (beyond the step-bounded fragment $PCTL^-$ ) is also open and likely undecidable.
Extension with Stability Operators:
To overcome the limitations of global stability definitions and the undecidability of general reachability, the authors extend PCTL with new atomic propositions that capture moment-based stability properties relative to specific initial states.
- Operators: They introduce step-bounded ( $E^k_\Pi, V^k_\Xi$ $E_{Π}^{k}, V_{Ξ}^{k}$ ) and step-unbounded ( $E_\Pi, V_\Xi$ $E_{Π}, V_{Ξ}$ ) operators.
  - $E_\Pi$ and $V_\Xi$ check if the Cesàro limit (time-averaged limit) of the first moment (expected value) and second moment (uncentered variance), respectively, lies within a specified convex polytope ( $\Pi$ or $\Xi$ ).
  - These operators utilize the Cesàro limit rather than pointwise limits to handle oscillatory behaviors that may not converge pointwise but have a well-defined average.
- Algebraic Approach: The verification of these new operators relies on linear-algebraic techniques rather than general reachability analysis.
  - The evolution of conditional moments is governed by linear operators: $B_J$ for the first moment and $T_J$ for the second moment.
  - The satisfaction set for the unbounded operators is computed by analyzing the spectral properties (eigenvalues and eigenvectors/Jordan blocks) of these operators.
  - For diagonalizable operators, the limit is determined by the projection of the initial state onto the eigenspace corresponding to eigenvalues on the unit circle.
  - For non-diagonalizable operators, the authors employ the Jordan normal form to compute limits symbolically, handling cases where terms diverge or cancel out.

Key Contributions and Results

Logical Framework: The paper provides a formal semantics for PCTL on MJLSs and extends it with operators to specify stability relative to specific initial state sets.
Algorithmic Verification:
- A decision procedure is provided for the step-bounded fragment ( $PCTL^-$ ) and the new stability operators ( $E_\Pi, V_\Xi$ , etc.).
- The algorithms for the stability operators reduce the verification problem to solving linear equation systems and checking membership in convex polytopes. This ensures that the resulting satisfaction sets are representable (as convex sets or unions thereof) and computationally tractable, provided the eigenvalues can be computed.
- The authors demonstrate that while the general PCTL model-checking problem is open due to connections with the Skolem problem, the specific fragment dealing with moment stability is decidable via linear algebra.
Handling Oscillations: By using Cesàro limits, the proposed operators capture a notion of convergence that remains well-defined even when moment sequences oscillate, contrasting with classical definitions that might fail in such cases.
Case Studies: The paper includes computational examples (e.g., a 3-mode MJLS with 2 state variables) visualizing satisfaction sets for formulas like $P_{\ge 0.3}(\Lambda \mathcal{U}_{\le 5} E_\Pi)$ , demonstrating the ability to identify regions of the state space that satisfy complex stability and reachability requirements.

Significance and Claims
The authors claim that their work enables a "refined" view of MJLS stability that was previously impossible to express or decide. By moving away from global guarantees, the framework allows analysts to:

Identify stability properties for specific, practically relevant subsets of initial conditions, avoiding the conservatism of global analysis.
Combine stability properties with classical reachability or branching-time objectives within a single logical formula.
Utilize probabilistic model checking as a natural framework for state-dependent stability analysis.

The paper remains modest regarding the scope of its decidability results. It explicitly acknowledges that the general model-checking problem for step-unbounded PCTL properties on MJLSs remains open and is closely tied to longstanding open problems in mathematics (Skolem problem). Furthermore, it notes practical limitations in implementation: exact computation of eigenvalues for matrices of dimension greater than 4 is generally impossible due to the Abel-Ruffini theorem, meaning that for larger systems, the analysis relies on numerical approximations rather than exact symbolic solutions. The paper concludes that while the specific logic enriched with stability operators (excluding the general unbounded until) is decidable via linear-algebraic techniques, the converse nesting (embedding PCTL formulas inside stability operators) is not supported in the current framework, and its model-checking problem would also be open.