I'm Neil Toronto of Toronto and
McCarthy, from the PLT group at
Brigham Young University. We'redeveloping languages for Bayesianmodeling and queries.

From Bayesian Notation to Pure Racket*
via Discrete Measure-Theoretic Probability in λZFC

Implementation and Application of Functional Languages
September 1-3, 2010

Neil Toronto and Jay McCarthy
PLT @ Brigham Young University, Utah, USA* Formerly PLT-Scheme

Doing Bayesian statistics is like doing
physics, but for fuzzy, uncertain, orBayesian Practice and Philosophy

random things. In physics, you mightuse a Newtonian model that gives
distance in terms of time (i.e. d=rt) andask how much time it will take to travel
given a certain distance.

• State a probabilistic model of a process; then pose a query thatruns the process backwards

22

In Bayesian statistics, you might designa model that says which words tend to

Bayesian Practice and Philosophy

appear in a document given the writer's
intent, and ask how likely it is that thewriter is trying to sell you Viagra given
the words in an email.

• State a probabilistic model of a process; then pose a query thatruns the process backwards
Document generation / Is this email spam?

22

Or you could model real-world scenes
and image capture, and then ask for a

Bayesian Practice and Philosophy

likely scene given an image---and that's
the computer vision problem in Bayesian
terms.

• State a probabilistic model of a process; then pose a query thatruns the process backwards
Document generation / Is this email spam?
Real-world scenes and image capture / Likely scene given a
photograph

22

Bayesian statisticians follow a particular
philosophy when they model the world

Bayesian Practice and Philosophy

and ask questions about it. John Tukey
probably stated it best: (read).

• State a probabilistic model of a process; then pose a query thatruns the process backwards
Document generation / Is this email spam?
Real-world scenes and image capture / Likely scene given a
photograph“An approximate answer to the right question is
worth a great deal more than a precise answer
to the wrong question.”John Wilder Tukey

22

In practice, the philosophy requires
putting off approximation for as long as

Philosophy Into Practice (1)possible. In fact, Bayesians intentionallyforget about how hard it might be to
calculate answers when they designmodels and pose queries.

• Approximations must be put off as long as possible

33

The answers end up not being
closed-form or finitely computable...

Philosophy Into Practice (1)• Approximations must be put off as long as possible
Models and queries are exact, and generally not closed-form
nor finitely computable

33

... so they usually end up compiling their
queries by hand, into programs that

Philosophy Into Practice (1)compute converging approximations.

• Approximations must be put off as long as possible
Models and queries are exact, and generally not closed-form
nor finitely computable
Compute answers as converging approximations

33

Here's a concrete example: an idealized
model of taking pictures of real-world

Philosophy Into Practice (1)scenes. The query asks for a likely
scene given an image, and then for ahigher-resolution picture of the same
scene. In other words, it enlarges
images. The model and query are short• Approximations must be put off as long as possible

and elegant.

Models and queries are exact, and generally not closed-form
nor finitely computable
Compute answers as converging approximations• Example: enlarging images
Model and query33

And this is the 600 lines ofhand-compiled, highly vectorized Python

Philosophy Into Practice (1)code that computes an approximate
answer.

• Approximations must be put off as long as possible
Models and queries are exact, and generally not closed-form
nor finitely computable
Compute answers as converging approximations• Example: enlarging images
Model and query

The answer's approximation

33

These are my friends, Andrew andDave, who write programs like that, in

Philosophy Into Practice (2)their natural habitat, under typicalconditions. They suffer these conditions
because above all, they want to answer
the right questions.

• Grads become compilers (and are just as grumpy)

44

So Bayesian philosophy motivates ourwork: we want to free Andrew and Dave

Philosophy Into Practice (2)from compiling answers to queries byhand. If we did that, they could spend a
lot more time searching the space ofmodels and experimenting.

• Grads become compilers (and are just as grumpy)• Our motivation: free (fire?) the grad students

44

The philosophy also places twoconstraints on our work: our query

Philosophy Into Practice (2)implementations can't approximate early,
and the modeling language has to be
expressive enough that it doesn't force
users to approximate early. Otherwise,
they won't be our users.

• Grads become compilers (and are just as grumpy)• Our motivation: free (fire?) the grad students• Our primary constraints
Do not approximate earlier than users would
Do not force users to approximate early
44Here's an approach that satisfies theconstraints. First, we determine what thePhilosophical Constraints

notation means, which usually means
turning examples into something formal
and compositional enough to generalize.

• Compatible approach
1. Informally determine meaning of notation

55

Then we develop an exact,
compositional semantics...

