Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Semantics of Probabilistic Programming: A Gentle Introduction
- 2 Probabilistic Programs as Measures
- 3 Application ofComputable Distributions to the Semantics of Probabilistic Programs
- 4 On Probabilistic λ-Calculi
- 5 Probabilistic Couplings from Program Logics
- 6 Expected Runtime Analyis by Program Verification
- 7 Termination Analysis of Probabilistic Programs with Martingales
- 8 Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities
- 9 The Logical Essentials of Bayesian Reasoning
- 10 Quantitative Equational Reasoning
- 11 Probabilistic Abstract Interpretation: Sound Inference and Application to Privacy
- 12 Quantitative Information Flow with Monads in Haskell
- 13 Luck: A Probabilistic Language for Testing
- 14 Tabular: Probabilistic Inference from the Spreadsheet
- 15 Programming Unreliable Hardware
8 - Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities
Published online by Cambridge University Press: 18 November 2020
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Semantics of Probabilistic Programming: A Gentle Introduction
- 2 Probabilistic Programs as Measures
- 3 Application ofComputable Distributions to the Semantics of Probabilistic Programs
- 4 On Probabilistic λ-Calculi
- 5 Probabilistic Couplings from Program Logics
- 6 Expected Runtime Analyis by Program Verification
- 7 Termination Analysis of Probabilistic Programs with Martingales
- 8 Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities
- 9 The Logical Essentials of Bayesian Reasoning
- 10 Quantitative Equational Reasoning
- 11 Probabilistic Abstract Interpretation: Sound Inference and Application to Privacy
- 12 Quantitative Information Flow with Monads in Haskell
- 13 Luck: A Probabilistic Language for Testing
- 14 Tabular: Probabilistic Inference from the Spreadsheet
- 15 Programming Unreliable Hardware
Summary
The quantitative analysis of probabilistic programs answers queries involving the expected values of program variables and expressions involving them, as well as bounds on the probabilities of assertions. In this chapter, we will present the use of concentration of measure inequalities to reason about such bounds. First, we will briefly present and motivate standard concentration of measure inequalities. Next, we survey approaches to reason about quantitative properties using concentration of measure inequalities, illustrating these on numerous motivating examples. Finally, we discuss currently open challenges in this area for future work.
- Type
- Chapter
- Information
- Foundations of Probabilistic Programming , pp. 259 - 294Publisher: Cambridge University PressPrint publication year: 2020
- Creative Commons
- This content is Open Access and distributed under the terms of the Creative Commons Attribution licence CC-BY 4.0 https://creativecommons.org/cclicenses/
- 2
- Cited by