The old Google Groups will be going away soon, but your browser is incompatible with the new version.
A Recursive Game
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 31 Newer >

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Dec 9 2005, 9:55 am
Newsgroups: alt.math.recreational, sci.math
Date: Fri, 09 Dec 2005 14:55:45 GMT
Local: Fri, Dec 9 2005 9:55 am
Subject: A Recursive Game
Consider the following proposed casino game:

There are two glass boxes. Each glass box has a slot on the top that
permits the house to add folding money to the box, and a lid that can
optionally be locked or unlocked. At the start of the game, both boxes
are empty. The game consists of one or more rounds. At the start of each
round, the house sets up the boxes so that one box is locked and the
other is unlocked (outside of the view of the player, of course). Then
the player picks one of the two boxes and tries to open it.

- If the player picked the unlocked box, s/he wins the contents of the
box, and the game is over.
- If the played picked the locked box, then the house adds 1.00 USD to
the unlocked box, and the game goes on for one of more rounds, until the
user opens an unlocked box.

To illustrate, here is how the game could proceed. The boxes are labeled
A and B. A and B start off empty.

- In the first round, the player picks box A. Box A is locked, so the
house adds a dollar to the unlocked box B.
- Round 2 starts with A empty and B containing \$1.00. The player picks
box A again, and again, box A is locked. The house adds another dollar
to box B.
- Round 3 starts with A empty and B containing \$2.00. The player now
switched to box B, but now B is the locked box. The house adds a dollar
to the unlocked box, A.
- Round 4 starts with A holding \$1.00 and B holding \$2.00. The player
picks box B, but this time B is unlocked. The player wins the \$2.00 that
was in B, and the game is over.

In the highly unlikely event that some casino would want to offer this
game, they would need to charge a fee for playing this game. To
determine a reasonable fee, we need to know how what the player's
expected winnings would be, assuming that the player and house follow
optimal strategies.

Rounded to the nearest cent, how much can a player of this game expect
to win?

While determining the answer to this question, Maple might come in handy.

If you're more ambitious, you can try to find a closed form expression
for the player's expected winnings, but keep in mind that it is unlikely
that such an expression exists, and even if it does, it might take a
Mathematician of the caliber of Srinivasa Ramanujan to find it.

If you're really, *really* ambitious, consider generalizing this to
three or more boxes.

--
"All things extant in this world,
Gods of Heaven, gods of Earth,
Let everything be as it should be;
Thus shall it be!"
- Magical chant from "Magical Shopping Arcade Abenobashi"

"Drizzle, Drazzle, Drozzle, Drome,
Time for the this one to come home!"
- Mr. Lizard from "Tutor Turtle"

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 11:05 am
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 11:05:23 -0500
Local: Fri, Dec 9 2005 11:05 am
Subject: Re: A Recursive Game
On Fri, 09 Dec 2005 14:55:45 GMT, "Frank J. Lhota"

With 2 boxes, assuming that in each round, each of the 2 boxes is
equally likely to be locked, I can prove that the optimal strategy is
the strategy of "go for the money" -- meaning, always pick the box
with the most money.

With this strategy, the expectation for the player is exactly 2/3.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 11:35 am
Newsgroups: alt.math.recreational, sci.math
Date: Fri, 09 Dec 2005 16:35:41 GMT
Local: Fri, Dec 9 2005 11:35 am
Subject: Re: A Recursive Game

quasi wrote:
> With 2 boxes, assuming that in each round, each of the 2 boxes is
> equally likely to be locked, I can prove that the optimal strategy is
> the strategy of "go for the money" -- meaning, always pick the box
> with the most money.

> With this strategy, the expectation for the player is exactly 2/3.

> quasi

I guess I should have made this clearer, but the house is *not*
constrained to choosing which box to lock at random. The house can (and
will) use strategy in its weighing of which box to lock, and will seek
to minimize the player's winnings.

Although we cannot assume that each box is equally likely to be locked,
your analysis still proves something useful: that the player's expected
winnings are *at most* 2/3, since the house could obtain that result
with the very simple strategy of using a coin flip to determine which
box to lock. Using a more complex strategy, however, the house can do a
little better.

--
"All things extant in this world,
Gods of Heaven, gods of Earth,
Let everything be as it should be;
Thus shall it be!"
- Magical chant from "Magical Shopping Arcade Abenobashi"

