Probability Programming

Yesterday a very interesting speaker, Eric Hehner, gave a talk at the graduate seminar:

TITLE

A Probability Perspective

ABSTRACT

This talk could be called “probability meets programming”. It draws together four perspectives that contribute to a new understanding of probability and solving problems involving probability. The first is the Subjective Bayesian perspective that probability is affected by ones knowledge, and that it is updated as ones knowledge changes. The problem of assigning prior probabilities is mitigated by the Information Theory perspective, which equates probability with information. The main point of the talk is that the formal perspective (formalize, calculate, unformalize) is beneficial to solving probability problems. And finally, the programmer’s perspective provides us with a suitable formalism.

I found the talk extremely fascinating. He first compared measures of probability, entropy, and information, demonstrating that they were (in a sense) substitutable concepts (analogous with Energy and Mass, or Energy and Temperature).

b bits	=	2b states	=	2-b chance
log(s) bits	=	s states	=	1/s states
-log(c) bits	=	1/c states	=	c chance

He also waxed poetical about how we are often fooled about probabilities, so it pays considerably to mechanize our calculations regarding those probabilities. It helps even further if we have a formal language into which we can directly translate our real-life word problems, so that we don’t accidentally setup and then solve the wrong problem. That is, we can then move on from debating about interpretations of the problem, and into actual calculation.

• If I have two children and one of them is a girl, what is the probability the other is also a girl? (ans: 1/3)
• If I have two children and the older one is a girl, what is the probability that the younger is also a girl? (ans: 1/2)

He also talked quite a bit on the Bayesian approach to probability, and why it is much nicer than the frequentist approach, because it assumes much less about the world. There is no need for a prior, and your measured probabilities are updated naturally as your knowledge of the world changes.

From this he moved on to providing a proto-language approach to how one would setup and solve these sorts of problems. He co-opted existing computer language constructs to do this. First we notice that in statements like

IF cond THEN this ELSE that ENDIF

the cond is a boolean value. But there’s a priori no reason why we are prevented from interpreting it as a probability, a real value in the range [0,1].

IF 1/2 THEN print(“heads”) ELSE print(“tails”) ENDIF

He quite nicely demonstrated a calculus that gives you the ability to compute the result of such random decision trees. So, for example if you were faced with the Two Envelopes Problem how you could compute the value of a strategy expressed in his probability language.

I really liked the talk because of the way in which it drew upon existing fields and showed a very curious intersection of them. After the talk I asked if he could use this language to calculate an optimum strategy (he said no, he hadn’t done that, but it would be a good area of research) and if he had considered the addition of a switch-case statement (he had, but though he didn’t know how it would look in the language, he quite liked the idea of adding it).

The research paper, a Probability Perspective underlying his talk is available, as is his book, A Practicle Theory of Programming. He also mentioned that he has a grad student that has applied this probability programming to proof of quantum algorithms with much success, and that he’s yet to find a student to implement (write a compiler/interpreter for the language)