Steve Smith has posted a couple of interesting probability problem solvers on his blog recently. His most recent one is a twist on the Monty Hall problem. I mentioned the Monty Hall problem and its solution in an earlier blog entry of mine, For Some Probability Problems, Seeing Can Be Believing:
When facing a particularly tough probabilty problem sometimes it helps to sit down and draw out the possible outcomes for the given scenarios. In doing so, things that may otherwise seem very complex boil down to a very apparent solution or explanation.
A great example of simplicity through diagraming is the Monty Hall problem, which goes like this: You are a contestant on the TV game show, Let's Make a Deal and are presented with three doors. Behind one door there is a luxury car. Behind the other two doors there is a poster of a car. The game show host asks you to pick a door. After choosing one, the game show host reveals one of the other doors that has a poster behind it and then asks you if you want to change your door choice to the other unopened door. What is the best strategy?”
The answer is that you should change the door you had selected, because there's a 2/3 probability that the door you did not select houses the luxury car. In other words, there is a 2/3 probability that the door you picked has the remaining poster. The solution seems backwards. It seems paradoxical that the door the host reveals to have a poster of a car could have any influence on your initial selection. But if you sit down and draw out the various probabilities you can see that there's there are more good outcomes if you make the switch than if you hold fast to your initial choice. The following diagram was created by Rick Block; here, instead of a poster of a car you get a goat. Same difference.
Steve's most recent puzzle asks what would happen if instead of a single contestent in the Monty Hall problem there were multiple participants:
I take 3 plain envelopes and put a $100 bill inside one of them, seal them, and give one to you, one to Bob, and one to Carrie, at random. Then I randomly ask one of you to open an envelope - for the sake of argument let's say I choose Carrie. Carrie opens her envelope to reveal that it is empty. Now I offer you the choice to trade envelopes with Bob - should you trade? And now I ask Bob the exact same question. Should he trade?
As written, Steve's problem isn't that interesting. If he is randomly choosing one envelope to open then there is no advantage to be gained by changing or not changing your envelope. Now, if Steve were to reword the problem as follows (as I believe was his intention), then things are a bit more interesting:
I take 3 plain envelopes and put a $100 bill inside one of them. I then let you choose one, and then give the other two to Bob and Carrie. I then open one of the envelopes (Carrie's or Bob's) knowing that it is empty. Now I offer you the choice to trade envelopes with Bob - should you trade? And now I ask Bob the exact same question. Should he trade?
There is a big difference between these two questions. In the first one, everything is random; in the second one, the host (Steve Smith) knowingly opens one of the envelopes that is empty. It's also important that the host is forced to open Bob or Carrie's envelope, and cannot attempt to open yours.
The answer to this problem can be worked out the same way as the traditional Monty Hall problem - by putting pen to paper and drawing out the probability tree, although I used the name Cal instead of Carrie. (See the full size image...)
As you can see, your odds are maximized if you get your hands on your contestant's envelope, while your opponent's best bet is to keep his envelope. Therefore, whoever gets to make the final change is the person with the best odds.
Another tool for determining how a probability puzzle works out is through empirical means. You can oftentimes write a terse program that simulates the problem at hand thousands of times and tallies up the various outcomes. I created such a program in C#.
1 for (int iter = 0; iter < ITERATIONS; iter++)
2 {
3 int moneyPos = rnd.Next(3);
4 int bucketChoice = 2;
5 int openDoor = rnd.Next(2);
6 if (moneyPos == openDoor)
7 openDoor = 1 - openDoor;
8 int oponentsPos = 1 - openDoor;
9
10 bool makeSwap = rnd.Next(2) % 2 == 0;
11 bool otherContestantMakesSwap = rnd.Next(2) % 2 == 0;
12
13 if (makeSwap)
14 {
15 tmp = bucketChoice;
16 bucketChoice = oponentsPos;
17 oponentsPos = tmp;
18 }
19
20 if (otherContestantMakesSwap)
21 {
22 tmp = bucketChoice;
23 bucketChoice = oponentsPos;
24 oponentsPos = tmp;
25 }
26
27 // See if we won
28 if (bucketChoice == moneyPos)
29 {
30 if (makeSwap && otherContestantMakesSwap)
31 numberOfWinningsWhenSwappingAndContestantSwaps++;
32 else if (makeSwap && !otherContestantMakesSwap)
33 numberOfWinningsWhenSwappingAndContestantStays++;
34 else if (!makeSwap && otherContestantMakesSwap)
35 numberOfWinningsWhenStayingAndContesstantSwaps++;
36 else
37 numberOfWinningsWhenStayingAndContesstantStays++;
38 }
39 else if (moneyPos == oponentsPos)
40 {
41 if (makeSwap && otherContestantMakesSwap)
42 numberOfContestantWinsWhenYouSwapAndContestantSwaps++;
43 else if (makeSwap && !otherContestantMakesSwap)
44 numberOfContestantWinsWhenYouSwapAndContestantStays++;
45 else if (!makeSwap && otherContestantMakesSwap)
46 numberOfContestantWinsWhenYouStayAndContestantSwaps++;
47 else
48 numberOfContestantWinsWhenYouStayAndContestantStays++;
49 }
50 }
51
52 // Summarize results
53 Console.WriteLine("Percentage of Wins When Swapping and Contestant Swapping: {0}", Convert.ToDecimal(numberOfWinningsWhenSwappingAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));
54 Console.WriteLine("Percentage of Wins When Swapping and Contestant Stays: {0}", Convert.ToDecimal(numberOfWinningsWhenSwappingAndContestantStays) / Convert.ToDecimal(ITERATIONS));
55 Console.WriteLine("Percentage of Wins When Staying and Contestant Swapping: {0}", Convert.ToDecimal(numberOfWinningsWhenStayingAndContesstantSwaps) / Convert.ToDecimal(ITERATIONS));
56 Console.WriteLine("Percentage of Wins When Staying and Contestant Stays: {0}", Convert.ToDecimal(numberOfWinningsWhenStayingAndContesstantStays) / Convert.ToDecimal(ITERATIONS));
57 Console.WriteLine("");
58 Console.WriteLine("Percentage of Contestant Wins When Swapping and Contestant Swapping: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouSwapAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));
59 Console.WriteLine("Percentage of Contestant Wins When Swapping and Contestant Stays: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouSwapAndContestantStays) / Convert.ToDecimal(ITERATIONS));
60 Console.WriteLine("Percentage of Contestant Wins When Staying and Contestant Swapping: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouStayAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));
61 Console.WriteLine("Percentage of Contestant Wins When Staying and Contestant Stays: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouStayAndContestantStays) / Convert.ToDecimal(ITERATIONS));
I set ITERATIONS to 50,000 and let 'er rip. The following output confirmed my initial assumptions:
Percentage of Wins When Swapping and Contestant Swapping: 0.08266
Percentage of Wins When Swapping and Contestant Stays: 0.16618
Percentage of Wins When Staying and Contestant Swapping: 0.16482
Percentage of Wins When Staying and Contestant Stays: 0.08318
Percentage of Contestant Wins When Swapping and Contestant Swapping: 0.16754
Percentage of Contestant Wins When Swapping and Contestant Stays: 0.08386
Percentage of Contestant Wins When Staying and Contestant Swapping: 0.08262
Percentage of Contestant Wins When Staying and Contestant Stays: 0.16914
As you can see, your chances of winning are best when you swap and your contestant stays or when you stay and your contestant swaps - namely, when you get your hands on your contestant's envelope. Your contestant, however, does best when he hangs onto his envelope, either by having you both stay or both change.