Philosophical Constraints• Compatible approach
1. Informally determine meaning of notation
2. Develop exact: “notation” → “calculations”

55

... approximate the calculations, provethat the approximation converges, andPhilosophical Constraints

then...

• Compatible approach
1. Informally determine meaning of notation
2. Develop exact
3. Approximate: “notation” → “calculations”, prove convergence55

... implement the approximating
semantics in Racket.

Philosophical Constraints• Compatible approach
1. Informally determine meaning of notation
2. Develop exact
3. Approximate: “notation” → “calculations”, prove convergence4. Implement approximating55

If you know abstract interpretation, ourapproach should seem very familiar. It

Philosophical Constraints

isn't abstract interpretation, though,because the approximations aren't
conservative.

• Compatible approach
1. Informally determine meaning of notation
2. Develop exact
3. Approximate: “notation” → “calculations”, prove convergence4. Implement approximating• Analogous to abstract interpretation
concrete/exact, abstract/approximating55

To turn notation into exact calculations,
we need a theory of probability that tells

Which Probability Theory?

us what those calculations should be.
Bayesians tend to think and calculate
using naive probability, which you
probably learned if you had to take anundergraduate statistics course. But we• Naive/undergraduate/informal probability theory

can't use naive probability.

How Bayesians tend to think about probability66

We plan to allow infinitely many randomvariables and distributions that have

Which Probability Theory?

both discrete and continuous parts.
Bayesians want those things, but naive
probability can't explain them.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities

66

The second problem arises from the factthat random variables can interact

Which Probability Theory?

non-locally, similar to how variables inlanguages with mutable state caninteract non-locally. Naive probability
theory doesn't explain thiscompositionally.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”

66Measure-theoretic probability explains
non-local interaction by having all

Which Probability Theory?

random variables interact through asingle, global object. You might call it a`store,' but its actual name is `probability
space.'• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global66

Omega is the set of all possible states of
the world being modeled. For example, if

Which Probability Theory?

your model includes flipping two coins,
all four combinations of outcomes will be
encoded somehow in Omega.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global: all possible “worlds”

66You'll also have random variables that
represent the coin flips, which decode orWhich Probability Theory?

