Refuting Equivalence in Probabilistic Systems

This direction is merged into another direction: quantitative termination analysis. Its last version stays readable and citable here.

Version 1 of 14 papers15 conceptsfrozen 2026-10-04

When we modify a piece of code—whether to optimize its performance or refactor its structure—we need to know if we have preserved its original behavior. In deterministic programming, this is the "equivalence problem." In the world of probabilistic systems, where programs output distributions rather than single values, this problem becomes significantly more complex.

Recent research has shifted from trying to prove that two probabilistic systems are identical to a more practical goal: efficiently refuting equivalence. By finding "witnesses" or counterexamples that prove two systems are different, researchers are creating tools that can debug complex stochastic models and verify probabilistic programs.

The Algebraic Shortcut: Polynomial Identity Testing

The first hurdle in checking if two probabilistic systems are equivalent is the state-space explosion. If you represent a probabilistic automaton as a transition matrix, comparing every possible path between two models is computationally exhausting.

In On the Complexity of the Equivalence Problem for Probabilistic Automata, Andrzej S Murawski, Stefan Kiefer, Joël Ouaknine, Björn Wachter, and James Worrell 0001 demonstrate that we can bypass this by treating the equivalence problem as an algebraic one. They utilize Polynomial Identity Testing (PIT).

The intuition is elegant: if you can map the behavior of a probabilistic automaton to a high-dimensional polynomial, then two automata are equivalent if and only if their corresponding polynomials are identical. PIT allows us to check this identity by evaluating the polynomials at a few random points. If the results match, the systems are almost certainly equivalent; if they differ, we have a definitive proof of non-equivalence. This randomized approach scales far better than deterministic algorithms and provides a foundation for verifying systems with complex cost structures or pushdown stacks.

Finding Witnesses in Probabilistic Programs

While automata are useful abstractions, modern probabilistic programs often include "conditioning"—statements like observe or score that prune or weight distributions based on data. This makes the equivalence problem even harder, as the final distribution is normalized by the total weight of all valid executions.

To tackle this, Petr Novotný 0001, Dorde Zikelic, Ehsan Kafshdar Goharshady, and Krishnendu Chatterjee developed a method to refute equivalence by searching for a witness function. In their work, Refuting Equivalence in Probabilistic Programs with Conditioning, they argue that if two programs are different, there must exist some function $f$ such that the expected value of $f$ under the first program's distribution is different from the expected value under the second.

Their approach uses two key mechanisms:

  1. Weighted Restarting Transformation: They convert complex conditional programs into simpler versions that are easier to analyze mathematically.
  2. Kantorovich Distance: Instead of a simple "yes/no" answer, they calculate a lower bound on the Kantorovich distance (a metric for how much one distribution must be "moved" to match another). If this distance is greater than zero, the programs are provably non-equivalent.

Why Refutation Matters for Debugging

The shift toward refutation is driven by a need for actionable feedback. A deterministic verification tool might tell a developer that two models are "not equivalent," but without a reason why, that information is hard to use.

By focusing on PIT and witness functions, these researchers provide a "smoking gun." In the automata context, PIT can help generate counterexamples—specific input sequences where the two models diverge. In the program context, the witness function identifies exactly which statistical property (e.g., a specific moment or a range of values) differs between the two versions of the code.

By combining algebraic techniques from randomized complexity theory with analytical tools like expectation supermartingales, this research direction transforms the theoretical challenge of probabilistic equivalence into a practical toolset for ensuring the correctness of stochastic software.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_refuting_equivalence_in_probabilistic_sy_22185ca2,
  title = {Refuting Equivalence in Probabilistic Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/refuting-equivalence-in-probabilistic-systems/rdr_22185ca2d2964f5ba19c540eeaa93261},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_refuting_equivalence_in_probabilistic_sy_22185ca2_v1,
  title = {Refuting Equivalence in Probabilistic Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/refuting-equivalence-in-probabilistic-systems/rdr_22185ca2d2964f5ba19c540eeaa93261/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}