Let's Make a Deal - Let Monty Rest!

Some "solved" problems just never go away. Perpetual Motion machines is one example. Another example is the Monty Hall Problem. There is presently a mini-debate in the discussion area of Scientific American's How Randomness Rules Our World and Why We Cannot See It with a significant number of adamant doubters of the standard result that states it is better to switch if Monty shows you a goat.

This problem is amazingly obvious to understand once you analyze it correctly and remove certain ambiguities from the problem statement. Here's my analysis and some Mathematica simulations to add some weight (as if any is needed).

Okay, we all can agree that the probability of NOT picking the DREAM VACATION is 2/3, right? There are two GOATS and one DREAM VACATION.

Now, when Monty shows you the remaining door with a GOAT he just beamed you some very significant information. He's told you that if you picked a GOAT then the probability of getting a DREAM VACATION is 1 if you switch! We already know the probability you picked a GOAT is 2/3 so after he gives you this new info your probability of winning is now 2/3. So switch for GOAT's sake!! If you don't switch, your probability is just 1/3.

Here is a Mathematica program for the non-believers.

GOAT = 0; (* Goat worth zero *)
VACATION = 1; (* Vacation worth one*)

makePrizes[] := Module[{},Switch[RandomInteger[{1,3}],
1,{GOAT,GOAT,VACATION},
2,{GOAT,VACATION,GOAT},
3,{VACATION,GOAT,GOAT}]]

randomPick[doors_List] := Module[{},RandomInteger[{1,Length[doors]}]]

strategy1VS2[trials_Integer] :=
Module[{winnings1=0, winnings2=0, firstPick, secondPick, doors, doors2},
SeedRandom[];
Do[doors = makePrizes[];
firstPick = randomPick[doors];
(*winnings of person who keeps first pick*)
winnings1+= doors[[firstPick]];
(*delete first pick from choices*)
doors2 = Drop[doors,{firstPick}];
(*delete goat from remaining*)
doors2 = Drop[doors2,Position[doors2,GOAT][[1]]];
(*Always pick remaining prize *)
secondPick =doors2[[1]];
(*winnings of person who switches*)
winnings2+= secondPick,{trials}];
{winnings1,winnings2}]

(*Run simulation 10000 times. *)
strategy1VS2[10000]
{3356,6644}

The result {3356,6644} means keeping first choice only paid 3356 over 10000 runs but switching paid 6644!

Now, there are ASSUMPTIONS here (there always are). One assumption is that on each run the position of the prize changes. It turns out that keeping the prize always in any particular door for the entire simulation does not matter (as long as the contestant does not have the information, obviously!)

strategy1VS2A[trials_Integer,init_List] :=
Module[{winnings1=0,winnings2=0,firstPick,secondPick,doors,doors2},
SeedRandom[];
Do[doors = init;
firstPick = randomPick[doors];
(*winnings of person who keeps
first pick*)
winnings1+= doors[[firstPick]];
(*delete first pick from choices*)
doors2 = Drop[doors,{firstPick}];
(*delete goat from remaining*)
doors2 = Drop[doors2,Position[doors2,GOAT][[1]]];
(*Always pick remaining prize *)
secondPick =doors2[[1]];
(*winnings of person who switches*)
winnings2+= secondPick;,{trials}];
{winnings1,winnings2}]

strategy1VS2A[10000,{GOAT,GOAT,VACATION}]
{3316,6684}

strategy1VS2A[10000,{GOAT,VACATION,GOAT}]
{3267,6733}

strategy1VS2A[10000,{GOAT,GOAT,VACATION}]
{3382,6618}

The other assumption is that your not forced to switch before seeing the goat. This IS important!!

strategy1VS2B[trials_Integer] :=
Module[{goatPositions,pos,winnings1=0,winnings2=0,firstPick,secondPick,doors,doors2},
SeedRandom[];
Do[doors = makePrizes[];
firstPick = randomPick[doors];
(*winnings of person who keeps first pick*)
winnings1+= doors[[firstPick]];
(*delete first pick from choices*)
doors2 = Drop[doors,{firstPick}];
(*Randomly choose from remaing*)
secondPick =randomPick[doors2];
(*winnings of person who switches*)
winnings2+= doors2[[secondPick]];,{trials}];
{winnings1,winnings2}]

strategy1VS2B[10000]
{3373,3295}

So information has value, Duh!

So now that you have this information, become a believer, make the switch!

Drilling Square Holes

