Author 
Topic: A simple game (Read 7107 times) 

Jonathan_the_Red
Junior Member
Gender:
Posts: 102


A simple game
« on: Aug 5^{th}, 2002, 11:04am » 
Quote 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 1p). 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 15^{th}, 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 5^{th}, 2002, 10:23pm » 
Quote 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
Gender:
Posts: 949


Re: NEW PROBLEM: A simple game
« Reply #2 on: Aug 28^{th}, 2002, 1:51pm » 
Quote Modify

No, Alice wins. This is a nonzeromean 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
Gender:
Posts: 288


Re: NEW PROBLEM: A simple game
« Reply #3 on: Aug 28^{th}, 2002, 2:40pm » 
Quote 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
Posts: 156


Re: NEW PROBLEM: A simple game
« Reply #4 on: Aug 28^{th}, 2002, 2:43pm » 
Quote 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
Gender:
Posts: 949


Re: NEW PROBLEM: A simple game
« Reply #5 on: Aug 29^{th}, 2002, 4:58am » 
Quote 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
Gender:
Posts: 102


Re: NEW PROBLEM: A simple game
« Reply #6 on: Aug 29^{th}, 2002, 2:49pm » 
Quote 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
Gender:
Posts: 102


Re: NEW PROBLEM: A simple game
« Reply #7 on: Aug 29^{th}, 2002, 2:50pm » 
Quote 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
Gender:
Posts: 1291


Re: NEW PROBLEM: A simple game
« Reply #8 on: Aug 29^{th}, 2002, 9:10pm » 
Quote Modify

50 posts. 6 more and you'll be a "Junior Member"! 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
Gender:
Posts: 318


Re: NEW PROBLEM: A simple game
« Reply #9 on: Sep 3^{rd}, 2002, 3:55pm » 
Quote Modify

I disagree! I throw all my chips on 51.

« Last Edit: Sep 3^{rd}, 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:
Posts: 46


Re: NEW PROBLEM: A simple game
« Reply #10 on: Jan 12^{th}, 2004, 1:17pm » 
Quote Modify

on Aug 29^{th}, 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 12^{th}, 2004, 1:55pm by Quetzycoatl » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: NEW PROBLEM: A simple game
« Reply #11 on: Mar 23^{rd}, 2005, 6:10pm » 
Quote Modify

on Aug 29^{th}, 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=(1p)/p > 1. Moreover, the probability of Bob losing for arbitrary A,B can be computed explicitly using the same martingale r^{Sn}, with stopping time T=min {j: S_{j}=B or A}. P(Bob loses)=P(S_{T}=B)=(1r^{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/(12d)) ~ 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)
Gender:
Posts: 1884


Re: A simple game
« Reply #12 on: Mar 23^{rd}, 2005, 7:24pm » 
Quote 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 28^{th}, 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 15^{th}, 2013, 2:48pm » 
Quote Modify

 Bob gives counter with probability p n gets with the probability (1p). Bob has B no. of counters n Alice has A at t=0.  w.r.t. Bob: Mean= [(AC1)p+(BC1)(1p)]/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<1p. 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 15^{th}, 2013, 2:56pm by titan » 
IP Logged 



