Polynomial Invariants for Probabilistic Transition Systems with Unbounded Support

Computer Science > Logic in Computer Science
[Submitted on 2 Sep 2026]
Title:Polynomial Invariants for Probabilistic Transition Systems with Unbounded Support
View PDF HTML (experimental)Abstract:We study the synthesis of polynomial invariants for probabilistic transition systems (PTS) based on martingale theory. We present tractable methods to verify that such polynomials are indeed invariants, in the sense that their expected value upon termination is the same as their value at the start of the computation. We do this by applying the Optional Stopping Theorem (OST) in the form of a specific precondition. This precondition requires the existence of an integrable dominating function for the martingale expression, which implies uniform integrability; we refer to this condition as dui. For linear PTS we simplify the dui property to proving finiteness of the expected value of an expression depending on the update matrix, the degree of the martingale expression, and the stopping time. Specifically, if all random samples have finite moments and we can verify a moment bound on the runtime of a linear loop, then we can automatically synthesise polynomial loop invariants that satisfy the OST. Notably, dui allows for the sampled distributions to have unbounded support, which is a novel contribution to the field.
References & Citations
Loading...
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Facts Only

* The study concerns the synthesis of polynomial invariants for probabilistic transition systems (PTS).
* Methods are based on martingale theory.
* Verification that polynomials are invariants involves checking if their expected value at termination matches the starting value.
* This check is done by applying the Optional Stopping Theorem (OST) with a specific precondition.
* The precondition requires the existence of an integrable dominating function for the martingale expression, termed dui.
* For linear PTS, dui simplifies to proving the finiteness of the expected value concerning the update matrix, the degree of the martingale expression, and the stopping time.
* If random samples have finite moments and a moment bound on the runtime of a linear loop is verified, polynomial loop invariants satisfying the OST can be synthesized automatically for linear systems.
* dui allows sampled distributions to have unbounded support.

Executive Summary

The research investigates synthesizing polynomial invariants for probabilistic transition systems (PTS) using martingale theory. The goal is to establish tractable methods to verify that these polynomials are true invariants, meaning their expected value upon termination equals their initial value. This verification is achieved by applying the Optional Stopping Theorem (OST) under a specific precondition requiring the existence of an integrable dominating function, referred to as dui. For linear PTS, the dui condition simplifies to demonstrating the finiteness of the expected value involving the update matrix, the degree of the martingale expression, and the stopping time. A key finding is that if random samples have finite moments and moment bounds on loop runtime can be verified for a linear loop, polynomial loop invariants satisfying the OST can be synthesized automatically. Furthermore, the dui condition permits sampled distributions to possess unbounded support, which is presented as a novel contribution to the field.

Full Take

The work connects advanced stochastic processes (martingales) with algebraic structures (polynomial invariants) within the framework of probabilistic system analysis. The introduction of the 'dui' condition as a bridge between martingale theory and verifiable system properties is significant because it shifts the focus from theoretical existence to computational verifiability, especially when dealing with potentially complex or unbounded probability spaces. The implication that dui permits unbounded support for sampled distributions challenges traditional assumptions in many areas of applied probability where finite bounds are often imposed. The novelty lies not just in applying OST but in defining a specific moment-based constraint (dui) that directly translates into algorithmic synthesis capabilities for invariants, suggesting a pathway to formally characterizing the long-term behavior and structural stability of stochastic systems with greater freedom regarding input distributions. Further inquiry should focus on the complexity overhead introduced by verifying the dui condition across different classes of PTS, and how these polynomial methods scale when moving beyond linear systems to non-linear transition dynamics.

Sentinel — Human

Confidence

The text exhibits the high technical density and precise structure expected of peer-reviewed academic work, indicating it is likely human-authored within the field.

Signals Detected

Moderate sentence length variance; academic density suggests deliberate construction.

Highly focused and technically precise, characteristic of specialized academic writing.

The flow follows a clear logical path (Problem -> Theory -> Condition -> Novelty), typical of research abstracts.

Claims are highly technical and rely on established mathematical concepts; no obvious markers of LLM confabulation detected.

Human Indicators

The use of domain-specific terminology (PTS, martingale theory, Optional Stopping Theorem, dui) integrated into a specific research problem suggests authentic expertise.

The structure follows standard academic presentation for a mathematical/CS paper.