a+bi

Last night I watched the movie 21, based on the book Bringing Down the House, about the MIT blackjack team. There is a scene in the movie in which math professor Mickey Rosa poses the Monty Hall problem to a student, Ben Campbell. Predictably enough Ben is able to figure out the correct strategy and realizes that switching doors yields a 2/3s probability of winning the car (which is roughly the same chance you’ll predict the entire plot of the movie within five minutes). The problem is, he’s wrong.

At first the error is subtle. There is not enough information about the behavior of the host to determine whether the best strategy is to switch or not. The problem is not constrained enough. This is made glaringly obvious when Mickey Rosa asks “how do you know he’s not trying to play a trick on you?” If there is the possibility that the host is trying to play a trick on you, then there is the possibility that the host only allows you to switch if you have already chosen the car. In that case, switching doors would result in a 0% chance of winning the car.

Only when you constrain the problem does it make sense to switch doors. If (and only if) the host always opens a door, the door always reveals a goat, and the host always offers the player the option of switching does switching result in winning the car 2/3s of the time. Wikipedia has a good analysis of this constrained version using Bayesian products. (The short answer, the host is essentially giving you the option of switching from your initial choice of one door, to the two remaining doors and if the car is behind one of those two, you win).

Of course if the host only gives you the option to switch when you’ve chosen the car it won’t take long for people to catch on, and everyone will win all the time. It makes more sense for the host to offer a switch when you’ve selected the car with probability p, and offer a switch when you’ve selected a goat with probability q. Thus the host opens the door with probability: .

Borrowing from the analysis on the wikipedia page, we see that:

We can now use this new piecewise function to determine the probability of winning the car by switching:

So:

If we let p = 1 and q = 1 (in other words, the host always opens a door) then the probability of winning the car by switching is 2/3s, which is what we should expect.

Update:
It makes the most sense for the host to always offer the switch when you’ve chosen the car (p=1), and to offer the switch when you’ve selected the goat with probability q. By solving the inequality:

We find that we should switch when q > 1/2.

I first tried to learn OCaml after hearing about it in my Programming Languages course in college. I didn’t get very far beyond the basics at the time for a variety of reasons involving both the language itself and the resources available to me. The problems I had that did not involve the language were not unique to OCaml (except perhaps the lack of available learning material) and were not particularly exceptional. The problems I had understanding the language however were, and the worst offender was without a doubt the semi-colon.

I had a lot of trouble understanding when to use semi-colons and when I needed one of them or two. I’m pretty sure my difficulty with this was not unique either. It seems to me that very few OCaml tutorials or books go into enough detail with this…err…detail and leave it as an exercise for the reader.

Ultimately the problem comes down to the difference between statements and expressions and their relationship to OCaml. There are a few different definitions of both statements and expressions, so for the sake of this post statements are going to refer to stand-alone elements of a programming language that do not return values (that is, they are evaluated solely for their side-effects) and expressions are combinations of values, variables, functions, etc . that are evaluated and return a value.

In an imperative language like C it’s easy to see the difference between the two. An assignment is a statement, an operation is an expression. It follows from this that statements can contain expressions (such as assigning a variable to the result of an operation) and that expressions can also contain expressions (chaining together operators or using the result of a function as the argument to another).

With OCaml it’s not so easy at first. OCaml is a multi-paradigm language and one of those paradigms is imperative programming. A lot of its syntax resembles the syntax of imperative languages like C, but it does not behave like an imperative language. In OCaml there are no statements. Everything is an expression. Everything has a return value. Sometimes that return value is of type unit (as in the case of assignment to a reference). For example, and if…else block in C does not return a value. However in OCaml it does – it’s value is the last expression evaluated within the block. This is why the value of the expressions in both the if and the else block much have the same type.

This brings us back to the semi-colon. The single semi-colon is an operator that behaves similarly to the comma operator in C. It evaluates the expression on the left side of the semi-colon, then evaluates the expression on the right side of the semi-colon and returns the result of the right-side expression (effectively ignoring the value of the left-side expression). So (a;b) would evaluate to b. Since the left-side value is ignored, this is only useful when the left-side produces side-effects (the corollary being that side-effect free OCaml programs shouldn’t use the semi-colon operator).

The only book I’ve seen this in is A Concise Introduction to OCaml which I unfortunately did not come across during my first attempt at learning the language.