How 21 got the Monty Hall problem wrong

May 7th, 2009 by Niki

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: p \times \frac13 + q \times \frac23.

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

P(H_{ij}|C_k) = \begin{cases}0 \text{ if } i=j\\0 \text{ if } j=k\\\displaystyle\frac{p}{2} \text{ if } i=k\\q \text{ if } i \neq k \text{ and } j \neq k\end{cases}

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

P(C_3|H_{12}) = \displaystyle\frac{P(H_{12}|C_3)P(C_3)}{P(H_{12})}\\P(H_{12}|C_3)P(C_3) = q \times \frac13\\P(H_{12}) = P(H_{12} \cap C_1) + P(H_{12} \cap C_2) + P(H_{12} \cap C_3)\\ = P(H_{12}|C_1)P(C_1) + P(H_{12}|C_1)P(C_2) + P(H_{12}|C_1)P(C_3)\\ = 0 \times \frac13 + \frac{p}{2} \times \frac13 + q \times \frac13 = \displaystyle\frac{p + 2q}{6}

So:

P(C_3|H_{12}) = \displaystyle\frac{2q}{p+2q}

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:

\displaystyle\frac{2q}{1+2q} > \frac12

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

On statements and expressions in OCaml

May 1st, 2009 by Niki

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.

The pocketknife paradox

April 18th, 2009 by Niki

A few months ago I was having a discussion with a few friends of mine and the subject of social awkwardness as it applies to telephone conversations arose. I am in many ways a stereotypical nerd and I am no stranger to social awkwardness. I have grown out of the worst of it, but telephone calls are still difficult for me.

One of my friends could not believe that anyone could have trouble making a phone call or talking to someone on the phone. At the time he worked in tech support and answered phones for a living. It came very naturally to him and he had trouble believing that he had some special skill that made him good at his job.

Eventually I came to realize how his attitude mirrored my own, albeit about entirely different subjects. I often have trouble understanding how some people are unable to understand basic logic or simple math. It’s frustrating to encounter an otherwise intelligent person who barely understand a concept as simple as say, division. There are certain skills that I possess that are “innate” (I don’t know if it’s genetic or environmental but it doesn’t matter either way) and that I take for granted. These skills are so simple for me that I have to fight the temptation to write off as stupid people who have difficulty with the same tasks.

I call this the “pocketknife paradox” – I have a lock-back pocketknife that I typically carry on me. I have observed that somewhere around half (and I believe it to be greater than half) of the people that I have lent it to are unable to figure out how to close it. The mechanism to lock the knife in the open position is so intuitive to me that I forget that many people don’t observe things the same way I do.

New project: data structures

April 17th, 2009 by Niki

Most of the code that I’ve written in the past few years has been closed-source, proprietary code for my employer. As such I have very little publicly available code to show other people. A few months ago I decided to start working on that by implementing some of the more interesting data structures that I’ve read about. The ultimate goal was to create a Fibonacci heap, which I’ve been meaning to do since I completed the final project for my algorithms class in college. We had to implement Dijkstra’s algorithm on the NYC subway system and a Fibonacci heap can lower the asymptotic bound on the running time.

I started with a Red-black tree as that is a pretty classic and oft-used data structure. Perhaps this endeavor was a little pointless as Red-black trees are usually the data structure used to implement the STL map. In a sense this was both the most useful (because of the frequency with which I use the map container) and the least useful (because it’s already available).

I then implemented two different heaps: a binomial heap and a Fibonacci heap. A binomial heap improves the running time of merging two heaps together (and uses this fact to implement most other operations using the merge) and a Fibonacci heap improves the running time of the decrease key operation – an operation that is frequently used in Dijkstra’s algorithm as well as many other graph algorithms.

The code isn’t as nice as I’d like (there is some debugging code left in, for example) but it was a good exercise and greatly took advantage of template meta-programming in C++.

The project page is here.

12am – a video game developed in 48 hours

March 9th, 2009 by Niki

I participated in the Global Game Jam with my co-worker Chris a little over a month ago. It was held at the Columbia Teacher’s College. Shortly after we arrived there was a brief introduction to the insanity to come, including a video from the guys that created World of Goo, meant to inspire us (and offering up some sound advice on how to create a game in such a short period of time). We were then given a list of design requirements. The theme of the game was “As long as we have each other, we will never run out of problems.” The game had to be completely playable in five minutes. It also needed to include one of the following adjectives: pointed, persistent or illusory.

After the orientation there was a mingling period where we were able to meet the other participants and form groups. To my relief there was a fair balance of students/enthusiasts and professionals, as well as a healthy mix of programmers, artists and designers. I was afraid that this event would attract too few programmers to be viable but my fears were completely unjustified.

Chris and I decided to stick together, and we eventually found a group of six people to work with, with a seventh on the way. Most were professionals in some capacity although aside from me and Chris, only one other worked in the video game industry. However we quickly realized that seven people was too many, as creative differences and [programming] language barriers were getting in the way. Eventually we split into two groups – our group consisting of four members and another group with three. Our group then split further, with one team member amicably leaving to join another group over creative differences. When we finally resolved the team formation issues there were three of us: me, Chris and Stefan – a Full Sail graduate.

We began designing the game. While we all had similar and complementary ideas we had a lot of trouble coming up with a cohesive design. Eventually we had a rough idea of some basic elements (using time travel to meet the five minute requirement, make a 2D game) and decided to start implementing the basics. I set up a Subversion repository and Stefan and I started coding while Chris dealt with the assets. We used C++ with SDL as our graphics/sound/input library. We ended up using two different compilers (Stefan used Visual C++ while I used gcc) which surprising did not cause any major problems. I worked on the time travel mechanics while Stefan worked on collision detection.

Once we had a code and asset base we went back to design. We ended up dropping the time travel mechanic and using elements of point-and-click adventure games (only with the pointing and clicking – we used the keyboard for input). We created almost a parody of adventure games – showing the consequences of entering someone’s house and looting it (a device all too common in the genre). In the end we had a dark, bleak story of a man who had lost touch with reality and with the one he loved.

With the design finally complete and only a few hours left we got back to implementing the game. By the time the deadline struck we had a fairly presentable (although very incomplete) game. We were awarded “most innovative UI.”

You can download the game and all the source code here, the official game jam website for our game is here.

Winx Club: Mission Enchantix

February 2nd, 2009 by Niki

The last game that I worked on was Winx Club: Mission Enchantix which was released in the US at the end of November. My boss just alerted me to a rather nice review of the game found on Game Vortex.

While there were a lot of problems during the development of the game (mostly dealing with the licensor-publisher-developer relationship and communication problems) I can honestly say that I enjoyed working on this title. I may have complained a lot about the side scrolling engine during development but I think the finished product came out quite nicely.

In completely unrelated news I should probably mention that I participated in the Global Game Jam and ended up working with one of my co-workers (with whom I’ve never actually worked before, we have always been on different projects) as well as a programmer whom I met at the event. The full details of the event will be forthcoming.

First Annual Global Game Jam

January 16th, 2009 by Niki

The First Annual Global Game Jam is taking place at the end of the month, from January 30th to February 1st. New York City has two host locations: NYU-Poly and Columbia’s Teacher’s College. A few of my coworkers and I are planning on participating. I’m an NYU-Poly alum (well technically a Polytechnic University alum) however I will be at the Columbia game jam as the NYU-Poly game jam is open only to NYU/NYU-poly students and alums (which precludes my coworkers from attending).

The Global Game Jam is a game development competition that takes place over 48 hours. The design and constraints of the competition aren’t revealed until the very start so that the teams cannot plan ahead. An entire video game must be developed within 48 hours, from design to implementation.

The goal is for us to split up and join other groups as a means of networking, giving students an opportunity to work with professionals and to advertise our company.

The Dark Ages

January 11th, 2009 by Niki

I have added two more projects to my projects page, both of which come from the dark ages. The dark ages is back when I knew nothing about programming and considered myself to be a great programmer. The Dunning-Kruger effect I suppose. I look back at this code now and shudder, I’m sure that you could post it to The Daily WTF and it would fit right in.

But who doesn’t have some code that they were once proud of and are now ashamed of? That’s all part of growth and learning. I decided to put these projects online for posterity and to remind myself of how far I’ve come and [hopefully] how far I’ll go. With that preamble out of the way, the projects I posted are:

The Mandelbrot set – I wrote this when I was in high school, using the Windows API. The code actually isn’t that bad, aside from some silly code-repetition. Overall it was a pretty simple project with a lot of boiler-plate code so there was little room for my naivety to get in the way.

