Randomized algorithms are widely used either for finding efficiently approximated solutions to complex problems, for instance primality testing, or for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of the programs. Providing tools for the mechanization of reasoning is consequently an important issue. Our paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distribution (Giry, 1982; Ramsey and Pfeffer, 2002) . It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory, but it only uses functional and algebraic properties of the unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy certain properties. Our approach covers only discrete distributions but gives rules for analysing general recursive functions. We apply this theory for formally proving a program implementing a Bernoulli distribution from a coin flip and the (partial) termination of various programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant (The Coq Development Team, 2006).
Other approaches based on interactive theorem provers include the work of Audebaud and Paulin-Mohring REF , who axiomatize (discrete) probability theory and verify some examples of randomized algorithms using the Coq proof assistant.
Proofs of randomized algorithms in Coq
Sci. Comput. Program.
Computer Science