One of the fringe benefits of working on a book is all the tidbits of knowledge you come across while doing research. While working on the graphics chapters I cam across a shape known as a Reuleaux triangle.

It turns out that this shape is the key to doing what on the surface may seem impossible, Drilling a nearly square hole.

Encyclopedia of Integer Sequences

I found this site via one of my connections on Linkedin. It is not the most intuitive web site in the world if you merely want to brows but it is rather unique and its search feature is probably useful to anyone doing Mathematics research.

Interval Math

While doing research for the Numerics Chapter of my forthcoming Mathematica Cookbook I came across a site devoted to research on Interval Math. Interval Math is an approach from the domain of Numerical Analysis that deals with the fact that all measurements are imprecise by abandoning the representation of measured values by numbers. Instead of numbers, it defines all mathematical operations on intervals.

Mathematica (as of version 5) support real (but not complex) interval math where intervals take the form Interval[{min1,max1}...]. All of the typical mathematical operations and functions are defined for intervals.

Interval math is important for computer systems that must act intelligently in the real world. All sensors are approximate. This is true for man-made devices as well as for our own eyes and ears. If a sensor on a robot returns a particular value there is always an inherent error. Rather than deal with errors by sampling and averaging, interval math allows the error to directly be represented in the values that enter downstream computations. This means all intermediate results track the propagation of errors from multiple sources to yield better information. There also seems to be a relationship between interval computation and fuzzy sets but it I have not located any resources except on paid content sites.

It seems that although the study of Interval math began in the US it is largely forgotten while in Germany it is there are conferences and it is part of the qualifying exams for studies in numerical methods.

Some of the less technical resources on the earlier mentioned site are this introduction, an article from American Scientist and even a movie.

The Problem with Mathematics Education

There are numerous essays and newspaper blurbs lamenting the poor state of mathematical education in the US. Here is a typical example: Presidential panel bemoans state of math education.

What I see as the problem is that advanced mathematics is introduced in language that is unfit to inspire any but the few that were genetically destined to be mathematicians (or physicists).

Ask a recent college grad what an Eigen value or Eigen vector is. I give you 100:1 odds you'll get a blank stare. Okay now ask them to read this explanation from a popular Math web site. I bet their face will be even blanker. Now ask them to read this wonderful little explanation. Chances are the lights came on.

This is not to say that the later explanation will allow a person to do the math. But this is certainly where Math education, even at the highest levels, should begin. Illustrate why the problem is important, give a sensory picture to go along with the abstractions. Some might believe that this is how most Mathematicians teach but that is simply not the case. Mathematics is a very macho profession and many mathematicians believe its beneath them to offer intuition prior to rigor. The sad truth is many of them could not come up with compelling intuitive explanations even if they wanted to. It was not the way they were taught either.

Ubiquitous Eigenvectors and Quantum Computing

Recently I have been studying Quantum Computation (QC). If you want to get anywhere with QC you need to master Linear Algebra and Vector Spaces since QC is baically an exercise in applied vector space theory.

Being a bit rusty in the topic myself, I decided to pick up the book Finite-Dimensional Vector Spaces by Paul Richard Halmos. Although Halmos is one of my favorite math authors, I picked this book primarily because it has a Kindle edition. It turns out that another one of Halmos's books, Linear Algebra Problem Book, is a far better choice for the non-mathematcian. The later book walks you step by step through bite sized problems and provides hints (and also all the answers if you get stuck). A free resource with answers can also be found here.

One of the central mathematical techniques at the heart of Linear Algebra is the concept of Eigenvectors and Eigenvalues. The term Eigen is derived from German and means "characteristic". An Eigen Decomposition is a method of reducing a square matrix to into a constant (eigenvalue) and a vector (eigenvector). This decompostion is central to many problems in physics.

It turns out that the study of Eigen decompostion can yield deep insight into problems that are in the realm of computer science. Consider, for instance, this paper about Google's page rank algorithm and the Eigenface technique for facial recognition.

Coming to grips with the mathematics behind Vector Spaces is one of the single most rewarding experiences for anyone interested in advanced problems in computer science. It is a must if you ever want to graduate from the comprehension of clasical algorithms to the comprehension of quantum algorithms. However, if are curious about QC but the thought of learning advanced linear algebra sounds like too big of a comitment, then you might want to check out Quantum Computation explained to my Mother. This is the most approachable paper I have ever read on the topic that is also mathematically accurate.