`read' the outcomes from a world object.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global: all possible “worlds”: “getters” or “readers” for worlds

66

Sigma is critical for handling
uncountable infinities properly, and it's

Which Probability Theory?

complicated.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global: all possible “worlds”: “getters” or “readers” for worlds: measurable events (for uncountable )66

And last, P assigns probabilities. In our
preliminary work, we don't let Omega get

Which Probability Theory?

any bigger than countable, so we canforget about Sigma, and use a P thatassigns probabilities to single worlds.
We have simpler calculations that way,
but they're still structured• Naive/undergraduate/informal probability theory

measure-theoretically, and we still haveto deal with approximation.

How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global: all possible “worlds”: “getters” or “readers” for worlds: measurable events (for uncountable )(or): probabilities of events66

Measure theory fits naturally intofunctional programming, but before we

Which Probability Theory?

start defining monads, we have to deal
with the fact that measure-theoretic
calculations aren't generally computable.

• Naive/undergraduate/informal probability theory
How Bayesians tend to think about probability
But can’t properly express infinities“Spooky interaction at a distance”• Measure-theoretic probability: global: all possible “worlds”: “getters” or “readers” for worlds: measurable events (for uncountable )(or): probabilities of events

Calculations uncomputable wheninfinite66

We want to transform notation intomeasure-theoretic calculations, andLambda-ZFC

eventually approximate the calculationsin Racket. For the semantic function's
target language, then, we need acall-by-value lambda calculus forexpressing uncomputable things that are• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus

well-defined in contemporary
mathematics.

77

So we start with Alonzo Church's
invention, the lambda calculus; then we

Lambda-ZFC

add Ernst Zermelo and Abraham
Fraenkel's inventions, the well-founded
sets and set operations; and we getlambda-ZFC.

• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus

λ calculus77

So we start with Alonzo Church's
invention, the lambda calculus; then we

Lambda-ZFC

add Ernst Zermelo and Abraham
Fraenkel's inventions, the well-founded
sets and set operations; and we getlambda-ZFC.

• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus+
λ calculus

Set theory77

So we start with Alonzo Church's
invention, the lambda calculus; then we

Lambda-ZFC

add Ernst Zermelo and Abraham
Fraenkel's inventions, the well-founded
sets and set operations; and we getlambda-ZFC.

• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus+
λ calculus=
Set theory

λZFC

77

Programming in lambda-ZFC is likedoing contemporary mathematics... but

Lambda-ZFC

with first-class lambdas, so we canstructure our uncomputablemeasure-theoretic calculations as
monadic computations.

• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus+
λ calculus=
Set theory

λZFC• “Programming” is doing contemporary math, plus λx.e77

Lambda-ZFC contains all set-theoretic
functions; specifically, all conditional

Lambda-ZFC

probability distributions.

• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus+
λ calculus=
Set theory

λZFC• “Programming” is doing contemporary math, plus λx.e
• Contains all set-theoretic functions

77

To give you an idea of its relative
computational power: you can solve any

Lambda-ZFC

oracle Turing machine halting problem
by writing an interpreter in lambda-ZFC.
It might seem like too much power, butremember that we want to interpret
Bayesian notation exactly. We'll worry• Looking for language for compositional measure- theoretic
calculations; similarity to Racket a plus+
λ calculus

about computability when we do theapproximations.

=Set theory

λZFC• “Programming” is doing contemporary math, plus λx.e
• Contains all set-theoretic functions• Can solve any OTM halting problem constructively
77Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.
But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomvariables. A collection of statements is a
probabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is
distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any
world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomvariables. A collection of statements is a
probabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is
distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any
world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

Environment idiom:, RV

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomvariables. A collection of statements is a
probabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is
distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any
world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

Environment idiom:, RV

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomvariables. A collection of statements is aStatements

probabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is
distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any
world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

Environment idiom:, RV

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomStatements

State monad:variables. A collection of statements is a

, modelprobabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is(usually)

distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any
world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

Environment idiom:, RV

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomStatements

State monad:variables. A collection of statements is a

, modelprobabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is(usually)

distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any

Queries

world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Developing the whole semantics right
now would take too much time, so I'm

Interpreting Notation

going to give some examples of syntax
and talk about the structure of thecalculations.
First we have random variable

Syntactic
Category

ExamplesComputational
Structure

expressions. In the first example, X and

Semantic
Functions

Y are random variables, so they'refunctions of Omega. I've already hinted
that you could interpret this by regarding
random variables as reader monadcomputations.

Expressions

Environment idiom:, RV

But there's no reason to impose a totalorder, so we use the corresponding
applicative functor, or idiom.
Next, we have statements about randomStatements

State monad:variables. A collection of statements is a

, modelprobabilistic model. We interpret eachstatement as transforming the global
probability space. The first example, X is(usually)

distributed Geometric B, extends theprobability space. The second example
is a `condition,' which asserts that
applying the random variable X+Y to any

QueriesState monad run:or,,Pr, Dist

world must yield 4. It *restricts* theglobal probability space.
A nice way to structure thesecalculations is with the state monad, withprobability-space-valued state.
Last, we have queries. The first example
is a `conditional probability query'. It
conditions the probability space first, andthen asks for the probability that B
outputs 1/2. The second example is likethe first, but is parameterized on the88

outputs of B and X+Y. It should return afunction, or a distribution, so it's a`distribution query'.
Queries run the probability space monadcomputation in their own particular way.

Now, you might think that with all thesetypes and idioms and monads and such,

Interpreting Notation

Racket might not be the best
implementation language. But Racket's
macro system allows us to implement
the semantic functions directly. Besides,
these types are difficult to encode in

Syntactic
Category

ExamplesComputational
Structure

Semantic
Functionsmost type systems; it seems to require
either unityped random variables ordependent types. It's possible in Typed
Racket using occurrence typing, but it'sa little too much trouble.

Expressions

Environment idiom:, RV

Statements

State monad:, model(usually
Queries)State monad run:or,,Pr, Dist• Difficult to encode types in most type systems

88

The random variable expression
semantic function can turn any

Fun Facts: Semantics

lambda-ZFC expression into randomvariable. When Omega is uncountable,
we're going to have to start worrying
about something called measurability,
but we'll be able to worry about it
compositionally.

•

interprets anything constructive
Uncountable : need to prove measurability conditions

99

Next is a fortunate accident: the randomvariable semantic function turns notation

Fun Facts: Semantics

that denotes conditional distributions into`transition kernels,' whichmeasure-theoretic probability uses tobuild probability spaces. So thesemantics turns Bayesian notation into
exactly what measure-theoretic
probability requires, and that fact doesn'tchange when Omega is uncountable. It
also allows Bayesians more freedom:

interprets anything constructive•

any expression with the right type canbe a conditional distribution. I'll show an
example later.

Uncountable : need to prove measurability conditions

is a discrete•
transition kernel
Uncountablealready works:

99

There's a single point of approximationin the approximating semantics: rightFun Facts: Semantics

before a query, `finitize' restricts Omega
to a finite subset of size k. Then, as k
approaches infinity, the answer to any
query approaches the correct value.
Finitize also renormalizes P so that itsums to 1.
Approximations for uncountable Omega
are going to be tricky, but there are a lot

