Lets Make A Deal Game Theory

(originally posted 10:08 AM, Feb 11, 2006)

A couple days ago (yes, in a bar) I became intrigued with a fairly well known game problem, here's my version:

1. There are three doors, one of which is a winner.
2. You pick one door, but it isn't opened yet.
3. At this point at least one of the unpicked doors (maybe both) are losers.
4. A losing unpicked door is opened.
5. You now have the option of either sticking with your original choice, or switching to the remaining unopened door. Which has a better chance of being the winner?
   

Here is a Perl script I wrote which will play the game using both the "switch" and "stay" strategies: http://eigenstate.net/misc_scripts/make_a_deal.pl

What do you think?

Tags: game theory, perl, lets make a deal







12 Feb 2006 - addition:

Here is one way of explaining what is going on:

When the losing choice is revealed, you gain some new information.

At the start, you have equal knowledge of all the choices, so at first every door has 1/n chance (1/3 if there are three doors).

You then divide doors into two groups: one door in group A (your first pick) and the rest of the doors in group B. With three doors group A carries 1/3 of the chances and group B carries 2/3.

When one of the doors in group B is revealed to be a loser you know something new:

You know that the group of chances that was in group B at the start must now be redistributed among the remaining doors in group B.

So if group B had 2/3 of the chances at the start, it *still has* 2/3 of the chances, but those all ride on the one remaining door in group B. So, the remaining door in group B has a 2/3 chance fo winning, whilst the door you originally picked, in group A still has only a 1/3 chance.

What has happend is that the revelation of the loser in group B has told you that all the other doors in group are more likely to be a winner.

If you try it with 10 doors it is still better to switch - to pick any remaining door in group B - than to stay with the door in group A.

Where N is the number of doors, the chance of the first pick winning is 1/N, and the chance of a door in group B after eliminating a loser from group B is: (N-1)/N

It is the -1 that makes swicthing worth it.

We can generalize the problem further by saying that T is the Total number of doors, A is the number of doors in group A, and B is the number in group B before a loser is revealed. Then the chance of a door in group A is A/T (for example, 1/3) and the chance of a door in group B, after the elimination is B - 1 / T.

So if there are 10 door total, and you put 3 doors in group A at the start:

T = 10
A = 3
B = 7

Each group A door has a 1/10 chance (3/10 for the group as a whole.) After eliminating a loser from group B, the group as a whole still has 7/10 chances and thus each remaining group B door has a 6/10 11 2/3% chance of being the winner. (thanks to keith for the correction)

Unit tests for Mozilla / Firefox coming soon

Dave Liebreich of Mozilla.com has posted the source code for jssh-driver - a unit test framework for use in Mozilla browsers, (e.g. Firefox). This little framework will allow you to have a directory of HTML files, and test if the browser renders them correctly. Basically the test loads the "golden master" versions into the browser and compares the rendered version to the version on disk. (When the browser renders an HTML page it takes it apart and puts it back together - hopefully correctly.)

Tags: mozilla, firefox, testing, unit tests

US Internet biz profits from oppression

From the Washington Post:

House: Internet Companies Give in to China

By FOSTER KLUG
The Associated Press
Wednesday, February 1, 2006; 10:37 PM

WASHINGTON -- Lawmakers on Wednesday accused U.S.-based Internet companies of
giving in to pressure from China and helping to censor Web users in violation
of American principles of free speech.

I think it's disgusting that these companies are seeking to profit from cooperation with oppression while simultaneously benefiting from the freedoms afforded them here in the US.

More tests, fewer bugs

Mozilla is looking for a few good test-driven engineers...

I visited the Mozilla Corporation offices yesterday, at the invitation of Dave Liebreich, who is heading up the effort to bring more testing to the Mozilla code base. There is a wiki page: http://wiki.mozilla.org/SoftwareTesting describing some projects and ideas. Dave is a good guy doing good work - let's help!

Tags: Mozilla, testing

Concrete Canvas

http://www.concretecanvas.org.uk/

Instant semi-permanent structure.
Fill bag with water, activate chemical gas-pack, it inflates and hardens and is ready for use in 12-hours.

Update (1 Feb 2006):
My friend and architect Bob Theis (http://www.bobtheis.net/) raised these important issues:

Clever idea. Two reactions:

1. Hard to imagine a shell that thin being dimensionally stable enough for such a span in compression ( how does it resist local buckling? ). ESPECIALLY when you cover it with earth to gain some insulation ( see below ).

2. The plastic sheet interior would condense ALL the water vapor that hits it when the temperature outside is low ( despite the website claims, the insulation value of the skin should be next to nil ), where it would then freeze in colder situations. So insulation and ventilation would be serious habitability issues.

Adding Assertions in Perl

I've been working on a Perl module that provides a set of assertion methods that will work in Perl 5.6.1 or later. (Note that Perl 5.10 should have some form of builtin support for assertions.)

So far I've implemented:

assert( expr, $optional_message ); # passes if expr is true
assert_is($$this,$that, $opt_msg); # compare with eq
assert_isnt($this,$that, $opt$msg); # Compare with ne

# all values must be == to each other
assert_num_equals($arrayref, $opt_msg);

save_data($key, $ref_to_data); # saves clone of data

# Assert that some data has (or not) the same values as the
# previsouly saved data - does a deep compare.
assert_data_not_different($key,$ref_to_data, $opt_msg);
assert_data_different($key,$ref_to_data, $opt_msg);


I've also implemented methods to set the pass and fail behaviors:

set_pass_behavior('silence');
set_pass_behavior('warn');
set_pass_behavior( \&my_sub ); # CODE ref


set_fail_behavior('silence');
set_fail_behavior('warn');
set_fail_behavior('confess'); #die with stack trace
set_fail_behavior( \&my_sub ); # CODE ref


I'm doing this for a client and am not sure if we'll be allowed to release the code publicly, but I hope so.

Adding Unit Tests to Legacy Code

I've started adding Unit Tests to a "legacy" code library. So far, the basic approach I am taking is:

1. Create the test harness.
2. The first test is to compile the old code library. Of course that fails at first because of all the things the library depends on.
3. Create enough "fake" class files that the library compiles.
4. Pick one subroutine (method) to test, and add a test that runs that subroutine. Of course it fails because of all the missing dependencies - the subroutine under test uses a bunch of subroutines defined in others.
5. In the test suite, create a FakeMethods class that defines stub versions of the missing external methods/subroutines, for example, the subroutine I am testing calls GetTotalAmount($cost,@items) so in the test suite I have something like this:
   
   

   sub GetTotalAmount {
    cluck('fake sub called');  # Print a stack trace showing we were called
    my($cost,@items) = @_;     # Document the arguments expected
    return;                    # Return nothing for now
   }
   



6. Some of the fake subroutines will need to return some actual values for the subroutine I am testing to run. Add just enough input so the test passes, even when this seems ridiculous. For example, I found that one subroutine wanted the name of a file to open, and that the subroutine would run even if I passed in the name of a non-existent file. OK, that's what I did. Later, we can add a test expecting the subroutine to throw an exception if the file doesn't exist, and then add defensive code to throw the subroutine.
   
7. Continue repeating steps 5 and 6 until the subroutine I am testing runs without throwing an exception.
8. Add tests to run the subroutine with variations on its arguments and/or environment. I may need to add more fake subroutines, mock data, etc.
9. The result is that I have a pretty clearly documented view of what the subroutine/method actually requires to run as of today.