NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/rec/puzzles/7288

Text File | 1992-11-15 | 7.6 KB | 185 lines

Newsgroups: rec.puzzles
Path: sparky!uunet!decwrl!cache.crc.ricoh.com!james
From: [e-mail] (James Allen)
Subject: Re: New Deal Puzzle
Message-ID: <[e-mail]>
Summary: Spoiler for n < 6
Organization: RICOH California Research Center
References: <[e-mail]> <[e-mail]>
Date: Sun, 15 Nov 92 19:22:32 GMT
Lines: 173

In <[e-mail]> [e-mail] (RING, DAVID WAYNE) writes:
] [e-mail] (Jim Saxe) writes...
] >        * * * * * THE ITERATED MONTY HALL PUZZLE * * * * *
] >What are the Dealer's and Guesser's optimal strategies and probabilities
] >of winning?
]
] Great puzzle!

Yes it does seem a good problem.  But I wonder if it's tractable.

Let G(52) denote Saxe's game, and G(n) denote a similar game starting from
a smaller deck.  Without ambiguity, G(n) can also denote the Guesser's
probability of winning the n-card game when both players play optimally.
Let q_i denote the probability -- from Guesser's viewpoint -- that
the i'th card is the Ace of Spades.  Let Q = (q_1, q_2, ..., q_n).

Initially Q = ( 1/52, 1/52, 1/52, ... ) in G(52) but after the first turn
it will be (a permutation of) Q = ( 1/52, 0, 51/2600, 51/2600, 51/2600, ...).
Thus while G(52) becomes similar to G(51) after the first round, solution is
non-trivial since the probabilities are different.

G(3) = 2/3 = probability of Guesser's success in the original Monty Hall
problem, but I won't try to prove that!   :-)

] *** SPOILER ALERT ***
] ^L
]
] 1. It is always in his (the Guesser's) best interest to play till the end.

Yes.

] 2. She (the Dealer) can force the situation into the standard MH problem (or
] better) by the following strategy: Always expose the card he just moved away
] from, except at the beginning, or if he just moved away from the Aces of
] Spades, Clubs, or Diamonds. In those cases expose a random card from the rest.

Yes, although one relevant remark is missing from this proof.  Suppose that
Guesser knows that Dealer is playing this way, that Guesser thus learns where
those three Aces are, and that the final 4 unexposed cards comprise the three
Aces and a non-Ace.  He can pick the non-Ace and force her to expose one of
the 3 Aces.

But then, he will have to move his marker for the final round and she can
expose the non-Ace without giving anything new away!  In that case Guesser
wins with probability 1/2.  Guesser has misplayed -- he should have come
down to the 3 Aces and won 2/3 of the time.  (Dealer has also misplayed:
with care she can achieve G(n) < 2/3 for all n > 3).

Thus for all n > 1,
    1/2  <=  G(n)  <=  2/3

In fact,
        G(2) =  1/2
        G(3) =  2/3
        G(4) =  5/8
        G(5) = 19/30

It seems likely that G(n) converges; that is

    lim G(n) = some constant K
    n->infinity

Perhaps G(n) < K for n even and G(n) > K for n odd.  If indeed G(4) < K < G(5)
the "candidate" K = 1 - 1/e comes to mind, where e = 2.718281828459... , but
this is "off the wall" speculation.

] 3. He [the Guesser] can always force the SMHP (or better) by jumping around
] randomly until there are three cards left.
] Thus his probability of winning is 2/3

This "sounds" right.  A little effort is required to show where it fails.

When G(n) does reduce to three cards, it's right for Guesser to pick the
*least* probable card if possible -- call its probability p -- and then switch
again on the final round.  Guesser then wins with probability (1-p).

From this it might appear that the best Dealer can hope for is to finish
with a "balanced" Q = (1/3, 1/3, 1/3) probability mix and let Guesser win
2/3 of the time.  If Q is skewed Guesser can apparently do better than this
by picking some card with probability less than 1/3.  In view of the bound
found by Tom in "] 2." above G(n) = 2/3 thus sounds correct.

But this argument collapses as we see by examining G(4) in detail.

Let P denote the currently picked card, X another unexposed card, and O an
exposed card.  The game G(4) proceeds as follows:

        Move:    Card:    (a) (b) (c) (d)
        1 Guesser:     P   X   X   X
        1 Dealer:     P   X   X   O
        2 Guesser:     X   P   X   O

Due to symmetry, this is the only G(4) "opening" we need consider.
Initially Guesser thinks that Q = (1/4, 1/4, 1/4, 1/4) are the probabilities
and these become Q = (1/4, 3/8, 3/8, 0) after Dealer exposes card (d).
Guesser would like to "stay" with (a) -- which now has low probability --
and force Dealer to expose a high-probability card.  But the rules require
that Guesser switch cards or accept (a) as his final pick.  Dealer has
"stymied" the Guesser.

Hence Guesser will pick a card with 3/8 probability and, after he switches
again, win with 5/8 probability.  (At her second turn, if (b) is the Ace
of Spades Dealer should expose (a) at least a third of the time or Guesser
can profitably stick with (b) at his final turn.)

Thus Guesser's result, G(4) = 5/8, is worse than in G(3) because his marker
ends up on what becomes a low-probability card after the 4-card ending.

The 5-card solution, G(5) = 19/30, can also be found without too much trouble:

        Move:    Card:    (a) (b) (c) (d) (e)
        1 Guesser:     P   X   X   X   X
        1 Dealer:     P   X   X   X   O
        2 Guesser:     X   P   X   X   O
        2 Dealer (a):     O   P   X   X   O
        2 Dealer (d):     X   P   X   O   O

Again the first few moves can be stipulated without loss of generality,
but two Dealer plays must be considered at her second turn.  Let Dealer
expose card (a) with probabilities (0, m, n, n) for the case where the
Ace of Spades is at (a, b, c, d) respectively.  If Guesser knows the
values of 'm' and 'n', his knowledge (Q) after Dealer's first and
second plays is easily derived:

                          (a)       (b)        (c)    (d)    (e)
    after 1 Dlr (e): Q  = (1/5,      4/15,      4/15,  4/15,    0)
    after 2 Dlr (a): QA = (  0,     4m/15,     4n/15, 4n/15,    0)
    after 2 Dlr (d): QB = (1/5, (4-4m)/15, (8-8n)/15,     0,    0)

(I have used "unnormalized probabilities" where {qA_i} sum to the
probability that Dealer exposes (a) at his second turn and {qB_i}
sum to the probability that Dealer exposes (c) or (d).)

From the above discussion, since Guesser must move his marker or end the game
prematurely, his net probability of success (assuming he knows 'm' and 'n') is

    prob(n)   =   1 - min(4n/15, 4n/15) - min(1/5, (8-8n)/15)

or since Dealer will select 'n' optimally,

    G(5) = min prob(n), where the minimum is over 0 <= n <= 1

(Notice that 'm' becomes irrelevant.)  This can be rewritten

    G(5) = 1/30 * (24 - max_over_n(8n + min(0, 10 - 16n)))

and easily solved to reveal n = 5/8, G(5) = 19/30.  Guesser must also protect
against non-saddle-point play by Dealer; this is easily done.  The full
solution in English is:

    * Guesser's first and second plays are trivial; we name the
        selected cards (a) and (b) respectively.
    * Dealer's first play is also trivial: expose a random non-Ace
        and call it (e).
    * At her second turn when a "virgin card" -- (c) or (d) -- is the Ace
        of Spades, Dealer must expose card (a) 5/8 of the time and
        expose the other "virgin" -- (d) or (c) -- 3/8 of the time.
    * At his third turn if (a) has not been exposed, Guesser should
        pick (a) exactly half the time.
    * Dealer's third play is trivial.
    * Guesser switches at his fourth turn, ending the game.
    * Guesser wins with probability 19/30.

Note that Dealer will "stymie" the Guesser in at least one of the two
cases (both case when 0.25 < m < 0.625), but she still can't do as well as
she did in G(4).

One can tediously solve for any G(n) in a similar fashion (*very* tedious
without some good software) but it would be much nicer to get some insight
or simplifying theorem to cut through the tedium and get a closed-form
expression for G(n).  Help anyone?

James