A discussion of the probability problem known as the Monty Hall problem.
A Basic computer program is described which solves the problem and which
demonstrates the use of simulation as a powerful, largely non mathematical solution method.
The name arises from an American game show which had an host named Monty Hall. The game show was very simple. The contestant was confronted with three closed doors. Behind two were goats (?) and behind the third was the prize, a car. The contestant was asked to nominate a door, the host then opened one of the two remaining doors to reveal a goat. The player was then asked whether or not he wished to change his original selection. The door of his choice was then opened to reveal either a goat or the prize car.
The question is, what should be the contestant’s strategy? Should the player change his choice when the offer is made and does it actually matter? An initial consideration of the problem is that, when it comes to the actual time of choice, what the contestant has to consider are two closed doors behind one of which is a goat and behind the other is a car. Intuitively one is inclined to think, it is a 50/50 choice. Forget all the initial shenanigans, we are left with a straight choice. Pick one or the other and see if we are lucky. There appears to be no advantage to either selection.
However, bending the brain a little and applying thought tells us that on the first nomination, there is a 1/3 chance of selecting the car and a 2/3 chance of selecting a goat. So in order to win, 1/3 of contestants should stick with the first choice but 2/3 will win only if they change their selection. Or to put it another way, if all contestants enter with a policy of changing their initial selection when asked, then 1/3 of them will lose and 2/3 will win. Pretty good odds. Pretty good policy.
So there we have the solution to the problem. Counter intuitively perhaps, changing your selection improves your chance of winning.
There is a good description and analysis of the problem on Wikipedia at,
http://en.wikipedia.org/wiki/Monty_Hall_problem
This problem is a good simple example of the type of problem which may be readily solved by simulation. Although this particular problem is easily solved by a bit of thinking, it is very easy to set up a computer to essentially play this type of game, to repeat it many times and thereby deduce the likelihood of any long term events occurring. Even very complex situations, requiring advanced mathematics for a direct solution may well yield to this approach. Indeed there are problems for which the mathematics does not exist to allow direct application and for which simulation is the only way to get a quantitative analysis of the problem.The Simulation Programme
The following programme simulates the Monty Hall problem and estimates the probability of success of each of the discussed policies.
This particular program should be easily adapted to other dialects of Basic. Most of the instructions are standard and should be found in other Basics.
The program is written in BBC Basic for Windows. This is a very useful, well documented, well supported, straightforward language for programming in an XP or Vista environment. It is highly recommended. A free demonstration version is available. The web site is,
There are perhaps just a couple of items which require explanation.
c1%+=1 is BB4W’s simplification of the more general statement c1%=c1%+1
and vdu30 is a command which homes the text cursor to the top left corner of the screen. The titles printed over the tops of columns are scrolled off screen when the number of iterations is large. The vdu30 allows the column headings to be re-written once the simulation has completed.Now a quick description of what the program is doing. Below is shown a small but typical section of the program's output. Each line represents one complete play of the game.
The three doors are first represented by a string of three question marks.
One location is randomly selected to hold the car but not revealed.
One location is randomly chosen to hold the contestant’s selection. This is shown in the string by changing the “?” to “S”.
Next the host reveals a goat; shown in the string with a G.
This is the point at which the player must make a choice.
In the output the actual goat/car arrangement is now shown and then followed with the result which each of the possible player choices would produce.
After repeating these results for a large number of plays, the simulation ends by computing the probability of winning under each of the strategies.
rem The Monty Hall Problem
print tab(41);"Selection Policy"
print tab(2);"Select Door Show Goat Actual SetUp Change No Change"
:
n%=100 : rem Choose number of iterations
c1%=0 : c2%=0 : rem Clear win counters
:
for i%=1 to n%
Car = rnd (3) : rem Car location
Sel = rnd (3) : rem Player selects a door
repeat
Host = rnd(3) : rem Host selects a door to open
until Host <> Sel and Host <> Car
rem Ensure host's choice is not the car or the selected door
:
rem Show the game
A$="? ? ?" : rem 3 unknown doors
rem Show player's selection
mid$(A$, (2*Sel)-1)= "S" : rem Mark selected door as S
print tab(4);A$;
mid$(A$, (2*Host)-1)= "G" : rem Mark host's door as G
print tab(17);A$;
rem Now reveal actual setup
S$ = "[G G G]" : rem Initially mark all doors as goats then
mid$(S$, 2*Car)= "C" : rem show car door as C
print tab(29);S$;
if Car= Sel then print tab(51);"WIN Car behind selected door" :c1%+=1
if Car<>Sel then print tab(42);"WIN Car behind other door":c2%+=1
next
:
print " Prob of win if selection unchanged = "; c1%/n%
print " Prob of win if selection changed = "; c2%/n%
vdu 30 : rem Home text cursor and reprint column headings
print tab(41);"Selection Policy";string$(25," ")
print tab(2);"Select Door Show Goat Actual SetUp Change No Change";string$(25," ")
end
The greater the number of iterations (n%) the more accurate will be the predicted probabilities. I have limited it to 100 in the program. This, I think, is sufficient to support the 1/3, 2/3 reasoning given in the introduction.
Should you be unfamiliar with the methods of simulation but intrigued by its possibilities I would like to suggest another problem which you might like to try. There is another well known problem in probability, the solution to which is counter intuitive. The problem is this. How many people need to be together in a room in order to find that, it is more likely than not, two (or more) have the same birthday?
Intuitively one is inclined to reason, there are 365 different birthdays possible, we could easily have 100 or more people all with different birthdays. Must take a fair number to make it likely two have the same birthday. The answer however, is quite surprising. It is possible to answer this question applying the principles of mathematical probability but it is not nearly as simple as was the Monty Hall problem. Simulation will give the answer with no knowledge of mathematical probability whatsoever.
The construction of the initial numerical model of the problem is probably the most interesting part of the problem solving. It is necessary to pick out the essentials of the problem and then represent those, and just those, in as simple a form as possible. I was tempted, in suggesting the problem, to offer a few hints on how to set up the problem in a simple fashion. On reflection I think I could be spoiling your enjoyment so I will leave it with you as it is.
Home Page