Abstract
This AFP entry defines a probabilistic while operator based on
sub-probability mass functions and formalises zero-one laws and variant
rules for probabilistic loop termination. As applications, we
implement probabilistic algorithms for the Bernoulli, geometric and
arbitrary uniform distributions that only use fair coin flips, and
prove them correct and terminating with probability 1.
License
History
- February 2, 2018
- Added a proof that probabilistic conditioning can be implemented by repeated sampling.
(revision 305867c4e911)
Topics
- Computer science/Functional programming
- Mathematics/Probability theory
- Computer science/Algorithms/Randomized