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"
<NOSPAM.lh...@adarose.com> wrote: >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.
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 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"
On Fri, 09 Dec 2005 11:05:23 -0500, quasi <qu...@null.set> wrote: >On Fri, 09 Dec 2005 14:55:45 GMT, "Frank J. Lhota" ><NOSPAM.lh...@adarose.com> wrote:
>>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.
>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
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?
On Fri, 09 Dec 2005 12:01:59 -0500, quasi <qu...@null.set> wrote: >On Fri, 09 Dec 2005 11:05:23 -0500, quasi <qu...@null.set> wrote:
>>On Fri, 09 Dec 2005 14:55:45 GMT, "Frank J. Lhota" >><NOSPAM.lh...@adarose.com> wrote:
>>>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.
>>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
>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
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.
<NOSPAM.lh...@adarose.com> wrote: >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.
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.
Frank J. Lhota wrote: > 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.
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.
>Frank J. Lhota wrote: >> 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.
>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.
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.
On Fri, 09 Dec 2005 19:05:46 -0500, quasi <qu...@null.set> wrote: >On 9 Dec 2005 12:17:45 -0800, "Jules" <julianro...@gmail.com> wrote:
>>Frank J. Lhota wrote: >>> 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.
>>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.
>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.
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 >it leads to?
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 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?
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.
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).
>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).
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.
On Sat, 10 Dec 2005 12:13:51 -0500, quasi <qu...@null.set> wrote: >On Sat, 10 Dec 2005 16:21:29 +0000 (UTC), Henry <s...@btinternet.com> >wrote:
>>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).
>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
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).
> 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
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"
<NOSPAM.lh...@adarose.com> wrote: >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..."?
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.
>> 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
>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.
quasi wrote: > On Mon, 12 Dec 2005 16:48:52 GMT, "Frank J. Lhota" > <NOSPAM.lh...@adarose.com> wrote:
> >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..."?
> 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.
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
> >> 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
> >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.
>> On Mon, 12 Dec 2005 16:48:52 GMT, "Frank J. Lhota" >> <NOSPAM.lh...@adarose.com> wrote:
>> >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..."?
>> 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.
>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
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,
The above logic contradicts yours, and contradicts the values of q 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?
>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
>> >> 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).
On Tue, 13 Dec 2005 22:24:32 -0500, quasi <qu...@null.set> wrote: >On 13 Dec 2005 08:39:31 -0800, s...@btinternet.com wrote:
>>quasi wrote:
>>> On Mon, 12 Dec 2005 16:48:52 GMT, "Frank J. Lhota" >>> <NOSPAM.lh...@adarose.com> wrote:
>>> >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..."?
>>> 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.
>>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
>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])
These look the same as those I wrote below yesterday
>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,
>The above logic contradicts yours, and contradicts the values of q >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?
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
>>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
>>> >> 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).
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.
>> 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.
Yes -- that explains it in a way that makes the intuition agree with the math.
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)
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])
> 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
-- "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"
