wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A simple game
        
(Message started by: Jonathan_the_Red on Aug 5^th, 2002, 11:04am)

Title: A simple game
Post by Jonathan_the_Red on Aug 5^th, 2002, 11:04am

Alice and Bob are going to play a game, with the following rules:

Alice picks a probability p, 0 <= p < 0.5
Bob takes any finite number of counters B.
Alice takes any finite number of counters A.

These happen in sequence, so Bob chooses B knowing p, and Alice chooses A knowing p and B.

A series of rounds are then played. Each round, either Bob gives Alice a counter (probability p) or Alice gives Bob a counter (probability 1-p). The game terminates when one player is out of counters, and that player is the loser.

Whom does this game favor? Analyze and discuss probabilities.

(note: a mathematician friend of mine came up with this one)

Title: Re: NEW PROBLEM: A simple game
Post by tim on Aug 5^th, 2002, 10:23pm

Bob wins. I'm at work and hence don't have time to post the detailed math. The basic idea is that for p<0.5 there is always a finite chance that Bob will never run out of coins even if Alice has an infinite number, and Bob can choose B such that this chance is as close to 1 as he likes.

Title: Re: NEW PROBLEM: A simple game
Post by James Fingas on Aug 28^th, 2002, 1:51pm

No, Alice wins.

This is a non-zero-mean random walk. The mean and variance on such a walk both increase linearly with time. Alice chooses p so that the variance increases faster than the mean does.

To win, Alice just has to wait until the variance minus the mean is much larger than the number of chips Bob has, at which point Bob could start to run out of chips. She can easily choose enough counters so that she couldn't possibly run out of chips until a long time after that.

Although there is a finite chance that Bob never loses counters, Alice makes this chance small by choosing p quite near 0.5. Bob compensates by choosing a large number of counters B, but Alice trumps him by choosing a much larger number of counters A.

Title: Re: NEW PROBLEM: A simple game
Post by Chronos on Aug 28^th, 2002, 2:40pm

I don't know about that, James. When the variance is higher than the mean, that might mean that Bob will run out of counters, but it might also mean that he'll end up with twice the mean. The two probabilities should be similar, which means that the game is probably at most balanced. I'm inclined to believe tim's argument that Bob can win.

Title: Re: NEW PROBLEM: A simple game
Post by AlexH on Aug 28^th, 2002, 2:43pm

James: I think you are mixing variance and deviation. Yes the variance goes up linearly with the # of flips, but its deviation (i.e. the sqrt of the variance) which controls how far from the mean we can expect our walk to get.

Title: Re: NEW PROBLEM: A simple game
Post by James Fingas on Aug 29^th, 2002, 4:58am

Hmm, It looks like it's been too long since I've taken probability. I will have to concede defeat. Bob only has a finite chance of losing. He can adjust this chance. Alice can only win if Bob loses. And we all know that Alice will eventually lose if she doesn't win first.

Title: Re: NEW PROBLEM: A simple game
Post by Jonathan_the_Red on Aug 29^th, 2002, 2:49pm

One of the things I like about this puzzle is the counterintuitive result. Not only does Bob win, but the value he must choose for B to give himself a reasonable chance of winning is surprisingly low. For example, if Alice chooses p = 0.49, Bob only needs to take 40 chips to have about an 80% chance of winning, even if Alice chooses to take 40 billion chips.

So to continue the puzzle: what number of chips B must Bob choose in terms of p in order to give himself an N% chance of winning?

Title: Re: NEW PROBLEM: A simple game
Post by Jonathan_the_Red on Aug 29^th, 2002, 2:50pm

Followup puzzle: how many posts must I make to no longer be labeled a "newbie?"

Title: Re: NEW PROBLEM: A simple game
Post by william wu on Aug 29^th, 2002, 9:10pm

50 posts. 6 more and you'll be a "Junior Member"! :D

Number of posts required for various rankings (this Pavlovian system was built into YaBB, not invented by me):

50
100
250
500

I'd reply to your puzzle continuation if I had more time to think about it. Currently I'm a bit tied up; one of my EE professors wants me to explain to him how to pull off the 5 card trick using a 124 card deck. This is a person I will probably ask for a recommendation later. Yet another test.

Title: Re: NEW PROBLEM: A simple game
Post by Eric Yeh on Sep 3^rd, 2002, 3:55pm

I disagree! I throw all my chips on 51. ;) ;) ;)

Title: Re: NEW PROBLEM: A simple game
Post by Quetzycoatl on Jan 12^th, 2004, 1:17pm

on 08/29/02 at 14:49:11, Jonathan_the_Red wrote:

This seemed a little odd to me, so I wrote a little simulation and I found that if P = 49% and Bob takes 40 chips, Alice wins about 60% of the time if she takes 4000 chips.

If they both take just 40 chips then Bob wins about 67% of the time.

If Bob chooses a low number, what Alice picks definitely has a bearing on the outcome. But as Bob starts picking higher numbers ( >500) Alice's seems to be less relevant. Or perhaps her starting number needs to be rising at an exponential rate.

Title: Re: NEW PROBLEM: A simple game
Post by Eigenray on Mar 23^rd, 2005, 6:10pm

on 08/29/02 at 14:49:11, Jonathan_the_Red wrote:

So to continue the puzzle: what number of chips B must Bob choose in terms of p in order to give himself an N% chance of winning?

Okay, so this is a bit late, but it follows from the discussion in [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1102522052]Return to Origin[/link] that the probability of Bob losing when A=infinity is r^-B, where r=(1-p)/p > 1.
Moreover, the probability of Bob losing for arbitrary A,B can be computed explicitly using the same martingale r^S_n, with stopping time T=min {j: S_j=B or -A}.
P(Bob loses)=P(S_T=B)=(1-r^-A)/(r^B-r^-A).

If p=1/2 - d, for d small,
log r = log (1/2 + d )/(1/2 - d) = log (1 + 4d/(1-2d)) ~ 4d,
so given small e>0, Bob should take at least
B = log(1/e)/log r ~ log(1/e)/(4d)
counters to ensure that he loses with probability < e.

Title: Re: A simple game
Post by Noke Lieu on Mar 23^rd, 2005, 7:24pm

THis riddle made my brain tick into classroom mode. It seems like it could be translated quite well into a demonstration/investigation, as long as I haven't misread it... So to check that, is this an accurate portrayal?

Have a deck of suffled cards, including jokers. Have the counters too (probably around 30 for each).

Alice can pick upto two suits. If the card turned over is one of the those suits chosen, she gets one of Bob's counters.
If it isn't then he gets one of hers.

That can then be changed so she can pick upto 6 value of cards.

...right?

[edit]
Actually, cycling home it dawned on me that this is very almost roulette.
Consequently, it shouldn't come as a surprise that the bank nearly always wins.
[

Title: Re: A simple game
Post by titan on Oct 15^th, 2013, 2:48pm

- Bob gives counter with probability p n gets with the probability (1-p). Bob has B no. of counters n Alice has A at t=0.

- w.r.t. Bob: Mean= [(AC1)p+(-BC1)(1-p)]/2 = [(A+B)p - B]/2. Is it right?

- Deviation(s) for a random walk is sqrt of t. so, s^2=t.
i.e. x=y^2. Hence, s increases with time.

- distance from mean=s.
So, x=mean+ns where n is an integer. and say when at t=1, n=1, then at t=2 if n=-1. then, net n=0. so, we put n=0 is equation.
if x is > 0 , implies Alice wins.

Let say A=5, B=10, p=1/3. Then mean=-2.5.
Since p<1-p. So, probability of n being -ve is higher. So, x is -ve in this case. So, Bob wins.
But, if A was chosen such that mean was positive then, A can win once, bcoz sqrt of t keeps on increasing and n*sqrt of t keeps on decreasing!

Does this analysis make sense? Help please!