"Drizzle, Drazzle, Drozzle, Drome,
Time for the this one to come home!"
- Mr. Lizard from "Tutor Turtle"

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 12:01 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 12:01:59 -0500
Local: Fri, Dec 9 2005 12:01 pm
Subject: Re: A Recursive Game

How about the following revision to the rules ...

Suppose the house can choose the box to lock, potentially with a mixed
strategy. The strategically optimal probabilities used by the house to
choose a box can (and almost certainly will) depend on the contents of
the pair of boxes. Similarly the optimal strategy for  the player will
presumably need to be a mixed strategy as a function of the position,
so as to defend against possible non-optimal house play.

But now it's a game since both sides have a choice of strategies.

For simplicity, assume 2 boxes.

Solve the game. What are the optimal strategies? What is the value of
the game?

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 12:10 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 12:10:57 -0500
Local: Fri, Dec 9 2005 12:10 pm
Subject: Re: A Recursive Game

Ok, from your other reply, I see that you intended the house to be
able to play strategically.

So now there's a game to be solved.

I have a little time to play with it, but now the game looks hard.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 1:26 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 13:26:38 -0500
Local: Fri, Dec 9 2005 1:26 pm
Subject: Re: A Recursive Game
On Fri, 09 Dec 2005 16:35:41 GMT, "Frank J. Lhota"

As noted, it's clear that the house can hold the player to 2/3 by
choosing the boxes as equally likely.

There are 2 simple pure strategies for the house ...

(1) always lock the box with the least money, and if the boxes have
equal amounts, choose at random, 50-50.

(2)  always lock the box with the most money, and if the boxes have
equal amounts, choose at random, 50-50.

Strategy (1) is a disaster for the house, giving the player an
arbitrarily high expected return with correct play. Although, if we
take elapsed time into consideration, it's not that dramatic. If a
round takes 2 minutes, the player's expected return with optimal play
is only about \$30/hr (a little less).

Strategy (2) is better for the house, but still bad, giving the player
an expected return of 1 with optimal play (although the hourly rate of
return for the player drops to \$10/hr). Since we know the house can
hold the player to 2/3 with 50-50 play, strategy (2) is no good.

Next, consider some simple strategies for the player ...

If the player decides to always choose the box with the least money,
but 50-50 if the amounts are the same, the player is sure to get a
return of 0, Thus, we can quickly reject that strategy -- it's the
absolute worst.

Suppose the player decides to always choose the box with the most
money, but 50-50 if the amounts are the same. Then it's not hard to
show that with this strategy, the value of the game for the player is
exactly 1/2. While 1/2 is better than nothing, it's intuitive that the
player should be able to do better by a position-based mixed strategy.

In any case, based on the analysis so far, the actual value of the
game must be between 1/2 and 2/3.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 3:17 pm
Newsgroups: alt.math.recreational, sci.math
From: "Jules" <julianro...@gmail.com>
Date: 9 Dec 2005 12:17:45 -0800
Local: Fri, Dec 9 2005 3:17 pm
Subject: Re: A Recursive Game

Define f(n) to be the expected payout to the player, under optimal
strategies, given that one box currently contains \$0, and the other box
contains \$n.  Given that one box has \$0 and the other box has \$n, we
can easily solve for the optimal mixed strategy (in terms of f(n),
f(n+1), and f(n-1)), and this will lead to the following recursion:
f(n) = (1 + f(n - 1)) * f(n + 1) / (1 + f(n + 1) + f(n - 1) - n) when
n>0, and f(0) = f(1) / 2.  We can also say that as f(n) >= n, and f(n)
- n approaches 0 as n --> infinity.  I'm not sure where to go from
here, though.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 7:05 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 19:05:46 -0500
Local: Fri, Dec 9 2005 7:05 pm
Subject: Re: A Recursive Game
On 9 Dec 2005 12:17:45 -0800, "Jules" <julianro...@gmail.com> wrote:

Nice recursion.

I did essentially the same thing -- the key idea being to reduce to
from the state (\$a, \$b) where a<=b to the state (\$0, \$n) where n=b-a
(but make sure to pay the \$(b-a)).

To use the recursion you obtained, you should solve for f(n+1) in
terms of the previous values.

In fact, I recommend shifting the terms down one, solving for f(n) in
terms of f(n-1) and f(n-2).

