Relational reasoning for Markov chains in a probabilistic guarded lambda calculus

DOI10.1007/978-3-319-89884-1_8MaRDI QIDQ2323974zbMATH OpenOpenAlexFDO

Authors Alejandro Aguirre, Gilles Barthe, Lars Birkedal, Aleš Bizjak, Marco Gaboardi, Deepak Garg

Publication date 13 September 2019

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1802.09787

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Combinatory logic and lambda calculus (03B40) Logic in computer science (03B70)

Abstract: We extend the simply-typed guarded $lambda$-calculus with discrete probabilities and endow it with a program logic for reasoning about relational properties of guarded probabilistic computations. This provides a framework for programming and reasoning about infinite stochastic processes like Markov chains. We demonstrate the logic sound by interpreting its judgements in the topos of trees and by using probabilistic couplings for the semantics of relational assertions over distributions on discrete types. The program logic is designed to support syntax-directed proofs in the style of relational refinement types, but retains the expressiveness of higher-order logic extended with discrete distributions, and the ability to reason relationally about expressions that have different types or syntactic structure. In addition, our proof system leverages a well-known theorem from the coupling literature to justify better proof rules for relational reasoning about probabilistic expressions. We illustrate these benefits with a broad range of examples that were beyond the scope of previous systems, including shift couplings and lump couplings between random walks.

Recommendations

• Relational reasoning via probabilistic coupling
• Step-indexed logical relations for probability
• Markov chains and Markov decision processes in Isabelle/HOL
• A lambda-calculus foundation for universal probabilistic programming
• Coupling proofs are probabilistic product programs

Cited in

(5)

• Formal reasoning about finite-state discrete-time Markov chains in HOL
• Trace relations and logical preservation for Markov automata
• Relational reasoning via probabilistic coupling
• Trace relations and logical preservation for continuous-time Markov decision processes
• scientific article; zbMATH DE number 7376040 (Why is no real title available?)

This page was built for publication: Relational reasoning for Markov chains in a probabilistic guarded lambda calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2323974)