[Guest]

"Pitch and Toss" was or is an Australian game of which the solution is relevant to some nuclear physics calculations, in a somewhat more complicated manner. It works out as an elementary result in random walk theory.

Two Aussies in the outback wish to play a gambling game to relieve their boredom. Player A has "a" Australian Dollar coins, while player B has "b" coins of the same denomination. In each step of the game a 50:50 coin flip decides which player wins that particular round. If player A wins then player B gives player A one of his coins, and if player B wins then player A gives player B one of his coins. The game terminates when one of the players becomes bankrupt. What is the probability that A wins the match?

Apologies to Rookie and/or the moderators if this one has been published before.

Edited October 3, 2009 by jerbil

[Guest]

I don't understand: aren't player A and B identical? If A wins, B gives A one of B's coins, and if B wins, A gives B one of A's coins, right?

So the person most likely to win is the one with most coins.

If you have 3 coins, and the other person has 100, you have a really good chance of losing (getting heads three times in a row is common). But if both players have 100, it's going to be a reaaaaaaaaaaaaaally long game.

Anyway, since we don't know who has more coins, and A and B are identical (as far as I can tell), it's still 50/50

[Guest]

I don't understand: aren't player A and B identical? If A wins, B gives A one of B's coins, and if B wins, A gives B one of A's coins, right?

So the person most likely to win is the one with most coins.

If you have 3 coins, and the other person has 100, you have a really good chance of losing (getting heads three times in a row is common). But if both players have 100, it's going to be a reaaaaaaaaaaaaaally long game.

Anyway, since we don't know who has more coins, and A and B are identical (as far as I can tell), it's still 50/50

Yes DN, but there happens to be a closed formula in terms of a and b which determines precisely what the probability is of player A winning the match, whether A starts with 53 and B starts with 41, or whatever. I quite agree that in this particular case A is more likely to win the match, but it is also possible that B wins. The question is "how probable" in each case.

Incidentally, meeting one Australian may be considered a misfortune. Meeting two identical Australians must be considered a disaster. (Tongue in cheek, you talking Kangaroos.)

Edited October 3, 2009 by jerbil

[Guest]

i atually looked in up and australia has the 15 highest value in surrency meaniong that there are over 4500 currencys that have less value that the australian. this means the technically he would have a 16/4500 otherwise a .00355.. percent chance of winning but that is if he was likley to be in a room full of 4500 different people with different currencys which is not possible practically. but if he were in australia he would have about a 40/60 or abo0ut 3/8 .425 percent chance of winning because of other people in the state could be america or any other currency. but if in america he woul likley win because americas currency is of more value than Australia's.

[Guest]

i atually looked in up and australia has the 15 highest value in surrency meaniong that there are over 4500 currencys that have less value that the australian. this means the technically he would have a 16/4500 otherwise a .00355.. percent chance of winning but that is if he was likley to be in a room full of 4500 different people with different currencys which is not possible practically. but if he were in australia he would have about a 40/60 or abo0ut 3/8 .425 percent chance of winning because of other people in the state could be america or any other currency. but if in america he woul likley win because americas currency is of more value than Australia's.

?

[Guest]

?

i just decided to make it way too complicated and see what people would think about what i was saying becasue if you look it up it all makes sense.

[Guest]

It has now been 12 hours since I first posted the problem, so I think it worthwhile to post the following.

Think of difference equations. They may not be common on this website, but are a useful addition to any problem solver's "vocabulary."

[Guest]

The probability that player A wins is A/B. It seems to hold for cases (1,1), (1,2), (1,3), (2,2) but I have not tested beyond that.

[Guest]

The probability that player A wins is A/B. It seems to hold for cases (1,1), (1,2), (1,3), (2,2) but I have not tested beyond that.

I think your program is wrong, ljb. The probability of A winning cannot be greater than 1.

[Guest]

I think your program is wrong, ljb. The probability of A winning cannot be greater than 1.

So true.

A/(A+B)

[Guest]

FOR A TO WIN

HE SHOULD WIN EACH TOSS AND B SHOULD LOSE EACH TOSS TILL A WINS A TOTAL OF b GAMES.

SO THE PROBABILITY OF HIM WINNING IS 1 IN 2 TO THE POWER b...AND VISE VERSA FOR B TO WIN

[Guest]

Absolutely correct, ljb, I did realize your answer was a mere typo. Well done. Of course proving it is a different matter. Believe it or not, the solution is just as easy when at each step the probability of A winning a coin is p:q not 50:50.

[Guest]

The chance of any person going bankrupt, if they were playing by themselves, is:

(1/2)^n

Where n is how many coins they have.

If A has 1 coin and B has 100, then the chance of A winning is

(1/2)^100

Right? Nope.

If A has 1 coin and B has 2, and x is the probability that A wins, then

x = 1/2(1/2) + 1/2(1/2(x))

x = 1/3

(It helps to draw a small tree of possibilities to understand how I got my equation).

I drew another tree for a = 2, b = 3, x = probability A wins, and this is what I'm getting:

x = 1/2(1/2(x)) + 1/2(y)

y = 1/2(x) + 1/2(1/2(y)) + 1/2(1/2)

I solved that x = 2/5. Feel free to check my algebra.

I think the answer is still on the magnitude of (1/2)^n, just diminished by something.

a = 1, b = 2, magnitude 1/4, P(A win) = 1/3

a = 2, b = 3, magnitude 1/8, P(A win) = 2/5

hm... looking at my tables, the number of branches looks like it might be determined by b. Which means nothing. And the final wincon of A is of course a+b.

After a bit of messing around (when I only have two examples to try to make a pattern, and I'm too lazy to get more examples, all I can do is mess around, lol), here's a wild guess:

P(A win) = [(1/2)^(b-a)]*2a/(a + b)

EDIT: Just saw the posts above. I thought of guessing lbj's answer, but I don't think it's correct: when b gets really larger than a, the probability of b winning should shoot up exponentially, or...

well, maybe not.

All A has to do is win more than he loses, and not lose at the wrong time. If he wins the first, 50% chance, then he can lose the second. He just needs to stay one step ahead, and eventually gather 100 more good coin tosses than B.

So I guess I was wrong about the magnitude.

Looking forward to the proof

Edited October 4, 2009 by DarthNoob

[Guest]

An interesting post, DN.

1. When the probability p of A winning a coin at each step is different from 1/2, exponentials do indeed enter the calculation.

2. ljb is correct.

3. I was amused at your typo referring to ljb as lbj since I almost did it myself.

4. I'll post my solution to the problem whenever anyone wishes, but meanwhile you may wish to consider the hint I gave earlier in post #7 on this thread.

[Guest]

The chance of any person going bankrupt, if they were playing by themselves, is:

(1/2)^n

Where n is how many coins they have.

If A has 1 coin and B has 100, then the chance of A winning is

(1/2)^100

Right? Nope.

If A has 1 coin and B has 2, and x is the probability that A wins, then

x = 1/2(1/2) + 1/2(1/2(x))

x = 1/3

(It helps to draw a small tree of possibilities to understand how I got my equation).

I drew another tree for a = 2, b = 3, x = probability A wins, and this is what I'm getting:

x = 1/2(1/2(x)) + 1/2(y)

y = 1/2(x) + 1/2(1/2(y)) + 1/2(1/2)

I solved that x = 2/5. Feel free to check my algebra.

I think the answer is still on the magnitude of (1/2)^n, just diminished by something.

a = 1, b = 2, magnitude 1/4, P(A win) = 1/3

a = 2, b = 3, magnitude 1/8, P(A win) = 2/5

hm... looking at my tables, the number of branches looks like it might be determined by b. Which means nothing. And the final wincon of A is of course a+b.

After a bit of messing around (when I only have two examples to try to make a pattern, and I'm too lazy to get more examples, all I can do is mess around, lol), here's a wild guess:

P(A win) = [(1/2)^(b-a)]*2a/(a + b)

EDIT: Just saw the posts above. I thought of guessing lbj's answer, but I don't think it's correct: when b gets really larger than a, the probability of b winning should shoot up exponentially, or...

well, maybe not.

All A has to do is win more than he loses, and not lose at the wrong time. If he wins the first, 50% chance, then he can lose the second. He just needs to stay one step ahead, and eventually gather 100 more good coin tosses than B.

So I guess I was wrong about the magnitude.

Looking forward to the proof

what i think is slightly different..

this is not a must win game ( if both A and B have 1000 coins they can play for all their life and end up not winning... in that case the probability of a no result is 99.999999999999999......%)

i mean that

probability of A to win + probability of B to win equal to 1 DOES NOT HOLD TRUE (as it does with the A/A+B solution provided by ljb)

it should be :

no result + A wins + B wins = 1

if B has only one coin then A has to win only the first toss: that is a probability of 50%,

or he has to win 2 out of 3 (that situation will arise only if he loses the first toss because the game ends if he wins), that again has a probability of 50%!!, because either of them will win 2 out of the first 3 tosses. or 3 out of 5 , or 4 out of 7, or 5 out of 9.......we keep the count till he is ahead by one toss and then we stop (assuming he doesn't go bankrupt and lose the game)

so there is 50 % chance of him winning one extra toss.

then the counting begins once again... if B has more than one coin at start of the game.

for him(A) to win the game he has to win b number of extra tosses that means his win probability is b times 50% or in other words 1 in 2^b

Edited October 4, 2009 by cmgogo00

[bushindo]

Absolutely correct, ljb, I did realize your answer was a mere typo. Well done. Of course proving it is a different matter. Believe it or not, the solution is just as easy when at each step the probability of A winning a coin is p:q not 50:50.

Here's a way to derive the answer using matrices. This probably isn't the solution you had in mind. I'd like to know that solution, though.

Let the total number of coins be T = p + q.

Let P(0) be the chance that A wins the game when he has 0 coin left. Of course, we know that P(0) = 0

Let P(1) be the chance that A wins the game when he has 1 coin left

...

Let P(n) be the chance that A wins the game when he has n coins

We can write the following system of equation

P(0)        =    P(0)               = 0

P(1)        = .5 P(0)     + .5 P(2) 

P(2)        = .5 P(1)     + .5 P(3) 

...

P(T - 1)    = .5 P(T - 2) + .5 P(T) 

P(T)        =                  P(T) = 1

We can write the above as a matrix equation A * x = x Where x = (P(0), P(1), ..., P(T) )' is a column vector of all the probabilities. A is a matrix of zeroes with 1's at A[1,1] and A[T,T], and .5's immediately to the left and right of the diagonal for rows 2 to (T-1). The solution to our problem is the eigenvector of A that correspond to the eigenvalue 1. Here's an example with T = 5

A = 

     [,1] [,2] [,3] [,4] [,5] [,6]

[1,]  1.0  0.0  0.0  0.0  0.0  0.0

[2,]  0.5  0.0  0.5  0.0  0.0  0.0

[3,]  0.0  0.5  0.0  0.5  0.0  0.0

[4,]  0.0  0.0  0.5  0.0  0.5  0.0

[5,]  0.0  0.0  0.0  0.5  0.0  0.5

[6,]  0.0  0.0  0.0  0.0  0.0  1.0


eigenvalues

[1]  1.000000  1.000000 -0.809017  0.809017 -0.309017  0.309017


eigenvectors

     [,1] [,2]      [,3]      [,4]      [,5]      [,6]

[1,]  1.0  0.0  0.000000  0.000000  0.000000  0.000000

[2,]  0.8  0.2 -0.371748 -0.371748 -0.601501 -0.601501

[3,]  0.6  0.4  0.601501 -0.601501  0.371748 -0.371748

[4,]  0.4  0.6 -0.601501 -0.601501  0.371748  0.371748

[5,]  0.2  0.8  0.371748 -0.371748 -0.601501  0.601501

[6,]  0.0  1.0  0.000000  0.000000  0.000000  0.000000

So, we see that for T = 5, (P(0), P(1), P(2), P(3), P(4), P(5) ) = (0, 1/5, 2/5, 3/5, 4/5, 5/5). It is relatively easy to discern the overall formula for P(n) from the this example. To be completely rigorous, one can directly compute the eigenvectors from a general A of size n x n, but I'd say that's a tag team job, if anyone wants to do it.

Of course, an easier way to prove the general formula would be to show that for matrix A of size N x N, where A has the special form specified above, the vector v = ( 0/N, 1/N, ...., N/N) is an eigenvector with eigenvalue 1. That is, the vector v satisfies the equation A*v = v. That should be a bit easier.

Edited October 4, 2009 by bushindo

[Guest]

What a truly fascinating approach, Bushindo. I had never thought of that tactic.

[Guest]

I am attaching my solution as an attached file, since my "spoiler" button seems temporarily to have gone AWOL. I can get nicer equations, using MathType, anyway.

Difference Equations.doc

[rookie1ja]

Spoilers should be working again properly. Temporary outage was caused due to forum upgrade. Thanks for understanding.

[Guest]

Thanks, Rookie.

I have just been looking at this post. After n steps, where n >= Min(a,b), the possibility of a lack of resolution decreases, eventually to zero. A useful trick, much used in Elementary Logic Theory, is to imagine that the first play occurs after 1/2 of an hour, tha next after another 1/4 of an hour, the next after another 1/8 of an hour, and so on. There will definitely be a resolution at the completion of 1 hour.

Edited October 5, 2009 by jerbil

[Guest]

I am attaching my solution as an attached file, since my "spoiler" button seems temporarily to have gone AWOL. I can get nicer equations, using MathType, anyway.

Difference Equations.doc

Wow.