The prime or the goat?

only_human · 2003-12-17, 23:40

I was just reading Paul Hoffman's book ("The man who only loved numbers") about Paul Erdõs. In it he talks about the Monty Hall dilemma based on the TV game show Let's Make a Deal, and interestingly posed as a brain teaser by Marilyn vos Savant.
In a nutshell, a game host shows you three doors, one of which has a car behind it -- the other two hide goats. After you select a door, the host shows you a goat behind one of the two unselected doors and asks if you want to switch from your initial choice to the other unopened door. The surprising answer is that that "when you switch, you win two out of three times and lose one time in three; but when you don't switch, you only win one in three times."

Code:

Choose Door 1 and stick with Door 1
Door 1      Door 2      Door 3      Outcome
Car          Goat         Goat         Win
Goat         Car          Goat         Lose
Goat         Goat         Car          Lose

Choose Door 1 but switch after seeing goat behind another door.
Door 1      Door 2      Door 3      Outcome
Car          Goat         Goat         Lose
Goat         Car          Goat         Win
Goat         Goat         Car          Win

I was wondering how this might apply to a range of numbers in the GIMPS hunt. For example, the range 25350000--30150000 has a guesstimated expectation of 0.45 primes. Say you pick a number (door) but can't peek behind it until your LL test completes. While you are getting ready to peek behind your door, one third of all the numbers in the range have been shown to have goats behind them (factors found or non-prime LL test results).

How would switching doors be the same or different from the "Let's Make a Deal" game?

Among other things, we don't really know if a prime is behind any of the doors -- but for the sake of discussion we can decide that there is exactly one (or not).

I am not posing this as an entirely serious problem. Simply feel free to post any thoughts or answers or comments directly into the thread.

GP2 · 2003-12-18, 04:39

Well, as you say, it's not applicable to GIMPS.

In the original problem, you know that there are exactly two goats and one car. So if the car is behind door one, then there can't be a car behind door two. Revealing information about one door changes the odds for all the remaining doors.

Now imagine a slightly different problem: you don't know how many goats or cars there are. Behind each door there is a 50-50 chance of a goat or a car, and you could have all 3 goats, all 3 cars, or some combination of goats and cars. Then every door is entirely independent and revealing information about one door doesn't reveal anything about the other doors.

GIMPS is like the second case. Except the odds of getting a car instead of a goat are more like 1 in 500,000.

only_human · 2003-12-18, 07:11

