wu :: forums
« wu :: forums - A simple game »

Welcome, Guest. Please Login or Register.
Sep 18th, 2018, 8:49am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Grimbal, Eigenray, SMQ, Icarus, william wu, towr)
   A simple game
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: A simple game  (Read 7198 times)
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
A simple game  
« on: Aug 5th, 2002, 11:04am »
Quote Quote Modify Modify

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)
« Last Edit: Nov 15th, 2003, 10:32am by Icarus » IP Logged

My arcade cabinet
tim
Junior Member
**





   


Posts: 81
Re: NEW PROBLEM: A simple game  
« Reply #1 on: Aug 5th, 2002, 10:23pm »
Quote Quote Modify Modify

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.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: A simple game  
« Reply #2 on: Aug 28th, 2002, 1:51pm »
Quote Quote Modify Modify

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: NEW PROBLEM: A simple game  
« Reply #3 on: Aug 28th, 2002, 2:40pm »
Quote Quote Modify Modify

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.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: NEW PROBLEM: A simple game  
« Reply #4 on: Aug 28th, 2002, 2:43pm »
Quote Quote Modify Modify

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.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: NEW PROBLEM: A simple game  
« Reply #5 on: Aug 29th, 2002, 4:58am »
Quote Quote Modify Modify

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: NEW PROBLEM: A simple game  
« Reply #6 on: Aug 29th, 2002, 2:49pm »
Quote Quote Modify Modify

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?
IP Logged

My arcade cabinet
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: NEW PROBLEM: A simple game  
« Reply #7 on: Aug 29th, 2002, 2:50pm »
Quote Quote Modify Modify

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

My arcade cabinet
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: NEW PROBLEM: A simple game  
« Reply #8 on: Aug 29th, 2002, 9:10pm »
Quote Quote Modify Modify

50 posts. 6 more and you'll be a "Junior Member"!  Cheesy
 
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.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: NEW PROBLEM: A simple game  
« Reply #9 on: Sep 3rd, 2002, 3:55pm »
Quote Quote Modify Modify

I disagree!  I throw all my chips on 51.  Wink  Wink  Wink
« Last Edit: Sep 3rd, 2002, 3:56pm by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Quetzycoatl
Newbie
*






   


Gender: male
Posts: 46
Re: NEW PROBLEM: A simple game  
« Reply #10 on: Jan 12th, 2004, 1:17pm »
Quote Quote Modify Modify

on Aug 29th, 2002, 2:49pm, Jonathan_the_Red wrote:
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.

 
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.
« Last Edit: Jan 12th, 2004, 1:55pm by Quetzycoatl » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: NEW PROBLEM: A simple game  
« Reply #11 on: Mar 23rd, 2005, 6:10pm »
Quote Quote Modify Modify

on Aug 29th, 2002, 2:49pm, 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 Return to Origin 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 rSn, with stopping time T=min {j: Sj=B or -A}.
P(Bob loses)=P(ST=B)=(1-r-A)/(rB-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.
IP Logged
Noke Lieu
Uberpuzzler
*****



pen... paper... let's go! (and bit of plastic)

   
WWW

Gender: male
Posts: 1884
Re: A simple game  
« Reply #12 on: Mar 23rd, 2005, 7:24pm »
Quote Quote Modify Modify

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.
[
« Last Edit: Mar 28th, 2005, 9:10pm by Noke Lieu » IP Logged

a shade of wit and the art of farce.
titan
Newbie
*





   


Posts: 33
Re: A simple game  
« Reply #13 on: Oct 15th, 2013, 2:48pm »
Quote Quote Modify Modify

- 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!
« Last Edit: Oct 15th, 2013, 2:56pm by titan » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board