interprets anything constructive•of available approximations. The mostefficient ones are randomized
algorithms.

Uncountable : need to prove measurability conditions

is a discrete•
transition kernel
Uncountablealready works:• Queries approximate with
Uncountable :withfinite, stochastic

99

The implementation is almost atransliteration of the approximating

Fun Facts: Implementation

semantics, with the substitutions you
would expect; for example,• Almost a transliteration of approximating semantics, except

1010

lazy lists instead of recursively
enumerable sets, and floats andFun Facts: Implementation

rationals instead of reals.

• Almost a transliteration of approximating semantics, except
Lazy lists represent recursively enumerable sets
Floats and exact rationals represent probabilities

10
10

Just as the random variable semantic
function interprets any lambda-ZFC

Fun Facts: Implementation

expression as a random variable, theimplementation interprets any Racket
expression as a random variable. It does
this by fully expanding the expressions
first, and then transforming kernel
syntax.

• Almost a transliteration of approximating semantics, except
Lazy lists represent recursively enumerable sets
Floats and exact rationals represent probabilities• RV : kstx -> kstx interprets any Racket expression

1010And because Racket has a very
expressive macro system, we canFun Facts: Implementation

separate the monadic computations
from the queries that run them, andallow the queries access to the boundidentifiers. They can even be in separate
modules. This is important forBayesians, who usually pose many
queries for each model.

• Almost a transliteration of approximating semantics, except
Lazy lists represent recursively enumerable sets
Floats and exact rationals represent probabilities• RV : kstx -> kstx interprets any Racket expression• (define-model name [X ~ ...] ...) is hygienicallyreferred to by (with-model name (Pr ... X ...))

10
10

Let's see how the implementation doeson a good, countably infinite probability

