Probability Monad in Swift

I read about the probability monad in The Frequentist Approach to Probability a couple of years ago and thought it was pretty neat. I decided to make one in Swift, as an exercise in learning the language, after having done the same in Clojure and Java 8.

If you don’t know what a monad is, don’t worry, it’s not important for this post. Just know that it lets you do neat stuff with probability distributions, programmatically speaking. Ok… on to the code.

Protocols for Probabilities

I initially tried to do this with protocols. I had two. One that let us randomly sample values from a probability distribution

and another one that allowed for parameterization, like for the Poisson distribution.

You may have noticed that there’s no protocol that allows you to map one distribution into another, which is what would make this into a monad. That’s because I had not yet figured out how to do it with structs or with classes. It’s easy to map one set of values drawn from a distribution into another set of values according to a function. But I really needed to create a new struct with a specific get() function. And then I remembered that functions were first class values in Swift!

Turns out you don’t need protocols or classes for this at all. You can do it all with a pretty simple struct!

Probability Distributions via Closures

With a single generic struct, we have everything we need for the probability monad. To convert one distribution into another, we need only pass in a function that maps elements of one distribution into elements of the other.

Let’s see what we can do if we start from the uniform distribution.

For starters, we can easily generate the true-false distribution by mapping the Uniform distribution with a function that generates the booleans from a double. From there, it’s straightforward to transform the true-false distribution into the Bernoulli distribution

By passing the appropriate transformation function or closure to the map function, one type of distribution can be converted into another.

BTW, to use the random number generators you’ll need to import Foundation. If you’re on a Mac, you could also import GameplayKit’s GKRandomSource. Or you can always use something from C.

Composing Distributions

If you want to compose distributions, the our struct needs an appropriate function: flatMap.

A standard example is the distribution you get from combining a pair of six-sided dice. We can start with a single die:

Next, we can use the flatMap function to compose the distributions of a pair of six-sided dice by passing in a function that provides the behavior we need.

Now that you’ve seen all the pieces, here’s the final form of the probability distribution struct:

Computing Statistics for a Distribution

You may have noticed a few functions for summary statistics (mean, etc) and probability computation. The most important function is prob, which lets you use predicates to ask questions of the distribution. There are a few basic examples of what you can do below.

If I can figure how to properly implement the given() function I’ll add that in a future post. I also want to be able to handle more interesting distributions, like that seen in a probabilistic graphical model.

All the code is on Github.

Symmetry

Symmetry is one of the most powerful ideas in physics. Emmy Noether, the most important woman in the history of mathematics, determined that every continuous symmetry in a physical system results in a conserved quantity. This is called Noether’s Theorem. Every beginning physics student learns that any system’s total energy, momentum, and angular momentum are conserved. Noether’s Theorem explains why. Each law comes from one of our universe’s symmetries. Let’s take a look.

vira3

Conservation of Energy

If each conservation law stems from an underlying symmetry, what causes energy conservation? First of all, what does it mean for energy to be conserved? Suppose we take a box and count the total energy inside. If come back later and count again, we should get the same answer, provided nothing entered or left the box. So, for an isolated system, whether we turn the clock forward or backward, we should see the same energy. That’s energy conservation. If you pick any system and study its “equations of motions”, which are the equations which govern its behavior, you’ll find that the equations look the same at any time t0 and at time t0 + t1. Or in other words, the laws of physics are symmetric in time. Energy is conserved because the laws of physics (or the universe) are homogeneous in time, i.e., whether we turn the clock forward or backward the equations are the same.

Conservation of Momentum

Similar to the discussion for energy, if we compute the total momentum for the box now and the total momentum at a later time, then the total momentum should be unchanged. If we look at the laws of physics, like we did for energy, we’ll find that they don’t explicitly depend on position. The laws of physics are the same no matter where you are in the universe. If we are at position x0 and then shift to position x0 + x1, the laws of physics are unchanged. This symmetry is called the homogeneity of space and it causes momentum conservation.

Conservation of Angular Momentum

You’re probably catching on now. When the laws of physics don’t explicitly depend on a variable like time or space, we get a conservation law. So what about rotational symmetry? If we rotate a system through an angle, the equations of physics are the same. So, there is no preferred direction in space. This symmetry is called the isotropy of space and it causes the conservation of angular momentum.

The Underlying Mathematics

If you look at classical (or quantum) mechanics, you’ll encounter Noether’s theorem and see that there’s a conservation law between every pair of canonically conjugate quantities. Each member of a pair will be an “observable” quantity that we could measure. One member of the pair is what we usually think of as an independent variable, like time, and can produce transformations in the system (like translation in space or time). The other will be a physical quantity like energy. So, at this level of understanding, time and energy are canonically conjugate. The same is true for space and momentum and for angular position and angular momentum.

Summary

Every conservation law stems from some underlying continuous symmetry. Energy conservation is due to the homogeneity of time, momentum conservation to the homogeneity of space, and the isotropy of space produces angular momentum conservation.

To learn more about this, you can take a look at any of the following resources, listed in order of increasing sophistication: