Does a Program Yield the Right Distribution?
Open Access
- 7 August 2022
- book chapter
- Published by Springer Nature
- p. 79-101
Abstract
We study discrete probabilistic programs with potentially unbounded looping behaviors over an infinite state space. We present, to the best of our knowledge,the first decidability result for the problem of determining whether such a program generates exactly a specified distribution over its outputs(provided the program terminates almost-surely). The class of distributions that can be specified in our formalism consists of standard distributions (geometric, uniform, etc.) and finite convolutions thereof. Our method relies on representing these (possibly infinite-support) distributions asprobability generating functionswhich admit effective arithmetic operations. We have automated our techniques in a tool called $$\textsc {Prodigy}$$ , which supports automatic invariance checking, compositional reasoning of nested loops, and efficient queries to the output distribution, as demonstrated by experiments.
Keywords
This publication has 52 references indexed in Scilit:
- Floyd--hoare logic for quantum programsACM Transactions on Programming Languages and Systems, 2011
- Formal certification of code-based cryptographic proofsACM SIGPLAN Notices, 2009
- Self-stabilizationACM Computing Surveys, 1993
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic AutomataSIAM Journal on Computing, 1992
- Fast randomized consensus using shared memoryJournal of Algorithms, 1990
- Particle transport and image synthesisACM SIGGRAPH Computer Graphics, 1990
- The rendering equationACM SIGGRAPH Computer Graphics, 1986
- A probabilistic PDLJournal of Computer and System Sciences, 1985
- Semantics of probabilistic programsJournal of Computer and System Sciences, 1981
- Guarded commands, nondeterminacy and formal derivation of programsCommunications of the ACM, 1975