But in my opinion, you will do better with a recursion for p(n), where
p(n) is the probability that the house locks the empty box when the
state is (\$0,\$n). You can get a recursion on the p's in essentially
the same way as you did for the f's.

The values of f can also be expressed in terms of the p's.

You can easily prove p(0)=1/2, so all you need is p(1) to start the
recursion.

It's clear that the values of p should be monotonically increasing,
and of course, since they are probabilities, they can't exceed 1, so
you can search numerically for the values of p(1) that maintain these
restrictions.

You can also check that any value of p(1) being tested maintains the
known restrictions on the f's.

As a starter, check that the inequalities n < f(n) <= n + 2/3 are
satisfied, and you can replace 2/3 by any known upper bound on f(0).

As a stronger requirement, check that for the given value of p(1), the
value of f(n)-n appears to approaches 0. In fact, I think you can also
require that f(n)-n is monotonically decreasing, and perhaps the
recursion could be used to prove this, but I'm not sure about the
monotonicity.

Reject any p(1) which fails to satisfy any of the known requirements.

Once you have p(1) to sufficient accuracy, you can calculate f(0)
which is the value of the game.

Additionally you can generate as many p's as needed to for the house
to actually play the game.

Finally, letting q(n) be the probability that the player should select
the empty box, you can also get a recursion for the q's in terms of
the f's (or the p's) and hence also determine the optimal strategy for
the player.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 7:07 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 19:07:07 -0500
Local: Fri, Dec 9 2005 7:07 pm
Subject: Re: A Recursive Game

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 7:36 pm
Newsgroups: alt.math.recreational, sci.math
From: "ronaldo" <ronald.schro...@hotmail.com>
Date: 9 Dec 2005 16:36:32 -0800
Local: Fri, Dec 9 2005 7:36 pm
Subject: Re: A Recursive Game
Have you considered sampling a large number of random plays to see what

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 8:07 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 20:07:08 -0500
Local: Fri, Dec 9 2005 8:07 pm
Subject: Re: A Recursive Game
On 9 Dec 2005 16:36:32 -0800, "ronaldo" <ronald.schro...@hotmail.com>
wrote:

>Have you considered sampling a large number of random plays to see what

Better first to solve for or at least hypothesize the optimal
strategies.

With both strategies unknown, a simulation would be cumbersome -- it
could be done, but for this problem we can do better than that. The
fact is, we have known recursive relationships which make it possible
to express all the unknown data in terms of a single unknown parameter
-- in other words, only one degree of freedom. Based on that, a
numerical solution should be relatively straightforward.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 9:10 pm
Newsgroups: alt.math.recreational, sci.math
From: "ronaldo" <ronald.schro...@hotmail.com>
Date: 9 Dec 2005 18:10:59 -0800
Local: Fri, Dec 9 2005 9:10 pm
Subject: Re: A Recursive Game
quasi wrote:
>a numerical solution should be relatively straightforward.

But that *is* what you asked for. Rounded to the nearest cent.

OK seriously now.
Assuming both player and house to play optimally this will include
trying to outguess the other party. The only defense against this is
random play, isn't it?

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 9 2005, 10:26 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Fri, 09 Dec 2005 22:26:19 -0500
Local: Fri, Dec 9 2005 10:26 pm
Subject: Re: A Recursive Game
On 9 Dec 2005 18:10:59 -0800, "ronaldo" <ronald.schro...@hotmail.com>
wrote:

>quasi wrote:
>>a numerical solution should be relatively straightforward.
>But that *is* what you asked for. Rounded to the nearest cent.

>OK seriously now.
>Assuming both player and house to play optimally this will include
>trying to outguess the other party. The only defense against this is
>random play, isn't it?

Yes, that's what's meant by a mixed strategy. Such a strategy will
specify probabilities for choices in certain situations. The
probabilities are optimized to the situation in such a way that no
other set of probabilities can guarantee a better result.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 10 2005, 11:21 am
Newsgroups: alt.math.recreational, sci.math
From: Henry <s...@btinternet.com>
Date: Sat, 10 Dec 2005 16:21:29 +0000 (UTC)
Local: Sat, Dec 10 2005 11:21 am
Subject: Re: A Recursive Game

