💻 computer science

A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines

This paper establishes a behavioral theory of probabilistic algorithms by proposing four axiomatic postulates and proving that probabilistic Abstract State Machines (pASMs) can simulate any algorithm satisfying these postulates with behavioral equivalence.

Original authors: Flavio Ferrarotti, Klaus-Dieter Schewe

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Flavio Ferrarotti, Klaus-Dieter Schewe

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 describe how a computer program works, but this program isn't just following a strict, straight-line path. Instead, at every turn, it flips a coin (or rolls a die) to decide where to go next. This is a Probabilistic Algorithm. These are the "gamblers" of the computer world, used for everything from sorting lists to cracking codes, because sometimes taking a random guess is faster or smarter than checking every single possibility.

This paper asks a big question: Can we write a universal "rulebook" that describes exactly what these randomizing programs are, without tying them to any specific computer language or hardware?

The authors, Flavio Ferrarotti and Klaus-Dieter Schewe, say "Yes." They create a new theory called a Behavioural Theory for these algorithms. Here is the breakdown of their work using simple analogies.

1. The Four Golden Rules (The Postulates)

To define what counts as a "probabilistic algorithm," the authors propose four strict rules. Think of these as the laws of physics for these random programs:

Rule 1: The Fork in the Road (Random Branching Time).
In a normal program, if you are at a crossroads, there is only one path forward. In a probabilistic program, there are many paths. The rule says: "At every step, the program must have a list of possible next steps, and each path must have a specific probability attached to it (like a 30% chance to go left, 70% to go right)."
- Analogy: Imagine a choose-your-own-adventure book where, instead of you choosing the page, a magic dice roll decides which page you turn to next. The book must clearly list the odds for every page.
Rule 2: The Shape-Shifting Mirror (Abstract States).
The program's "state" (its current memory and data) can look different on the outside, but if the underlying structure is the same, the program should behave the same way.
- Analogy: Imagine two identical houses, but one is painted blue and the other red. If you swap the furniture around in a way that keeps the layout identical, the house is still the same "house" for the purpose of the story. The rule ensures that if you rename things (like changing "John" to "Jane" in the code), the probabilities of the next steps stay exactly the same.
Rule 3: The Toolbox (Background).
The program needs a standard set of tools to do its math, including a special set of tools just for handling numbers between 0 and 1 (probabilities).
- Analogy: You can't bake a cake without flour and eggs. Similarly, these algorithms need a pre-loaded "toolbox" that includes logic (True/False), lists, and a special "probability calculator" that knows how to add and multiply chances without the numbers getting too big or weird.
Rule 4: The Local View (Probabilistic Bounded Exploration).
This is the most important and tricky rule. It says the program doesn't need to look at the entire universe to decide what to do next. It only needs to look at a small, finite "snapshot" of its current state.
- The Twist: The authors introduce a concept called "Slicing." Imagine you have a complex recipe with 100 ingredients. If you decide to only use the top 10 ingredients (slicing the list), the recipe still works, but it produces fewer possible outcomes. The rule says: "If you restrict the choices (slice the list), the program just re-calculates the odds for the remaining options so they still add up to 100%." This separates the structure of the changes from the chance of the choices.

2. The Machine Model: pASMs

The authors then introduce a specific type of machine called a Probabilistic Abstract State Machine (pASM).

Think of a pASM as a robot that follows the four rules above.
It has a special command called choose ... with weight .... This is like the robot saying, "I see three doors. Door A has a weight of 1, Door B has a weight of 2, and Door C has a weight of 3. I will roll a 6-sided die to pick one, where Door C is twice as likely to be picked as Door A."

3. The Big Proof (The Capture Theorem)

The paper's main achievement is proving that these two things are actually the same thing:

The Theory: Any program that follows the four Golden Rules.
The Machine: Any pASM robot built with the choose command.

The Result: The authors prove that every probabilistic algorithm that follows their rules can be simulated step-by-step by a pASM robot.

The Analogy: Imagine you have a chaotic, random dance performed by a human (the algorithm). The authors prove that you can build a robot (the pASM) that can copy that dance perfectly, step-for-step, with the exact same random moves and probabilities. No matter how complex the human's dance is, if it follows the rules, the robot can do it too.

4. What They Don't Cover

The paper is very specific about what it leaves out:

Quantum Computers: They explicitly state their theory does not cover quantum algorithms. In quantum computing, the "state" itself is random (like a spinning coin that is both heads and tails at once). In this paper, the randomness only happens when the program chooses its next move, not in the state of the data itself.
Infinite Choices: They assume the list of possible next steps is always finite (you can't have an infinite number of doors to choose from in one step).

Summary

In short, this paper builds a solid mathematical foundation for understanding random computer programs. It defines what they are using four clear rules and proves that a specific type of machine (the pASM) is powerful enough to describe and simulate any such program perfectly. It's like writing the "Constitution" for probabilistic computing, ensuring that no matter how you write the code, if it follows the constitution, it behaves in a predictable, analyzable way.

Technical Summary: A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines

Problem Statement
While probabilistic algorithms (PAs) are ubiquitous in modern computer science—ranging from sorting and cryptography to machine learning—existing formal approaches are grounded in specific mathematical models (e.g., probabilistic Turing machines) rather than derived from first principles. There is a lack of a "behavioural theory" in the sense of Gurevich's programme: a model-independent axiomatic characterisation of PAs, coupled with a proof that a natural abstract machine model captures exactly this class via step-by-step behavioural equivalence. Such a theory is necessary to underpin rigorous specification, verification, and refinement methods for probabilistic systems.

Methodology
The authors develop a behavioural theory within the framework of Abstract State Machines (ASMs). The methodology proceeds in three stages:

Axiomatisation: The authors define the class of PAs through four specific postulates. These postulates extend the existing theory of parallel ASMs to accommodate probabilistic branching.
Machine Model Definition: They introduce Probabilistic Abstract State Machines (pASMs), an extension of standard parallel ASMs that includes a probabilistic choice rule.
Capture Theorem: They prove that the axiomatic definition and the machine model coincide. Specifically, they demonstrate that every PA satisfying the postulates can be simulated step-by-step by a behaviourally equivalent pASM, and vice versa.

Key Contributions

Axiomatic Characterisation (Four Postulates):
- Postulate 1 (Random Branching Time): Defines a PA as having a set of states where each state $S$ has a finite set of possible successor states $\tau(S)$ governed by a probability measure $d_S$ . A run is a sequence of states where each successor is drawn from this distribution.
- Postulate 2 (Abstract State): States are isomorphism-closed structures over a signature. Crucially, isomorphisms between states must preserve the probability distribution over their successors.
- Postulate 3 (Background): Extends the standard ASM background to include probability values (the set $[0, 1] \subset \mathbb{R}$ ) equipped with multiplication, truncated addition, and ordering, allowing for the expression and combination of probabilities within state transitions.
- Postulate 4 (Probabilistic Bounded Exploration): This is the conceptual core. It requires a finite set of witness terms (multiset comprehension terms) and p-witness terms (which include probability values) that determine the update sets and probability measures. A novel slicing condition is introduced: restricting the choice condition in a witness term yields a sub-algorithm with fewer runs, where the states that do occur are preserved but their probabilities are renormalised via conditionalisation. This separates the combinatorial structure of updates from the probabilistic structure of choices.
Probabilistic Abstract State Machines (pASMs):
The authors define pASMs as an extension of parallel ASMs. The key addition is the probabilistic choice rule: choose x1...xk : ψ with weight p do r. This rule selects alternatives satisfying $\psi$ based on weights $p$ , normalising them to form a valid probability distribution. The semantics define update sets and associated probability measures for each rule type (skip, assignment, conditional, parallel, and probabilistic choice).
The Capture Theorem:
The central result (Theorem 3) states that every PA satisfying the four postulates is behaviourally equivalent to a pASM.
- Proof Strategy: The proof decomposes a single step of a PA into two conceptual substeps:
  1. A parallel substep that determines, in parallel, all "characterising tuples" for possible successor states and their associated probabilities.
  2. A probabilistic substep that selects among these characterising tuples based on their probabilities.
- The authors leverage existing results from the parallel ASM thesis (specifically regarding isolating formulas and critical tuples) to construct a pASM rule for each state.
- To handle the potentially infinite number of states, they define a WP-similarity relation based on the bounded exploration witness. Since there are finitely many equivalence classes, the infinite set of state-specific rules can be collapsed into a single finite pASM rule.

Results

Plausibility: The authors prove (Theorem 2) that every pASM satisfies the four defining postulates, confirming that the machine model is a valid instance of the axiomatic class.
Capture: The main technical achievement is the proof that the axiomatic class is fully captured by the pASM model. The construction ensures that for any state, the pASM rule produces the exact same set of update sets and probability distribution as the original PA.
Applicability: The theory is shown to cover standard classes of probabilistic algorithms, including numerical, Las Vegas, Monte Carlo, and Sherwood algorithms, as well as genetic algorithms. The paper explicitly notes that Quantum algorithms are outside the scope, as their randomness resides in states rather than transitions.

Significance
The paper claims to provide the first model-independent axiomatic characterisation of probabilistic algorithms that is paired with a step-by-step behavioural equivalence proof to a concrete machine model. By establishing that pASMs capture exactly the class of PAs defined by the four postulates, the work underpins the ASM method for the specification, verification, and refinement of probabilistic systems. The introduction of the slicing condition in the bounded exploration postulate is identified as the conceptual core that allows for the separation of combinatorial update structures from probabilistic choice structures.

Scope and Limitations
The theory assumes that the set of possible successor states is always finite and that randomness is confined to transitions (choices), not the states themselves. Consequently, it does not cover quantum algorithms. The authors note that a corresponding logic for pASMs is a natural next step but is not pursued in this work.

1. The Four Golden Rules (The Postulates)

2. The Machine Model: pASMs

3. The Big Proof (The Capture Theorem)

4. What They Don't Cover

Summary

More like this