» Archive for the 'math' Category

New project: prime number storage

Thursday, July 9th, 2009 by Niki

I have added a new project to the projects page: Prime number storage. When I was in college a friend of mine and I came up with a method for compressing and storing prime numbers. While doing research on our method we discovered that it was already in use.

However I recently decided to implement it anyway, as it was (and still is) interesting to me.

How 21 got the Monty Hall problem wrong

Thursday, 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.

The Dark Ages

Sunday, 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.

Tupper’s self-referential formula and other projects

Thursday, 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).