Verifying Sampling Algorithms via Distributional Invariants

Abstract This paper presents a Hoare-like verification framework for discrete probabilistic programs that we apply to two non-trivial sampling algorithms: Lumbroso’s Fast Dice Roller and Saad et al. ’s Fast Loaded Dice Roller. These algorithms have previously resisted formal verification due to their probabilistic nature, intricate loop structure, and parametric input. Our approach complements existing proof rules based on inductive distributional invariants, enabling us to verify both total and partial correctness of the two algorithms.

Authors

• Daniel Zilken
• Kevin Batz
• Joost-Pieter Katoen RWTH Aachen University
• Tobias Winkler RWTH Aachen University, Aachen, Germany

Keywords

No keywords are indexed for this paper.