On Fri, 09 Dec 2005 20:07:08 -0500, quasi <qu...@null.set> wrote:
>With both strategies unknown, a simulation would be cumbersome -- it
>could be done, but for this problem we can do better than that. The
>fact is, we have known recursive relationships which make it possible
>to express all the unknown data in terms of a single unknown parameter
>-- in other words, only one degree of freedom. Based on that, a
>numerical solution should be relatively straightforward.

It certainly looks like that, but it does not seem to be so easy in
practice - I found myself trying to solve several simultaneous
quadratic equations.  Some experimention also suggested my approach
was ill conditioned - my best effort came up with a final result close
to 5/8 but the actual optimal mixed strategies seemed to be difficult
to pin down precisely (beyond the fact that the guesser will tend to
pick the higher value box more often, and the locker will usually lock
that box).

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 10 2005, 12:13 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Sat, 10 Dec 2005 12:13:51 -0500
Local: Sat, Dec 10 2005 12:13 pm
Subject: Re: A Recursive Game
On Sat, 10 Dec 2005 16:21:29 +0000 (UTC), Henry <s...@btinternet.com>
wrote:

Unfortunately, I have no time to play right now -- for the next 2
weeks, my free time is zero. However it would be fun to find the
optimal strategies more accurately, so if it's not resolved in 2
weeks, I'll play with it then.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 10 2005, 10:12 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Sat, 10 Dec 2005 22:12:38 -0500
Local: Sat, Dec 10 2005 10:12 pm
Subject: Re: A Recursive Game

The problem teased me, so I did a little work on it.

Firstly, it can be proved that the optimal strategies are unique, and
are mixed in all states.

Let v[n] be the value of the game in state (\$0,\$n).

Let p[n] be the probability that in state (\$0,\$n), the house locks the
empty box (assuming the house plays optimally).

Let q[n] be the probability that in state (\$0,\$n), the player chooses
the empty box (assuming the player plays optimally).

Based on the known recursive relationships previously discussed, the
following can be proved:

p[n]=q[n] for all n.

p[0]=1/2

The sequence p[n] is strictly increasing,
and approaches a limit of 1, as n approaches infinity.

Moreover, p[n] > n/(n+1) for all n, and the difference p[n] - n/(n+1)
decreases monotonically with a limit of 0.

n < v[n] < n + v[0] for all n.

The sequence v[n] - n is strictly decreasing, approaching a limit of 0
as n approaches infinity.

Based on the above restrictions, it can be proved that the value of
the game, v[0], satisfies:

0.6245354 < v[0] < 0.6245367

The first few probabilities of the optimal strategy, p[0], p[1], p[2],
p[3] satisfy

p[0] = 1/2

0.601186 < p[1] < 0.601190

0.68812 < p[2] < 0.68818

0.751 < p[3] < 0.755

With more work, these probabilities can be approximated to greater
accuracy and also get approximations for other values of p[n], n>3.

However it can be shown that the probabilities p[4], p[5], p[6], ...
have insignificant affect on the expected return.

Similarly, the lack of perfect accuracy in the probabilities p[1],
p[2], p[3] is also not significant.

Thus, to actually play this game, each side should choose p[0]=1/2,
and then choose probabilities p[1], p[2], p[3] consistent with the
above inequalities. After n=3, any probabilities are ok, even a fixed
strategy (since once n>3, there's not enough to gain by mixing).

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 12 2005, 11:48 am
Newsgroups: alt.math.recreational, sci.math
Date: Mon, 12 Dec 2005 16:48:52 GMT
Local: Mon, Dec 12 2005 11:48 am
Subject: Re: A Recursive Game

quasi wrote:
> On Sat, 10 Dec 2005 12:13:51 -0500, quasi <qu...@null.set> wrote:
> The problem teased me, so I did a little work on it.

I'm glad you enjoyed working on it. After all, problems like this exist
for our amusement. :)

> Firstly, it can be proved that the optimal strategies are unique, and
> are mixed in all states.

> Let v[n] be the value of the game in state (\$0,\$n).

> Let p[n] be the probability that in state (\$0,\$n), the house locks the
> empty box (assuming the house plays optimally).

> Let q[n] be the probability that in state (\$0,\$n), the player chooses
> the empty box (assuming the player plays optimally).

Are you sure that you didn't mean to say "... the player chooses the \$n
box..."?

