Stability Checking of Markov Jump Linear Systems via Probabilistic Temporal Logic (Extended Version)
Source: arXiv:2606.24880 · Published 2026-06-23 · By Lena Becker, Holger Hermanns
TL;DR
This paper addresses the stability analysis of Markov Jump Linear Systems (MJLSs), which combine linear dynamical modes switched according to an underlying Markov chain, a model essential in domains like flight control, power systems, and robotics. Classical notions of stability for MJLSs—mean stability and mean-square stability—focus on asymptotic behaviour of first and second moments across all initial states, but can be overly conservative or misleading when only subsets of initial states are practically relevant. The authors approach stability analysis through probabilistic model checking by formalizing PCTL (Probabilistic Computation Tree Logic) for MJLSs, enabling state-based temporal properties on uncountably infinite state spaces.
The main novelty is extending PCTL with operators capturing moment-based stability properties relative to specified convex sets of initial states. Although a complete decision procedure for full PCTL on MJLS remains open (due to connections with known Skolem-hard problems), the paper presents algorithms to check PCTL− (step-bounded fragment) and new stability operators by leveraging linear algebraic techniques such as spectral analysis and Jordan normal forms of propagation operators. The approach produces computable, convex satisfaction sets describing which initial states have moments converging to sets of interest. This framework refines stability verification by focusing on relevant initial conditions rather than global properties, enabling nuanced reasoning about long-run Cesàro-averaged behaviour of moments. The paper illustrates the theory with computational examples, demonstrating practical utility in MJLS stability characterization.
Key findings
- MJLS mean stability (MS) is characterized by spectral radius ρ(BJ) < 1, where BJ = (P^T ⊗ I_n) · blkdiag(A_1,...,A_m) (Thm 1).
- Mean-square stability (MSS) corresponds to ρ(TJ) < 1 where TJ = (P^T ⊗ I_{n^2}) · blkdiag(A_1 ⊗ A_1,...,A_m ⊗ A_m) (Thm 1).
- PCTL can be soundly defined over uncountable MJLS state spaces, with satisfaction sets for formulas measurable in the σ-algebra generated by cylinder sets (Thm 2).
- Exact model checking for unbounded until (full PCTL) on MJLS is open and undecidable in general due to reductions to the Skolem problem for LDSs embedded in MJLSs.
- Extended PCTL operators Ek_Π and E_Π express long-run Cesàro-averaged inclusion of the first moment in convex polytopes Π, with analogous Vk_Ξ and V_Ξ for second moments relative to polytopes Ξ.
- Algorithmic model checking of Ek_Π and E_Π reduces to linear-algebraic computations involving powers and Jordan normal form decompositions of BJ, yielding convex satisfaction sets over initial states.
- Cesàro limits exist if unstable eigenvalue components cancel out; otherwise limits do not exist and symbolic representations of divergence are incorporated.
- Example MJLS with three modes and two state variables demonstrates that parts of state space can exhibit stable moments while global stability fails.
Threat model
Not applicable; the paper focuses on formal verification of MJLS stability properties as a mathematical and computational problem rather than security against attackers. The adversary is not modeled explicitly.
Methodology — deep read
Threat model and assumptions: The paper assumes MJLSs modeled by a finite set of linear systems A_1,...,A_m with mode switching governed by a discrete-time Markov chain with transition matrix P. Adversaries are not explicitly modeled; analysis focuses on characterizing stability over initial states. The underlying assumption is knowledge of system matrices and transition probabilities.
Data: The system is mathematically specified by (P, {A_1,..., A_m}) with state space S_J = R^n × {1,...,m}. The continuous state space is uncountable; initial states are subsets thereof, typically convex polytopes for tractability.
Architecture/algorithm: Stability is characterized via spectral properties of operators BJ = (P^T ⊗ I_n) · blkdiag(A_i) for first moments and TJ for second moments. The paper extends Probabilistic Computation Tree Logic (PCTL), defining semantics for MJLSs with atomic propositions parameterized by convex polytopes over state variables. New operators Ek_Π, E_Π, Vk_Ξ, V_Ξ capture Cesàro-averaged moment inclusion in polytopes.
For model checking, PCTL− formulas are evaluated by recursively computing satisfaction sets: continuous state sets for which formulas hold, represented as convex polytopes. For Ek_Π, initial conditional moments propagate via powers of BJ; satisfaction comes from membership in convex polytopes computed via linear inequalities.
When BJ is diagonalizable, eigen-decomposition lets one express initial states as linear combinations of eigenvectors, checking convergence of Cesàro averages via eigenvalues inside the unit circle. For non-diagonalizable BJ, Jordan normal form is used, with symbolic handling of non-convergent terms.
Training/Eval regime: Not applicable as this is a theoretical formal verification approach.
Evaluation protocol: Theoretical proofs establish measurability, correctness of satisfaction sets, and connections to classical stability (Thms 2–4). Computational examples illustrate evaluation on representative MJLSs, e.g., a 3-mode, 2D state example with defined polytopes.
Reproducibility: The paper does not mention code or dataset release but provides detailed algorithms and mathematical formalisms sufficient for independent implementation. The MJLS example matrices and transition matrix are fully specified in Appendix A.1.
End-to-end example: For a given initial state (x, θ), conditional expected value vectors e_θ ⊗ x are propagated under powers of BJ. Cesàro averages of these propagate mean values over time. Membership in a convex polytope Π is checked via linear inequality systems applied to these averages. The satisfaction set Sat(Ek_Π) consists of all initial states whose Cesàro-averaged expected value lies in Π up to step k. For infinite horizon, eigenvalue analysis determines limit existence. Thus, model checking reduces to computable linear algebra and convex geometry problems on infinite continuous state spaces.
Technical innovations
- Formal extension of PCTL semantics to uncountable MJLS state spaces combining discrete modes and continuous states labeled by convex polytopes.
- Novel moment-based PCTL operators Ek_Π, E_Π, Vk_Ξ, V_Ξ capturing Cesàro-averaged convergence of first and second moments relative to convex sets of initial states.
- Linear algebraic model checking algorithms leveraging eigenvalue analysis and Jordan normal form decompositions of moment propagation operators BJ and TJ for computing satisfaction sets over infinite continuous states.
- Identification and characterization of decision problem tractability and undecidability boundaries for MJLS model checking due to reductions from classical Skolem problems in reachability.
Datasets
- Example MJLS — 3 modes × 2 continuous states — Synthetic and fully specified in the paper (Appendix A.1)
Baselines vs proposed
- Classical mean stability condition: ρ(BJ) < 1 diagnosed instability with ρ(BJ) ≈ 11.4 versus refined subset-wise stability analysis enabled by new PCTL operators.
- PCTL model checking for bounded until (PCTL−): decidable and computable using presented algorithms versus full PCTL with unbounded until: open/undecidable.
Limitations
- Complete decision procedure for full PCTL on MJLS remains open and likely undecidable due to Skolem-hard problems inherited from embedded LDS reachability issues.
- Focus on convex polytopes as atomic propositions limits expressiveness; more complex sets are intractable for membership and propagation operations.
- The approach relies heavily on spectral properties; pathological cases with non-diagonalizable BJ and eigenvalues on the unit circle require symbolic or approximate handling.
- No adversarial robustness or control synthesized; analysis is purely verification over known MJLS models without noise or input uncertainties beyond Markov switching.
- Computational scalability for high-dimensional state spaces and many modes is not evaluated; matrix operations scale poorly with dimension and number of modes.
Open questions / follow-ons
- Developing decision procedures or approximations for full PCTL model checking (including unbounded until) on MJLS despite Skolem-hardness.
- Extending logical frameworks to richer geometric or temporal properties beyond convex polytopes while retaining computational tractability.
- Incorporating inputs, controls, or adversarial disturbances into the MJLS framework with corresponding probabilistic model-checking techniques.
- Scalability improvements and numerical stability analysis for high-dimensional MJLS moment propagation using advanced linear algebra or approximation methods.
Why it matters for bot defense
The paper contributes a rigorous formal framework for verifying long-run stability properties of systems combining probabilistic switching and linear dynamics. While not directly about captcha or bot-defense, the techniques for reasoning about probabilistic temporal properties on infinite continuous-state spaces could inform analysis of automated attack models whose behaviour evolves according to stochastic hybrid dynamics. For bot-defense, this work illustrates how temporal logic can be extended to capture nuanced, subset-dependent stability or steady-state guarantees rather than global worst-case scenarios. Such refined guarantees may translate into verification of bot behaviour patterns relative to initial configurations or environmental states, enabling more targeted defenses.
Practitioners could apply the convex polytope labeling and moment-based operators as a conceptual tool to model adversarial state trajectories in CAPTCHA-solving automation, framing detection as a problem of reach-avoid or long-run stability under probabilistic switching. However, the computational complexity and lack of decision procedures for full logic highlight limitations for immediate real-time or large-scale application. Overall, the research enriches theoretical foundations for temporal reasoning about probabilistic dynamical systems—potentially relevant to future bot-defense models that integrate continuous and stochastic dynamics.
Cite
@article{arxiv2606_24880,
title={ Stability Checking of Markov Jump Linear Systems via Probabilistic Temporal Logic (Extended Version) },
author={ Lena Becker and Holger Hermanns },
journal={arXiv preprint arXiv:2606.24880},
year={ 2026 },
url={https://arxiv.org/abs/2606.24880}
}