• 0
Sign in to follow this  
Followers 0

A Game of Probabilities

Question

Posted · Report post

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

0

Share this post


Link to post
Share on other sites

18 answers to this question

  • 0

Posted (edited) · Report post

not related in any way to a game on this site ???

:D

wd Y-san .. u did it ... ;)

edit... added spoiler

Edited by Yodell
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

I guess neither of us knows which objects have property M, and we rely on a third party to give us a determination at the end of each N phase or the STOP event?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

I guess neither of us knows which objects have property M, and we rely on a third party to give us a determination at the end of each N phase or the STOP event?

Yes, or they could be, like, upside down cards or mahjong tiles or something like that that we shuffled.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Or beakers of acid/base we test with litmus paper...or glasses of pepsi/coke we taste test...but not beakers of acid/base that we taste test...

(sorry, couldn't resist ;P)

1

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

I think the second player could choose one of the cards chosen by the first player, as the first player's choices are secret.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

The game seems simply to determine when to say Stop.

Seems that 2 draws puts your winning chances above 50%.

So I'm stopping after my 2nd draw.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

let me see if i have the riddle correct with an example.

let's say i have 12 playing cards, 4 of which are spades. all cards are over turned, so no one knows which is which.

player 1 chooses 1 card, and keeps it down turned.

then player 2 chooses 1 card. player 2's card is revealed. if it's a spade, he wins, else keep playing.

player 1 picks another card (assuming player 2 didn't win.) player 1 can call stop. if either of the two cards are spade, player 1 wins.

else, player 2 wins.

sound good?

Only possible difference is that player 2 [i think] doesn't know which card player 1 has chosen.

E.g. P2 might choose one of them herself, and thus can 'steal' some of p1's chances.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Yes, your choice is secret, and the object (beaker/tile/card) is not removed from the selection process.

And if I choose your card, your chances for stopping the second round aren't as good. ;)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

The game seems simply to determine when to say Stop.

Seems that 2 draws puts your winning chances above 50%. 

So I'm stopping after my 2nd draw.

Generalizing to j and k,

I would compute player 2's chances with player 1 being silent.

On the turn the it exceeds 50%, I would say stop.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

You and I are playing a little game (that is in no way whatsoever related to any game played on this site *cough*). There are 12 objects, 4 of which have the property M. The goal is to choose an object with the property M.

However, you and I are playing by different rules. For each round, first there is the N phase, in which you secretly choose an object (write down its number or something), then there is the D phase, during which I pick an object and it is revealed whether or not the object has property M.

If the object I pick has the property M, I win, if not we keep going. During any N phase, after you choose an object, you can call 'STOP' and the game will end. Then you reveal your choices, and if at least one has the property M, you win. If none have the property M, I win.

What is your play?

Bonus: Generalize to a case of n objects, k of which have the property M.

Here's an approximative strategy,

At every point of the game, we can summarize the current state of the game with the number of remaining objects (R), the number of unopened chosen objects (c), and the k number of objects with property M.

We define a function for the probability of winning at state (R, c, k) as

post-14842-0-81798300-1340501484_thumb.p

The strategy now is as follows,

1) At the beginning of N phase (before we choose an object), we calculate the chance we would win if we were to call stop at that N phase. Call this S0, which is defined as

S0 = W( R, c + 1, k )

2) We then calculate the chance we would win if we go through one more round and then stop at the next N phase. Call this S1, which is defined as

S1 = ( 1 - k/R ) * [ [ ( c + 1 )/R ] * W( R - 1, c + 1, k ) + [ 1 - (c+1)/R ]* W( R - 1, c + 2, k ) ]

3) If S1 > S0, then continue the game. Otherwise, stop the game.

Back to the example where R = 12 and k = 4. At the first turn where c = 0, which means the game state is (12, 0, 4), we get

S0 = .3333

S1 = .398

Which means that we should continue the game. If the opponent does not win the game during next turn, then there are two possible next states, which are

(11, 1, 4) - The opponent did not open your chosen door - The strategy above says that we should stop at this N phase.

(11, 0, 4) - The opponent did open your chosen door (essentially a new game with R = 11) - The strategy above says we should continue the game.

Continue until the strategy calls for a stop.

Edited by bushindo
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Excellent, thank you Bushindo :)

I thought there might be multiple ways of looking at the problem, but felt that the differential method was the best, although I have no idea how to prove it. It makes a 'profit=marginal cost' kind of sense.

And yes, one of the key aspects, I think, is that the probabilities change each round, after you get information (that is, whether I choose your object). I.e., for the mth round, you calculate the probability you win if you stop at the (m+1)th round taking into account the probability that I choose your object, but during the (m+1)th round, you know whether I chose your card or not.

The other possible way I can see for looking at the problem is to assume an infinitely large n, such that at the stopping point, P(winning if you go one more round)=P(winning if you 'STOP' now), and working backwards.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

The best strategy for N is to yell STOP only and as soon as he or she recieves something with property M because the payoff for losing is symmetrical to both ways of losing (D draws M or N calls STOP holding only not-M). It always pays to go another round after drawing not-M. It might be a more interesting game if there were different payoffs, though. What if it cost more to lose from D drawing M than from yelling STOP while only holding not-M? If that were the case, there would be a point at which it becomes more costly to continue playing. The payoff matrix would be based on the notion that k/(n-x) is the probability of winning the next round {where x is the number of the round, k is the number of objects with M, and n is the total number of objects}. I decided not to keep going and calculate the whole payoff because I need a function which is 0 when x is odd and 1 when x is even, and I'm a little too lazy for that.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Oh, I was assuming that the choice was only secret for D, but N knows what he or she draws. Those are two different games.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Consider the decision tree.

You can calculate the probability that you will win, when you predetermine on which round you will say STOP (if you survive until that round).

The first round probability is 4/12=0.33

Second is 0.397979...

This increases, until some round to say STOP where the probability of winning will begin to drop.

Obviously the "general solution" is to say STOP on the round that produces the overall highest probability of winning relative to the beginning of the decision tree.

My solution would be a computation, rather than a calculation. There are multiple ways of presenting it, but none of them would look nice.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

The best strategy for N is to yell STOP only and as soon as he or she recieves something with property M...

You can't say STOP after they've already won.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Some people are arguing that it's best for N to go 2 rounds because then he or she has over a 50% chance of winning. The problem is allowing round 2 gives D a 31.8% of winning. That means letting the game reach round 2 only gives N a 1.2% net advantage for allowing it vs. a 33% advantage for calling STOP after the first draw. I'd say N's best strategy is to call STOP after the first draw.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

You can't say STOP after they've already won.

Of course not, but it doesn't matter. If N knows what he or she draws, then the only reason to continue the game is if he or she draws not-M. Calling STOP at this point would ensure a loss. Continuing gives a chance of victory and a chance of loss. So clearly it's better to allow another round. This logic continues until k=n, at which point whoever draws next wins.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.