Good work! My solution was basically along these lines, although I did
not do as much analysis on p[n], q[n] as you have. Sharing puzzles like
this on the newsgroups is quite enlightening, since it exposes one to
different approaches to a problem. Thanks for sharing your solution.

--
"All things extant in this world,
Gods of Heaven, gods of Earth,
Let everything be as it should be;
Thus shall it be!"
- Magical chant from "Magical Shopping Arcade Abenobashi"

"Drizzle, Drazzle, Drozzle, Drome,
Time for the this one to come home!"
- Mr. Lizard from "Tutor Turtle"

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 13 2005, 12:10 am
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Tue, 13 Dec 2005 00:10:19 -0500
Local: Tues, Dec 13 2005 12:10 am
Subject: Re: A Recursive Game
On Mon, 12 Dec 2005 16:48:52 GMT, "Frank J. Lhota"

No, I meant it as I said it.

Does that not agree with your analysis?

>> Based on the known recursive relationships previously discussed, the
>> following can be proved:

>> p[n]=q[n] for all n.

The equality of p and q was surprising, but follows directly from the
recursive relationships.

Thanks for the problem -- it was fun.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 13 2005, 11:39 am
Newsgroups: alt.math.recreational, sci.math
From: s...@btinternet.com
Date: 13 Dec 2005 08:39:31 -0800
Local: Tues, Dec 13 2005 11:39 am
Subject: Re: A Recursive Game

No - it looks very strange.  If q[n] is high, then the player is
usually choosing the empty box, so it would make sense for the house to
always unlock the empty(/lower value) box.  In fact, using your
definition of q[n], it tends to 0 quickly as n increases

The game analysis is to find the minimax solution (n>0) for
v[n] = p[n]*q[n]*v[n+1] + p[n]*(1-q[n])*n +
(1-p[n])*(1-q[n])*(1+v[n-1])

This results in solutions for n>0 of
v[n] = p[n] * v[n+1]
v[n] = q[n] * v[n+1]  +  (1-q[n]) * n
v[n] = p[n] * n  +  (1-p[n]) * (1+v[n-1])
v[n] = (1-q[n]) * (1+v[n-1])
and looking at the first and second, or third and fourth, p[n] and q[n]
are clearly different

My approximate results (based on yours) include
v[0] = 0.62454
v[1] = 1.24908
v[2] = 2.07767
p[1] = 0.60119
q[1] = 0.23112

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 13 2005, 10:24 pm
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Tue, 13 Dec 2005 22:24:32 -0500
Local: Tues, Dec 13 2005 10:24 pm
Subject: Re: A Recursive Game
On 13 Dec 2005 08:39:31 -0800, s...@btinternet.com wrote:

hmm ...

I see your point both logically and mathematically, so it seems like I
must have made an error somewhere.

Ok, I see my error.

I had the correct recursive form for the p's, but the wrong one for
the q's.

On checking my work, I think now that all the claims are correct
except the claim that q[n]=p[n].

I think that you're right that they go in opposite directions, and
that as n approaches infinity, while p[n] increases and approaches 1,
q[n] decreases and approaches 0.

My revised (hopefully correct) recursive relationships are these:

v[n] = p[n]*v[n+1]

v[n] = p[n]*(n)+(1-p[n])*(1+v[n-1])

v[n] = q[n]*v[n+1]+(1-q[n])*n

v[n] = (1-q[n])*(1+v[n-1])

and

p[0] = q[0] = 1/2.

Calculating q[1], q[2], q[3] based on the above, it seems apparent
that the sequence q[n] decreases very rapidly -- q[n] appears to
approach zero much faster that p[n] approaches 1. Also, the value I
get for q[1] matches yours.

When I get a chance, I'll calculate the values of q with more
accuracy, but for now, except for q[0]=1/2 which is exact, here are
some rough calculations:

q[1] = 0.23112
q[2] = 0.0762
q[3] = 0.019

In the meantime, forgetting about the math, which seems to validate
your objection, try this logic ...

Suppose the state is (\$0,\$n), where n>0.

If you know the house is going to lock the empty box, then you always
want to select it.

Similarly, if you know the house going to lock the nonempty box, then
you always want to select that.

So this suggests that as p[n] approaches 1, q[n] approaches 1,

implied by the recursive forms, so it's an apparent paradox.

