A Behavioural Theory of Probabilistic Algorithms Using Probabilistic Abstract State Machines
This work establishes a foundational theoretical framework for probabilistic algorithms, relevant to computer science theorists.
The paper provides an axiomatic definition of probabilistic algorithms and introduces probabilistic Abstract State Machines (pASMs), proving that every probabilistic algorithm satisfying the postulates can be simulated step-by-step by a behaviourally equivalent pASM.
We motivate an axiomatic definition of probabilistic algorithms (PAs) by four postulates covering random branching time, abstract states, background, and random bounded exploration. Then, we introduce probabilistic Abstract State Machines (pASMs) and show that they specify PAs. Finally, we prove that every PA satisfying these postulates can be simulated step-by-step by a behaviourally equivalent pASM with the same signature and background.