Duelling Idiots (Paul Nahin)problem. (By `good,' by the way, I meanthat the problem includes gambling anddeath.) It comes from Paul Nahin's bookof puzzlers. Two idiots decide to duel,
but they have only one gun, asix-shooter. So they put a bullet in it andtake turns spinning the chamber andfiring at each other. What's theprobability that the player that shoots
first wins?

1111

The trick to answering the query is torecognize that how many shots it takes

Duelling Idiots (Paul Nahin)

before the gun finally goes off has ageometric distribution.

(define-model idiot-duel[winning-shot ~ (Geometric 1/6)])

11
11

The probability that player one wins is
the probability that the winning shot is

Duelling Idiots (Paul Nahin)

odd-numbered, and this approaches 2/3
as k approaches infinity. So player one
has a much better chance of winning
this duel. But suppose the idiots know
this, so they come up with a plan to even(define-model idiot-duel[winning-shot ~ (Geometric 1/6)])

the odds. Player one takes one shot,
then player two takes two shots, player
one takes three shots, and so on.
What's the probability that player one
wins?

(with-model idiot-duel(Pr (odd? winning-shot))); --> 2/3 as k --> ∞11
11

Our query now looks like this, wherep1-fires? is defined byDuelling Idiots (Paul Nahin)(define-model idiot-duel[winning-shot ~ (Geometric 1/6)])(with-model idiot-duel(Pr (odd? winning-shot))); --> 2/3 as k --> ∞(with-model idiot-duel(Pr (p1-fires? winning-shot)))11
11

Designing p1-fires? was the trickiest partof the solution. Don't stare at it too long,

Duelling Idiots (Paul Nahin)though; the point is that it exists and isn't
too hard to write.

(define-model idiot-duel[winning-shot ~ (Geometric 1/6)])(with-model idiot-duel(Pr (odd? winning-shot))); --> 2/3 as k --> ∞(with-model idiot-duel(Pr (p1-fires? winning-shot)))(define (p1-fires? n [shots 1])(cond [(<= n 0) #f][else (not (p1-fires? (- n shots)(add1 shots)))]))

11
11

Nahin spends a page of his bookdescribing his MATLAB solution, which

Duelling Idiots (Paul Nahin)uses problem transformation andsymbolic algebra hackery. He computes
the answer to 25 decimal places. Our
solution consists of just the declarative
encoding of the problem on this slide,(define-model idiot-duel[winning-shot ~ (Geometric 1/6)])

which took five minutes to write and test.
We get the same first 25 digits, but the26th is 9... so it looks like Nahin shouldhave rounded up.

(with-model idiot-duel(Pr (odd? winning-shot))); --> 2/3 as k --> ∞(with-model idiot-duel(Pr (p1-fires? winning-shot)))(define (p1-fires? n [shots 1])(cond [(<= n 0) #f][else (not (p1-fires? (- n shots)(add1 shots)))]))
Nahin (MATLAB):
Us (Racket, k=321):

0.5239191275550995247919843
0.52391912755509952479198439
11
11

But the probelm isn't Bayesian! So
suppose that player one is actually aDuelling Idiot and Half-Wit

half-wit, and proposes flipping a coin to
see whether they will spin the chamber.
If they don't spin it, the gun will go off
within six shots, and for four of thoseshots, it will be in player one's hand. But
player two is an idiot and agrees to it.

1212The model looks like this now. The
boolean-valued random variable spin?

Duelling Idiot and Half-Wit

represents the coin flip. Winning-shot's
conditional distribution is specified using
cond. A Bayesian would normally write
his own first-order function instead. Thisis much nicer, and it has a precise
meaning because we have acompositional semantics.

(define-model half-wit-duel[spin? ~ (Bernoulli 1/2)][winning-shot ~ (cond [spin? (Geometric 1/6)][else (UniformInt 1 6)])])

12
12

The probability that player one wins isn't
really a Bayesian question. But this is:

Duelling Idiot and Half-Wit

what's the probability that they spun thechamber given that player two won?

(define-model half-wit-duel[spin? ~ (Bernoulli 1/2)][winning-shot ~ (cond [spin? (Geometric 1/6)][else (UniformInt 1 6)])])(with-model half-wit-duel(Pr spin? (not (p1-fires? winning-shot))))1212

And the answer is... a little bit more than
1/2. Knowing just the outcome of theDuelling Idiot and Half-Wit

duel tells us a little bit about its causes...
and that's Bayesian.

(define-model half-wit-duel[spin? ~ (Bernoulli 1/2)][winning-shot ~ (cond [spin? (Geometric 1/6)][else (UniformInt 1 6)])])(with-model half-wit-duel(Pr spin? (not (p1-fires? winning-shot))))Answer: about 0.588 (compare (Pr spin?) = 0.5)1212

Because we have a semantics, we candefine a notion of observational

Observational Equivalence• Model equivalence:
between andmeans no query

equivalence, which lets us determine
when we can perform optimizations...

can distinguish13
13

... like variable collapse, which is likeconstant folding, and condition

Observational Equivalence

propagation, which is like constraint
propagation. Both of them can yieldorder-of-magnitude speedups.

• Model equivalence:
between andmeans no querycan distinguish• Justifies measure-theoretic optimizations
Variable collapse (constant folding for rvs)

Propagating conditions (like constraint propagation)

1313And both of them can only be provencorrect in the exact semantics.

Observational Equivalence• Model equivalence:
between andmeans no querycan distinguish• Justifies measure-theoretic optimizations
Variable collapse (constant folding for rvs)

Propagating conditions (like constraint propagation)• Justifiable only in the exact semantics

13
13

Suppose that, at the 29th approximation,a certain query returned 0.7. Then, after

Observational Equivalence• Model equivalence:
between andmeans no queryan `optimization,' the same query
returned 0.2. It's obviously wrong.

can distinguish• Justifies measure-theoretic optimizations
Variable collapse (constant folding for rvs)

Propagating conditions (like constraint propagation)• Justifiable only in the exact semantics
Suppose for

,

but

13
13

But then, what if we find that at the400th approximation, the original query

Observational Equivalence

returns 0.19? Maybe the optimization
preserves meaning and speeds
convergence.

• Model equivalence:
between andmeans no querycan distinguish• Justifies measure-theoretic optimizations
Variable collapse (constant folding for rvs)

Propagating conditions (like constraint propagation)• Justifiable only in the exact semantics
Suppose for
But what if, for

,

but
,

?
13
13

In fact, that's what mostmeasure-theoretic optimizations do.

Observational Equivalence

Attempting to reason about them in theapproximating semantics, or heaven
forbid the implementation, would be a
total mess, and we'd end up• Model equivalence:
between andmeans no queryreconstructing the exact semantics

can distinguishanyway.
Having an exact, compositionalsemantics sets our work apart fromother work on Bayesian modelinglanguages, and in short, it's an• Justifies measure-theoretic optimizations

awesome thing to have.

Variable collapse (constant folding for rvs)

Propagating conditions (like constraint propagation)• Justifiable only in the exact semantics
Suppose for
But what if, for

,

but
,

?
13
13