Coupling proofs are probabilistic product programs
Authors:
Open Access
- 1 January 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 161-174
Abstract
Couplings are a powerful mathematical tool for reasoning about pairs of probabilistic processes. Recent developments in formal verification identify a close connection between couplings and pRHL, a relational program logic motivated by applications to provable security, enabling formal construction of couplings from the probability theory literature. However, existing work using pRHL merely shows existence of a coupling and does not give a way to prove quantitative properties about the coupling, needed to reason about mixing and convergence of probabilistic processes. Furthermore, pRHL is inherently incomplete, and is not able to capture some advanced forms of couplings such as shift couplings. We address both problems as follows. First, we define an extension of pRHL, called x-pRHL, which explicitly constructs the coupling in a pRHL derivation in the form of a probabilistic product program that simulates two correlated runs of the original program. Existing verification tools for probabilistic programs can then be directly applied to the probabilistic product to prove quantitative properties of the coupling. Second, we equip x-pRHL with a new rule for while loops, where reasoning can freely mix synchronized and unsynchronized loop iterations. Our proof rule can capture examples of shift couplings, and the logic is relatively complete for deterministic programs. We show soundness of x-PRHL and use it to analyze two classes of examples. First, we verify rapid mixing using different tools from coupling: standard coupling, shift coupling, and path coupling, a compositional principle for combining local couplings into a global coupling. Second, we verify (approximate) equivalence between a source and an optimized program for several instances of loop optimizations from the literature.Keywords
All Related Versions
Funding Information
- NSF (TC-1065060 & TWC-1513694)
- Simons Foundation (#360368)
This publication has 53 references indexed in Scilit:
- Proof-Relevant Logical Relations for Name GenerationLecture Notes in Computer Science, 2013
- A Finite Population Model of Molecular Evolution: Theory and ComputationJournal of Computational Biology, 2012
- Formal certification of code-based cryptographic proofsACM SIGPLAN Notices, 2009
- Relational separation logicTheoretical Computer Science, 2007
- Probabilistic predicate transformersACM Transactions on Programming Languages and Systems, 1996
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graphRandom Structures & Algorithms, 1995
- Shift-couplingStochastic Processes and their Applications, 1993
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Approximating the PermanentSIAM Journal on Computing, 1989
- A probabilistic PDLJournal of Computer and System Sciences, 1985