Author |
Topic: A simple game (Read 8329 times) |
|
Jonathan_the_Red
Junior Member
Gender: 
Posts: 102
|
 |
A simple game
« on: Aug 5th, 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 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 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 28th, 2002, 1:51pm » |
Quote 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
Gender:
Posts: 288
|
|
Re: NEW PROBLEM: A simple game
« Reply #3 on: Aug 28th, 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 28th, 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 29th, 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 29th, 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 29th, 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 29th, 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 3rd, 2002, 3:55pm » |
Quote Modify
|
I disagree! I throw all my chips on 51. 
|
| « 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:
Posts: 46
|
|
Re: NEW PROBLEM: A simple game
« Reply #10 on: Jan 12th, 2004, 1:17pm » |
Quote 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:
Posts: 1948
|
|
Re: NEW PROBLEM: A simple game
« Reply #11 on: Mar 23rd, 2005, 6:10pm » |
Quote 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)
Gender:
Posts: 1884
|
|
Re: A simple game
« Reply #12 on: Mar 23rd, 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 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 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print