Now take the initial 3 door problem but during a commercial break, offer the host a sip of bourbon. You pick door number 1 and the host shows you what is behind door number 2 (he is drunk and doesn't check first to see if the car is there).

If the car is there, you've lost because the game is over -- but if he shows you a goat, you still have only 1 chance in 3 to get the car if you don't switch doors; if you do switch doors, you have 2 chances in 3 to get the car (the decision table is the same as in the first message -- I think).

Now say that SETI receives a message from outer space that is a sequence of mersenne prime numbers; the 41st mersenne prime number is in the range of the 500,000 doors proposed for this Monty Hall problem (and the 42nd is not -- it is higher). Our drunk host opens 450,000 doors and still the prime number hasn't been found. At this point is it better to stick with door number 1 or to switch?

GP2 · 2003-12-18, 08:12

I believe it's better to switch.

The original door, picked at random with no information, had no better than a 1 in 500,000 chance of being the right door. Whereas, choosing from among the other remaining doors you ought to have roughly a 1 in 50,000 chance of finding the prime.

Opening those other 450,000 doors revealed information that you didn't have when you picked the original door. You take advantage of that information by switching.

An extreme case of this would be if the host opened 499,998 doors, leaving only your original door and one other. You're being given an overwhelming clue...

Again, though, none of this is really applicable to real-life GIMPS as opposed to space-alien Monty-Hall GIMPS.

only_human · 2003-12-18, 15:17

I think you are right (especially about this being space-alien Monty-Hall GIMPS and not real-life GIMPS).

However, I have some points where I am not sure of my reasoning (and console myself that many others have had trouble)

For example, in the three door game, when the drunk host opens a door there is one chance in three that the game is over right then (with no chance to improve your odds by switching). So I am not certain if I have invalidated the Monty-Hall scenario by that proviso. Maybe the odds are 2 in 3 if you switch, but you are only allowed to switch 2/3rds of the time since sometimes the game ends early -- I am not sure.

During the second commercial break, the host confides to you (and condemns very strongly) that his cousin has installed a trojan program in the SETI search that forges a message from aliens when the search aims into the constellation Capricorn. The host shows a surprising amount of mathematical acumen but tells you he has no idea if the contents of the message are in fact a true statement.

rbarreira · 2003-12-18, 22:42

By the way, if you are trying to explain Monty Hall's problem to someone, at first they're always sceptical that it's better to switch, since seeing as there are two doors left after the other one is open, one would think that the probability to win is 1/2 on both cases (to switch or not to switch).

I found that the best way to convince people is to think like this (needs no tables or probability trees) - if you had initially chosen the car, when you switch you will switch to a cow (losing the game). On the other hand, if you had chosen a cow (and there are two), the host would show you the other cow, therefore forcing you to win if you choose to switch. Since there are two cows, and you win by choosing a cow and then switching, the probability of winning is 2/3.

If you like programming, check this out - http://acm.uva.es/p/v104/10491.html :)

only_human · 2003-12-19, 02:02

rbarreira,
I like your explanation. I also bookmarked that site to look it over more thoroughly in the future. The programming contests look interesting.

2003-12-17, 23:40	#1
only_human "Gang aft agley" Sep 2002 2·1,877 Posts	The prime or the goat? I was just reading Paul Hoffman's book ("The man who only loved numbers") about Paul Erdõs. In it he talks about the Monty Hall dilemma based on the TV game show Let's Make a Deal, and interestingly posed as a brain teaser by Marilyn vos Savant. In a nutshell, a game host shows you three doors, one of which has a car behind it -- the other two hide goats. After you select a door, the host shows you a goat behind one of the two unselected doors and asks if you want to switch from your initial choice to the other unopened door. The surprising answer is that that "when you switch, you win two out of three times and lose one time in three; but when you don't switch, you only win one in three times." Code: Choose Door 1 and stick with Door 1 Door 1 Door 2 Door 3 Outcome Car Goat Goat Win Goat Car Goat Lose Goat Goat Car Lose Choose Door 1 but switch after seeing goat behind another door. Door 1 Door 2 Door 3 Outcome Car Goat Goat Lose Goat Car Goat Win Goat Goat Car Win I was wondering how this might apply to a range of numbers in the GIMPS hunt. For example, the range 25350000--30150000 has a guesstimated expectation of 0.45 primes. Say you pick a number (door) but can't peek behind it until your LL test completes. While you are getting ready to peek behind your door, one third of all the numbers in the range have been shown to have goats behind them (factors found or non-prime LL test results). How would switching doors be the same or different from the "Let's Make a Deal" game? Among other things, we don't really know if a prime is behind any of the doors -- but for the sake of discussion we can decide that there is exactly one (or not). I am not posing this as an entirely serious problem. Simply feel free to post any thoughts or answers or comments directly into the thread.

2003-12-18, 15:17	#5
only_human "Gang aft agley" Sep 2002 2×1,877 Posts	I think you are right (especially about this being space-alien Monty-Hall GIMPS and not real-life GIMPS). However, I have some points where I am not sure of my reasoning (and console myself that many others have had trouble) For example, in the three door game, when the drunk host opens a door there is one chance in three that the game is over right then (with no chance to improve your odds by switching). So I am not certain if I have invalidated the Monty-Hall scenario by that proviso. Maybe the odds are 2 in 3 if you switch, but you are only allowed to switch 2/3rds of the time since sometimes the game ends early -- I am not sure. During the second commercial break, the host confides to you (and condemns very strongly) that his cousin has installed a trojan program in the SETI search that forges a message from aliens when the search aims into the constellation Capricorn. The host shows a surprising amount of mathematical acumen but tells you he has no idea if the contents of the message are in fact a true statement. Last fiddled with by only_human on 2003-12-18 at 15:21

2003-12-18, 22:42	#6
rbarreira Oct 2003 Portugal 1011₂ Posts	By the way, if you are trying to explain Monty Hall's problem to someone, at first they're always sceptical that it's better to switch, since seeing as there are two doors left after the other one is open, one would think that the probability to win is 1/2 on both cases (to switch or not to switch). I found that the best way to convince people is to think like this (needs no tables or probability trees) - if you had initially chosen the car, when you switch you will switch to a cow (losing the game). On the other hand, if you had chosen a cow (and there are two), the host would show you the other cow, therefore forcing you to win if you choose to switch. Since there are two cows, and you win by choosing a cow and then switching, the probability of winning is 2/3. If you like programming, check this out - http://acm.uva.es/p/v104/10491.html :) Last fiddled with by rbarreira on 2003-12-18 at 22:44

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!	dabaichi	News	571	2020-10-26 11:02
disk died, prime work lost forever? where to put prime? on SSD or HDD?	emily	PrimeNet	3	2013-03-01 05:49
How do I determine the xth-highest prime on prime pages?	jasong	Data	7	2005-09-13 20:41
The 40th known Mersenne prime, 220996011-1 is not PRIME!	illman-q	Miscellaneous Math	33	2004-09-19 05:02
Goat grazing inside a circular fence.	Fusion_power	Puzzles	2	2003-09-25 04:40

2003-12-18, 04:39	#2
GP2 Sep 2003 2585₁₀ Posts	Well, as you say, it's not applicable to GIMPS. In the original problem, you know that there are exactly two goats and one car. So if the car is behind door one, then there can't be a car behind door two. Revealing information about one door changes the odds for all the remaining doors. Now imagine a slightly different problem: you don't know how many goats or cars there are. Behind each door there is a 50-50 chance of a goat or a car, and you could have all 3 goats, all 3 cars, or some combination of goats and cars. Then every door is entirely independent and revealing information about one door doesn't reveal anything about the other doors. GIMPS is like the second case. Except the odds of getting a car instead of a goat are more like 1 in 500,000.

2003-12-18, 07:11	#3
only_human "Gang aft agley" Sep 2002 2·1,877 Posts	Now take the initial 3 door problem but during a commercial break, offer the host a sip of bourbon. You pick door number 1 and the host shows you what is behind door number 2 (he is drunk and doesn't check first to see if the car is there). If the car is there, you've lost because the game is over -- but if he shows you a goat, you still have only 1 chance in 3 to get the car if you don't switch doors; if you do switch doors, you have 2 chances in 3 to get the car (the decision table is the same as in the first message -- I think). Now say that SETI receives a message from outer space that is a sequence of mersenne prime numbers; the 41st mersenne prime number is in the range of the 500,000 doors proposed for this Monty Hall problem (and the 42nd is not -- it is higher). Our drunk host opens 450,000 doors and still the prime number hasn't been found. At this point is it better to stick with door number 1 or to switch?

2003-12-18, 08:12	#4
GP2 Sep 2003 2585₁₀ Posts	I believe it's better to switch. The original door, picked at random with no information, had no better than a 1 in 500,000 chance of being the right door. Whereas, choosing from among the other remaining doors you ought to have roughly a 1 in 50,000 chance of finding the prime. Opening those other 450,000 doors revealed information that you didn't have when you picked the original door. You take advantage of that information by switching. An extreme case of this would be if the host opened 499,998 doors, leaving only your original door and one other. You're being given an overwhelming clue... Again, though, none of this is really applicable to real-life GIMPS as opposed to space-alien Monty-Hall GIMPS.

2003-12-19, 02:02	#7
only_human "Gang aft agley" Sep 2002 2·1,877 Posts	rbarreira, I like your explanation. I also bookmarked that site to look it over more thoroughly in the future. The programming contests look interesting.