An old new notation for elementary probability theory

摘要

The Eindhoven approach to quantifier notation is 40 years old. We extend it by adding "distribution comprehensions" systematically to its repertoire; we believe the resulting notation for elementary probability theory is new. After a step-by-step explanation of the proposed notational innovations, with small examples, we give as our exemplary case study the probabilistic reasoning associated with a quantitative noninterference semantics based on Hidden Markov Models of computation. Although that example was the motivation for this work, we believe the proposal here will be more generally applicable: and so we also revisit a number of popular puzzles, to illustrate the notation's wider utility. Finally, we review the connection between comprehension notations and (category-theoretic) monads, and show how the Haskell approach to monad comprehensions applies to the distribution comprehensions we have introduced.