[REBOL] Re: A Rebol Challenge. The Monty Hall Puzzle
From: joel:neely:fedex at: 16-Dec-2001 16:20
Hi, Sunanda, et al,
It seems to me that the problem in the original post was persuasion
and not just computation. That being the case, the text of the
program itself (or its derivation) should be a compelling argument
for the right answer.
IOW, if I had trouble understanding/accepting an answer, I would
not be very persuaded simply by the output of a highly compact
program that seemed to contain assumptions about the very answer
I was having trouble with.
That said, let me offer two lines of reasoning (starting with the
same assumptions -- one argument based on verbal reasoning and one
based on code refactoring) which might be of some persuasive value
(but YMMV).
****************
* ASSUMPTIONS: *
****************
0) There are three doors.
1) The prize door is chosen at random.
2) The contestant chooses a door at random.
3) Monty chooses and opens a door at random that is neither the
prize door nor the contestant's door.
********************
* VERBAL ARGUMENT: *
********************
Imagine that there are two contestants playing as a team. They
agree on an initial guess (randomly chosen, remember), but then
one (A) always keeps the initial guess, while the other (B) always
switches after Monty opens a door.
Since Monty always opens a non-prize door (leaving two doors
unopened) exactly one of them must win on every round.
Since Monty opens the non-prize door after the initial guess is
chosen, his choice of which door to open changes neither the
initial guess nor the door behind which the prize has already
been placed. Therefore, A's chances of winning are unaffected
by what Monty does.
Since A is choosing randomly to find the winning one door out of
three, his odds of winning are 1/3, and his odds of losing are 2/3.
Therefore, B's odds of winning are 2/3 (B wins whenever A loses).
*************************
* REFACTORING ARGUMENT: *
*************************
Implementing the assumptions (using RANDOM) and trying a bunch of
rounds, we get something like this (in my best commented-to-death
style -- remember that we're explaining to a skeptic ;-) :
8<------------------------------------------------------------
pickadoor: function [
rounds [integer!]
][
prizedoor guessdoor montydoor keepwins switchwins
][
;
; neither strategy has won anything before we start
;
keepwins: switchwins: 0
;
; simulate the specified number of rounds
;
loop rounds [
;
; prize is behind a randomly-chosen door
;
prizedoor: random 3
;
; contestant (or team) randomly guesses a door
;
guessdoor: random 3
;
; Monty opens a non-prize, non-guessed door
;
until [
montydoor: random 3
all [montydoor <> prizedoor montydoor <> guessdoor]
]
;
; which strategy won on this round?
;
either guessdoor = prizedoor [
keepwins: keepwins + 1
][
switchwins: switchwins + 1
]
]
print [
"Keep won" keepwins "rounds,"
"switch won" switchwins "rounds"
]
]
8<------------------------------------------------------------
Having started with a painfully explicit (but obviously valid --
I hope!) function, let't start compacting and refactoring. I'll
save my typing time and your bandwidth and reading time by
omitting the comments from here on...
Step 1: Since KEEPWINS + SWITCHWINS is always equal to rounds
played thus far, we don't need both variables. Let's
eliminate SWITCHWINS throughout the code.
8<------------------------------------------------------------
pickadoor: function [
rounds [integer!]
][
prizedoor guessdoor montydoor keepwins
][
keepwins: 0
loop rounds [
prizedoor: random 3
guessdoor: random 3
until [
montydoor: random 3
all [montydoor <> prizedoor montydoor <> guessdoor]
]
if guessdoor = prizedoor [
keepwins: keepwins + 1
]
]
print [
"Keep won" keepwins "rounds,"
"switch won" rounds - keepwins "rounds"
]
]
8<------------------------------------------------------------
Step 2: Since KEEPWINS only depends on the values of GUESSDOOR
and PRIZEDOOR (but *not* on MONTYDOOR), we can eliminate
MONTYDOOR from the code.
8<------------------------------------------------------------
pickadoor: function [
rounds [integer!]
][
prizedoor guessdoor keepwins
][
keepwins: 0
loop rounds [
prizedoor: random 3
guessdoor: random 3
if guessdoor = prizedoor [
keepwins: keepwins + 1
]
]
print [
"Keep won" keepwins "rounds,"
"switch won" rounds - keepwins "rounds"
]
]
8<------------------------------------------------------------
Step 3: The variables PRIZEDOOR and GUESSDOOR are set to a new
value once per loop, and then examined exactly once per
loop; therefore, we can eliminate the variables by using their
defining expressions instead of their (single) usage.
8<------------------------------------------------------------
pickadoor: function [
rounds [integer!]
][
keepwins
][
keepwins: 0
loop rounds [
if (random 3) = random 3 [
keepwins: keepwins + 1
]
]
print [
"Keep won" keepwins "rounds,"
"switch won" rounds - keepwins "rounds"
]
]
8<------------------------------------------------------------
At this point, a symmetry argument should suffice to persuade
that the output converges to 1/3 and 2/3 (assuming that the
PRNG is valid).
Step 4: Apply symmetry; the choice of 3 is irrelevant.
8<------------------------------------------------------------
pickadoor: function [
rounds [integer!]
][
keepwins
][
keepwins: 0
loop rounds [
if 3 = random 3 [
keepwins: keepwins + 1
]
]
print [
"Keep won" keepwins "rounds,"
"switch won" rounds - keepwins "rounds"
]
]
8<------------------------------------------------------------
Step 5: Just for fun, let's get dense! Compacting words to
one-letter names, pruning constant output strings, and
eschewing layout whitespace...
8<------------------------------------------------------------
REBOL []p: function [n][k r][k: 0
loop n[if 3 = r 3[k: k + 1]]print[k n - k]]
8<------------------------------------------------------------
Step 6: If we're willing to pollute the global namespace,
forego the function, and type the one-liner into the
interactive console each time...
8<------------------------------------------------------------
n: 10000 k: 0 loop n[if 3 = random 3[k: k + 1]]print[k n - k]
8<------------------------------------------------------------
But, IMHO, the persuasion is in the process by which we arrived
at the last version (or maybe a version or two before that... ;-)
and not in its raw output.
-jn-
PS: As I've mentioned before, I have a random process that picks
the sigs on this box. The resonance between topic and the
randomly chosen sig per message has been *really* freaky today!
--
If you think big enough, you'll never have to do it.
-- Reisner's Rule of Conceptual Intertia
joel:FIX:PUNCTUATION:dot:neely:at:fedex:dot:com