Guaranteed Bounds on Posterior Distributions of Discrete Probabilistic Programs with Loops
summary
Automated tool Diabolo implements two provable methods: residual mass semantics (fast unrolling upper/lower bounds) and geometric bound semantics (contraction invariants over eventually geometric distributions). Paper proves soundness and convergence; geometric bounds reduce to decidable polynomial inequalities. On 43 benchmarks Diabolo finds geometric bounds for 37 (85%), typically in seconds and up to 5 minutes. Example: conditional die problem has exact expectation 1.5 and Diabolo produces a tight bound quickly and recovers tail decay ≈1/3 (found 0.34).
AI-written summary · about