Saturday, 14 October 2017

Monty Hall

Two weeks ago, on Saturday 30 September, two big names in mathematics died.  Vladimir Voevodsky, who was only 51, made huge contributions to mathematics.  I became aware of his importance to contemporary mathematics when reading Michael Harris's wonderfully stimulating book Mathematics without Apologies and regret that I do not know much about him and his work.

The other, Monty Hall, was not a mathematician but a game show host, who has given his name to one of the most famous recreational mathematical puzzles.  A lot has been written about the Monty Hall Problem: I recommend Jason Rosenhouse's book (called, surprisingly enough, The Monty Hall Problem, which gives an excellent account of the embarrassing (for male mathematicians) l'affaire Parade which brought the puzzle to public notice - see http://marilynvossavant.com/game-show-problem/ for the correspondence.

In Monty Hall's game show, a contestant had to choose one of three boxes.  One contained a car: the other two each contained a goat.  After the contestant had made their choice, Monty (who knew which box contained the car) would sometimes open the door of an unchosen box to reveal a goat, and then offer the contestant the chance to change their choice.  Should the contestant switch?

I remember, as a schoolboy, discussing with my friends a problem in one of Martin Gardner's books.  Three prisoners, A, B and C, are told that on the next day two of the three will be executed: which two has already been decided randomly.  (As I get older I increasingly find the rather bloodthirsty settings of puzzles like this in very poor taste: why do so many mathematical puzzles involve the abuse and execution of prisoners?)  A knows that his chance of survival is 1/3.  The guard won't answer any question which would give him information about whether or not he has been chosen for execution.  But A points out to the guard that at least one of the other two is going to die, so if the guard identifies to A one of the others who will die, then that cannot give any information about A's fate: whichever two have been selected, the guard can answer this question without revealing whether A has also been chosen.

So the guard tells A that C is going to die.  A is now happy: his survival chance was 1/3 but has now gone up to 1/2 since it is either him or B who will survive.

Of course (on certain assumptions) A is wrong: it is B whose survival chance has gone up to 2/3.  A's chance is unchanged at 1/3.  If A and B were selected to die, the guard would tell A that B was ill-fated.  If it was A and C to die, then the guard would answer "B".  Bit if B and C are both going to die, then the guard could answer either "B" or "C", and if one assumes the guard chooses randomly which to name, then enumerating the cases shows that when the guard answers "C", two times out of three it was A rather than B who is also selected for death.

This led me to get the Monty Hall Problem wrong when I first read about it in a newspaper article (the Independent, perhaps around Christmas 1990?)  Knowing that in the Gardner problem A's chances haven't changed, I assumed that the quiz show contestant can't improve their chance of winning by switching.  This is plain wrong, but I wonder if memories of Gardner's puzzle led astray many of the mathematicians who on first seeing it got the Monty Hall Problem wrong?  Although my initial answer was wrong, on careful reading of the analysis I did quickly come to agree that the contestant should switch, and verified this by computer simulation.

In fact, the problems are very closely related.  What Monty Hall is doing is essentially saying to A, "C is going to die - would you like to change places with B?"  And since B has a 2/3 chance of survival, A should certainly accept that offer.  (On certain assumptions.)

But the assumptions are critical (and most recent presentations of the Monty Hall Problem do make this clear.)  The 2/3 probability of winning if the contestant switches assumes that the host will always carry out the procedure, and that, when the contestant has initially chosen the box with the car, that the host will choose one of the other boxes to open with equal probability.  (If the host simply always opens the nearer box with the goat, then on the occasions when the host opens the further away box, the contestant will know that a switch guarantees success.)   And the host might not go through this procedure every time. If the host wants to save his employers money, then he might only offer the switch option on those occasions when the contestant has initially chosen the winning box.  If the host likes the contestant, he might only offer the switch option when the initial choice is losing.

In fact (according to, for example, the Wikipedia entry for Month Hall, in the real game show Monty did not always offer the choice.  He was playing a psychological game with the viewer, and, when "The Monty Hall Problem" became famous, he was well aware that the conditions necessary for the mathematical puzzle did not in fact apply to his game show.  I find it very pleasing that the game show host had a better understanding of the mathematics problem than many of the mathematicians whose instinctive answer, like mine, was wrong.