Robotic Motion Planning – I wrote this in college for my Computational Geometry class. I of course left this to the last minute and coded the entire thing in about a week, getting very little sleep during that time. Given the complexity of it and the extremely tight schedule it’s not that surprising it turned out the way it did. It’s extremely buggy (in fact, I can’t get it to run anymore!) and missing features. I never got around to actually calculating the path of the robot.

I have a few other old projects lying around, mostly from college. If I get a chance I’ll add those to the Dark Ages section of my projects page as well.

The Power of Perl

January 9th, 2009 by Niki

Perl was the first “real” programming language that I learned. As I recall I was really into web design at the time and wanted to learn how to make CGIs. Perl of course was the language de rigeur at the time for CGIs and was the natural choice. I did end up writing a couple of CGIs (including a message board!) as well as some more general scripts.

I once wrote a perl script that generated a Sierpinski Triangle using periods and asterisks. It was an extra-credit assignment for one of my high school math classes. It used the even/odd properties of Pascal’s triangle to generate it. I had to modify Pascal’s triangle, actually, because the size of the numbers ended up overflowing the integer type.

However it wasn’t until many years later that I truly started to understand and appreciate the power of Perl. By that time I had moved onto more “hardcore” languages (specifically C and C++) and largely forgot about Perl. That is until I started working at my current employer Powerhead Games. While our games are written in C++, we use Perl for a lot of behind-the-scenes work. Sometimes this is directly related to the game code – use a Perl script to read some files created by designers and have it output a C++ source file.

Sometimes however it’s just used as a time saver. Today, for example, we received a bug list from a publisher. This bug list was saved as an Excel document, but the individual bug reports it contained weren’t formatted in an “Excel-y” manner – they weren’t neatly arranged in rows and columns. This meant that in order to add these bugs into our database as-is they would have to be entered by hand.

Enter Perl. I saved the Excel document as a tab-separated text file and managed to write a script that extracted the meaningful information from each bug report and reformat so that it could be imported into our database. This took me no more than an hour (and I’m far from a Perl monk). Trying to write some C/C++ code to do the same thing would probably have taken longer than just manually entering all the data.

Tupper’s self-referential formula and other projects

January 8th, 2009 by Niki

Last night I added a Projects page and added two projects: my OCaml code and DWM patches mentioned in the previous post.

Over the past couple of days I managed to fix a couple of bugs in the OCaml code and add a Perl script to generate some information that can be used as input to the OCaml program. Tupper’s self-referential formula is a formula that can graph a monochromatic bitmap. The self-referential part refers to Tupper using it to graph a bitmap that looks like the formula itself. You can check out the projects page for more information on what the software actually does (and check Wikipedia for more information on the formula). The rest of this post is going to be about the code.

\displaystyle{1\over 2} < \left\lfloor \mathrm{mod}\left(\left\lfloor {y \over 17} \right\rfloor 2^{-17 \lfloor x \rfloor - \mathrm{mod}(\lfloor y\rfloor, 17)},2\right)\right\rfloor

Tupper's formula contains an exponent that is negative for most values of (x, y). A negative exponent of course results in the multiplicative inverse of the expression with a positive exponent. Since the OCaml Big_int module only supported positive exponents I simply negated the exponent (thus making it positive) and then inverted the result.

This worked fine for every case except when x was equal to zero, so initially I just skipped that case to prevent run-time errors. Eventually I realized that when x was zero the exponent was positive and since I was negating it, it ended up negative. The Big_int library then threw an exception.

I added in a check to test the sign of the exponent and to do the calculations with the absolute value. Then, depending on the sign, I would either multiply or divide (use the inverse). To do this I curried either the multiplication or division function and used the curried function for the rest of the calculations.

After that it rendered the image properly. I then went about generalizing the formula (and my code) so that it could support any monochromatic bitmap, not just the self-referential bitmap.

Tupper’s version of the formula is restricted to a bitmap that is 17 pixels high. There really isn’t a way to generalize the formula to accept any size bitmap unfortunately, but it’s easy enough to change the formula to accept a specific size. This of course makes it easy to generalize the code.

Finally I wrote a Perl script that will take an image and convert it to that magic number (the special integer representation of the bitmap).