From: potamian@apollo.HP.COM (Spyros Potamianos)
Subject: Re: Monte Hall II
Date: Fri, 18 Dec 1992 22:18:43 GMT
Reply-To: potamian@hpl.hp.com
Organization: Hewlett-Packard Company, Chelmsford, MA

In article <Dec.18.06.50.20.1992.23923@romulus.rutgers.edu>, clong@romulus.rutgers.edu (Chris Long) writes:
|> 
|> There are three doors, behind one of which is a good prize and behind
|> the other two are booby prizes (each door equally likely to have the
|> good prize).  You pick a door, and then of the two remaining doors
|> Monte picks one containing a booby prize and shows it to you, and
|> offers you the opportunity to switch.  We all know by now that if Monte
|> choose uniformly at random if there is more than one door with a booby
|> prize to choose from you should always switch and your probability of
|> winning is 2/3.
|> 
|> 1.  If doors A, B, and C (door A leftmost, door C rightmost) have the
|> probabilities a, b, c with a+b+c=1 of having the good prize behind
|> them, what is your best strategy?
|> 
|> 2.  If when Monte is faced with two empty doors instead of choosing
|> uniformly he chooses the leftmost door with probability p, the
|> rightmost with probability q and p+q=1, what is your best strategy
|> now?
|> 
|> 3.  What if both conditions hold?
|> -- 
|> Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
|> 
|> "S.B., with an I.Q. of 161, failed to complete his course of study,
|> running away instead with his professor's wife."
|> H. J. Eysenck, _Know Your Own I.Q._
----------------------------------------------------------------------------

Nice puzzle! Long live Monty!

Although both David Karr and Stein Kulseth have been faster in posting
(correct) answers, I decided to post this because
a) I wrote it and hate to just throw it away
b) it's a little bit more "formal" (hm... is that an advantage or
disadvantage?? :-)

Anyway, here it goes.....

----------------------------------------------------------------------------
Obviously a strategy consists of 2 steps:
    Step 1: choose a door (3 options here)
    Step 2: depending on which door Monty opens, decide whether
	    to switch or not. There are 4 options:
		a) always switch
		b) switch iff Monty opens leftmost door
		c) switch iff Monty opens rightmost door
		d) never switch

----------------------------------------------------------------------------
I claim that the "best" strategy is:
    a) choose the door with the *least* proability of being the
       one with the treasure
    b) always switch (no matter which door Monty opens)

Clarification: By "best" I mean a strategy that no matter what are the
probabilities a, b, c, p, q is no worse than any other.
Or, to rephrase that, in some cases there might be other strategies
that do equally well but not better. For example if a=1, b=c=0,
then the strategy: "always pick door A and don't switch" is as good
(but no better) than "pick B and switch".
----------------------------------------------------------------------------

To prove this claim I will prove the following lemmas:

Lemma A: (to be proven later)
--------
    Lets ignore "step 1" of the strategy for the time being, and choose
    a door at random. So, without loss of generality, let say that we
    choose door A.  Then:

    Monty opens			prob		switch		don't switch
    -----------			----		------		------------
    LEFTMOST (door B)		ap+c		c/(ap+c)	ap/(ap+c)
    RIGHTMOST (door C)		aq+b		b/(aq+b)	aq/(aq+b)

    where the first column shows which door Monty opens, the second
    the probability of this event, the third the probability of
    winning if you switch, and the fourth the probability of winning
    if you don't switch.

----------------------------------------------------------------------------

Lemma B:
--------
    As far as the second step of the strategy is concerned (still ignoring
    the first step...) then the probability of winning is:

    always	switch if Monty		switch if Monty		never
    switch	opens leftmost door	opens rightmost door	switch
    ------	-------------------	--------------------	------
    b+c =	aq+c			ap+b			ap+aq = a
    1-a
    
    (this follows easily from Lemma A)

----------------------------------------------------------------------------

Lemma C:
--------
    Given the table in Lemma B, then the best strategy for both steps,
    is to choose the door with the minimum probability i.e. MIN(a,b,c)
    and always switch.

    Proof:
    ------
    1) if you always switch, then the probability of winning is "1-a"
       (where "a" is the probability for the chosen door)
       which is obviously maximized by picking the door with the minimum
       probability. So, prob. of winning is:
 	   P1 = 1 - MIN(a,b,c)

    2) If you switch if and only if Monty opens the leftmost door,
       then the probability of winning is "aq + c"
       No matter what door you have chosen, you can not do better than
       case (1), because:
	   P2 = aq+c <= a+c = 1-b <= 1 - MIN(a,b,c) = P1

    3) Similarly to case (2) above,
	   P3 = ap+b <= P1
    
    4) If you never switch, then the probability of winning is "a"
       which is maximized by picking the door with the maximum
       probability. However:
	    P4 = MAX(a,b,c) <= 1-MIN(a,b,c) = P1
       so, again, this strategy is no better than (1)
    
----------------------------------------------------------------------------

Proof of Lemma A:
-----------------
    Assume that the probabilities of the treasure being behind
    the door you choose, the leftmost remaining door and the rightmost
    remaining door are "a", "b" and "c" respectively.

    There are 4 possible events:

    Event 1: you choose the right door, and monty opens the leftmost
	     remaining door
    Event 2: you choose the right door, and monty opens the rightmost
	     remaining door
    Event 3: you choose the wrong door, and the treasure is in the
	     leftmost remaining door. Obviously, in this case Monty
	     will be forced open the rightmost door.
    Event 4: you choose the wrong door, and the treasure is in the
	     rightmost remaining door. Obviously, in this case Monty
	     will be forced open the leftmost door.
    

    The following table summarizes the probabilities of these events,
    and shows what happens if you decide to switch doors

    Event:	Monty opens	Prob.	Switch
    -------	-----------	-----	------
    Event 1	leftmost	ap	Loose
    Event 2	rightmost	aq	Loose
    Event 3	rightmost	b	Win
    Event 4	leftmost	c	Win

    So, the probability of Monty opening the leftmost door is "ap+c"
    (the sum of the probabilities of the 1st and 4th row).
    In this case, if you switch you only win in the latter case
    (probability = "c") so :

    Prob. of winning if you switch *given* that Monty picked the leftmost
    door = "c/(ap+c)".
    Prob. of winning if you don't switch (given that blah blah blah...)
    is 	= "ap/(ap+c)"

    Similarly, the prob. that Monty opens the rightmost door is "aq+b"
    and given that, the probability of winning  if you switch is
    "b/(aq+b)", and if you don't "aq/(aq+b)"

----------------------------------------------------------------------------
Spyros Potamianos
potamian@hpl.hp.com
Newsgroups: rec.puzzles