Wednesday, February 23, 2005

The Monty Hall problem

This particular problem has caught the fancy of some (Microsoft) interviewers lately but sometime back it was the hot topic for debates among top Mathematicians worldover. Marilyn Vos Savant was a columnist in Parade magazine (Appearently she is listed in Guiness Book of World Records for highest IQ (228)!). Her column used to invite logical questions from the readers and she used to solve the problems and supply the reasoning too. The column stirred up a hornet's nest when it published the solution by Marilyn for following problem:

Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what's behind the doors, opens another door, say number 3, which has a goat. He says to you, "Do you want to pick door number 2?" Is it to your advantage to switch your choice of doors?

Craig. F. Whitaker
Columbia, MD

We'll come to Marilyn's solution but before that there's an intesting piece of trivia about how it got the name - The Monty Hall's Problem/Paradox. Monty Hall was the presenter of Let's Make A Deal, which was a famous game show on american television back in 70's. The aforementioned problem is taken from the show. There was one episode where Monty did the exact thing; made the contestant choose one of the three doors and opened one not having the car. Now the contestant was asked whether s/he wants to change the choice. This made certain Mr. Whitaker think about the mathematical side of it!

Coming back to Marilyn; she suggested that the contestant should switch the doors. This response caused an avalanche of responses, mainly from people disagreeing with her! Various professors, PhDs and teachers challanged her solution. They had decided that it doesn't matter if the contestent switch or not! Due to the fervor created by Ms. Savant’s two columns, the New York Times published a large front page article in a 1991 Sunday issue which declared: “Her answer... has been debated in the halls of the C.I.A. and the barracks of fighter pilots in the Persian Gulf. It has been analyzed by mathematicians at M.I.T. and computer programmers at Los Alamos National Laboratory in New Mexico. It has been tested in classes ranging from second grade to graduate level at more than 1,000 schools across the country.” After several rounds of communication, she finally asked people to organize experiments (by computer simulation) and send her the results. The results matched her claim to astonishing degrees. But not all were satisfied by this experimental proof. Later several people came forward with theoritical proofs. The following picture explains the solution by taking all the possible outcomes and hence proving that the chances increase to 2/3 if the switch is made!

The catch is in the phrase "..and the host, who knows what's behind the doors..". If it was to be the case where the host was also as clueless as the contestent, the switch wouldn't have made any difference. But since the host knows beforehand about the gate with the car behind it and knowing that opens a gate which doesn't have the car behind it, it would increase the probability of winning car by switching the gates! Hats off to Marilyn for getting this non-intutive solution!

P.S. : I got curious about the origin and explaination after I read about this problem in The Curious Incident.... The protagonist, Christopher, has solved the problem all by himself in the book!

No comments: