wu :: forums « wu :: forums - A simple game » Welcome, Guest. Please Login or Register. Jan 24th, 2022, 9:48pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, SMQ, Grimbal, ThudnBlunder, william wu, towr, Eigenray)    A simple game « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: A simple game  (Read 7987 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

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

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

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

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

william wu

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?

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »