Proofs of randomized algorithms in Coq

Philippe Audebaud 1 Christine Paulin-Mohring 2, 3, *
* Auteur correspondant
3 PROVAL - Proof of Programs
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This 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 distributions. It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analysing general recursive functions. We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.
Type de document :
Article dans une revue
Science of Computer Programming, Elsevier, 2009, 〈10.1016/j.scico.2007.09.002〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00431771
Contributeur : Christine Paulin-Mohring <>
Soumis le : vendredi 13 novembre 2009 - 09:43:00
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:55:55

Fichier

postprint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Philippe Audebaud, Christine Paulin-Mohring. Proofs of randomized algorithms in Coq. Science of Computer Programming, Elsevier, 2009, 〈10.1016/j.scico.2007.09.002〉. 〈inria-00431771〉

Partager

Métriques

Consultations de la notice

499

Téléchargements de fichiers

366