Perhaps it's just an illustration that a fixed strategy is no good for
either player -- that the balance is in the mix. Or maybe there's
still an error somewhere in the analysis. What do you think?

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 14 2005, 3:30 am
Newsgroups: alt.math.recreational, sci.math
From: Henry <s...@btinternet.com>
Date: Wed, 14 Dec 2005 08:30:18 +0000 (UTC)
Local: Wed, Dec 14 2005 3:30 am
Subject: Re: A Recursive Game

These look the same as those I wrote below yesterday

What this actually does is explain why there is a mixed strategy:

House decides to unlock empty box
Player knows this so decides to choose full box
House knows this so changes mind and decides to unlock full box
Player knows this so changes mind and decides to choose empty box
House knows this so changes mind and decides to unlock empty box
Player knows this so changes mind and decides to choose full box
...
House and Player collapse in heap and look for better mixed strategies

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 14 2005, 4:55 am
Newsgroups: alt.math.recreational, sci.math
From: s...@btinternet.com
Date: 14 Dec 2005 01:55:49 -0800
Local: Wed, Dec 14 2005 4:55 am
Subject: Re: A Recursive Game

Henry wrote:
> What this actually does is explain why there is a mixed strategy:

> House decides to unlock empty box
> Player knows this so decides to choose full box
> House knows this so changes mind and decides to unlock full box
> Player knows this so changes mind and decides to choose empty box
> House knows this so changes mind and decides to unlock empty box
> Player knows this so changes mind and decides to choose full box
> ...
> House and Player collapse in heap and look for better mixed strategies

Sorry - I meant to go on:

For the Player, choosing the empty box when it is unlocked is a very
bad result for high n, and so the chance of this needs to be low
(though not 0).  For the House, the other three of the outcomes are
more similarly bad (though not identical) for high n, and so q falls to
0 more quickly than p rises to 1 as n increases.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 14 2005, 10:21 am
Newsgroups: alt.math.recreational, sci.math
From: quasi <qu...@null.set>
Date: Wed, 14 Dec 2005 10:21:25 -0500
Local: Wed, Dec 14 2005 10:21 am
Subject: Re: A Recursive Game
On 14 Dec 2005 01:55:49 -0800, s...@btinternet.com wrote:

Yes -- that explains it in a way that makes the intuition agree with
the math.

quasi

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 15 2005, 9:30 am
Newsgroups: alt.math.recreational, sci.math
From: s...@btinternet.com
Date: 15 Dec 2005 06:30:14 -0800
Local: Thurs, Dec 15 2005 9:30 am
Subject: Re: A Recursive Game

quasi wrote:
> Yes -- that explains it in a way that makes the intuition agree with
> the math.

v[0] is 0.62453572058294332938468293828432119587938741061271189... and
this is enough to derive the early values of v[n] from v[1]=2*v[0] and
v[n+1] = v[n] * (1+v[n-1]-n) / (1+v[n-1]-v[n])
This gives initial values of about
v[0] = 0.62453572
v[1] = 1.24907144
v[2] = 2.07766697
v[3] = 3.01910160
v[4] = 4.00380771
v[5] = 5.00063426
v[6] = 6.00009060
v[7] = 7.00001133
v[8] = 8.00000126
v[9] = 9.00000013
v[10] = 10.00000001
and for large n we have v[n] about n + 0.456628.../(n+1)!

p[n] is simply v[n]/v[n+1] and q[n] is simply =(v[n]-n)/(v[n+1]-n)

Henry

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 15 2005, 1:37 pm
Newsgroups: alt.math.recreational, sci.math
Date: Thu, 15 Dec 2005 18:37:59 GMT
Local: Thurs, Dec 15 2005 1:37 pm
Subject: Re: A Recursive Game

s...@btinternet.com wrote:
> v[0] is 0.62453572058294332938468293828432119587938741061271189... and
> this is enough to derive the early values of v[n] from v[1]=2*v[0] and
> v[n+1] = v[n] * (1+v[n-1]-n) / (1+v[n-1]-v[n])

Wow! How did you compute v[0] to 53 places?

--
"All things extant in this world,
Gods of Heaven, gods of Earth,
Let everything be as it should be;
Thus shall it be!"
- Magical chant from "Magical Shopping Arcade Abenobashi"

"Drizzle, Drazzle, Drozzle, Drome,
Time for the this one to come home!"
- Mr. Lizard from "Tutor Turtle"