Verifying Sampling Algorithms via Distributional Invariants

Abstract

This paper presents a Hoare-like veri cation 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 veri cation 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.