Verifying Sampling Algorithms via Distributional Invariants
Abstract
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.
Fields of Study & Subjects
Machine Learning and Algorithms
Anomaly Detection Techniques and Applications
Machine Learning and Data Classification
Publication details
- Journal / source
- Lecture notes in computer science
- Publisher
- Springer Nature Switzerland
- Pages
- 259–278
- Publication date
- 1 January 2026
- Language
- EN