[RedLeader]

Problem ("Coin-Tossing"): Assume three men, Mr. X, Mr. Y and Mr. Z, arrive with amounts of coins, x, y and z, to play a game. The rules of the game are as follows:

(1) In each round, each player tosses one coin. In the case of a tie (HHH, TTT) coins are retossed. Repeat until a toss yields not a tie (HHT, HTH, HTT, THH, THT, TTH).

(2) The odd player out (e.g. the "T" in HHT) keeps all 3 coins to himself from that round.

Given values x, y and z, what is the average/expected number of tosses before the first man goes broke?

Note that we ask for "tosses" and not "rounds," as multiple tosses can occur within rounds to break ties.

[Haphazard]

So the number of coins each man has to begin with doesn't matter?

[themuzicman]

Can we assume that either X, Y, or Z is > 2? Or maybe that all of them are?

For all values = 2, the answer is 100% that one man will be out in the 2nd round. (Yes, I know this isn't tosses...)
For all value = 1, the answer is 100% that one man will be out in the 1st round.

Beyond two, the game may go on more than two rounds.

[Haphazard]

All combinations:

HHH
THH
HTH
HHT
TTH
THT
HTT
TTT

So there are 8 combinations and 2 in which there needs to be a retoss. That means that 1/4th of the time there will be at least one more toss per round, 1/16 of a chance that there will be at least three tosses, 1/64 of a chance that there will be at least four tosses, 1/256 chance that there will be at least five tosses...

[RedLeader]

	Originally Posted by Haphazard To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	So the number of coins each man has to begin with doesn't matter?

Well, it matters in as much as your final expression for the expected number of tosses will contain x, y and z..variables for the numbers of coins.

i.e. E(#tosses)=x+y+z <- Not the answer

---------- Post added 07-13-2010 at 02:46 PM ----------

	Originally Posted by themuzicman To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	Can we assume that either X, Y, or Z is > 2? Or maybe that all of them are? For all values = 2, the answer is 100% that one man will be out in the 2nd round. (Yes, I know this isn't tosses...) For all value = 1, the answer is 100% that one man will be out in the 1st round. Beyond two, the game may go on more than two rounds.

Assume that they could be any postive integer amounts of coins, ya. Just know that your final expression will show that the above two cases hold true for verification.

[themuzicman]

Let's see...

Sum(x->oo) 1/4^x = ....

[Haphazard]

(x+y)/2z+(x+z)/2y+(y+z)/2x= R

R+ [1 sigma R 1/4^n]

[Monte314]

This is a non-trivial problem, but is amenable to a number of avenues of attack. For the time being, I am observing....

[Latro]

My initial look is numerical:

( Show Spoiler )

#!/usr/bin/python
#cointoss.py
#executes code for the problem stated at
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

import random
def cointoss(n,initcoins):
#run the simulation n times with the initial coin numbers being in the list initcoins

total = 0
for i in range(n):

coins = initcoins[:]
p = 0 #number of tosses that have occurred in this particular run
while min(coins) > 0:

done = False
toss = []
for j in range(3): #do the tosses

toss.append(random.choice([0,1]))

for j in range(3):

if done: break
for k in range(j+1,3):

if done: break
if toss[j] == toss[k] and toss[j] != toss[3-j-k]:
#if we have equality of these two but not the other;
#also notice that j+k is never 0 so the reference is
#always defined

coins[j] -= 1 #take away from the two that are the same
coins[k] -= 1
coins[3-j-k] += 2 #give to the one that is different
done = True

p += 1 #a toss has happened

total += p

return total/n

print(cointoss(int(input('number of runs')),[10,20,30]))

(Indenting on VBulletin, ugh...)
Some data (I will probably write an additional script to actually run through in a predictable way later and then attempt to do an interpolation with a large data set, but at the moment I've already procrastinated way too much):

( Show Spoiler )

[10,20,30] clusters around 140
[10,15,20] clusters around 90
[5,10,15] clusters around 35

At a glance it does not seem to be linear in the inputs, which, while expected, makes the problem a lot harder.

[Monte314]

Approximate empiricial results: the three numbers are the starting coin count for each guy, and the the number on the right is the average number of tosses until the first bankruptcy of some player. Each value is based on approximatley 100,000 games. I seem to be getting the same results as Latro, e.g., see the first entry:

tosses(10,20,30) = 138

tosses(1,1,1) = 1.33
tosses(1,1,2) = 1.33
tosses(1,2,2) = 1.777
tosses(1,2,3) = 2
tosses(2,2,2) = 2.66
tosses(3,3,3) = 5.16
tosses(4,4,4) = 8.57
tosses(5,5,5) = 12.83
tosses(6,6,6) = 18
tosses(7,7,7) = 24.25
tosses(8,8,8) = 31.25
tosses(9,9,9) = 38.91

tosses(100,100,100) = 4450.
tosses(1024,1024,1024) = 466666
tosses(1,1000,1000) = 666
tosses(1,2000,2000) = 1333
tosses(1,3000,3000) = 1666

tosses(10,5,5) = 18.5
tosses(50,50,50) = 1133
tosses(100,50,50) = 1685
tosses(10,9,8) = 38.42

tosses(10,10,1) = 7
tosses(10,10,2) = 13.28
tosses(10,10,3) = 19
tosses(10,10,4) = 24.25
tosses(10,10,5) = 29
tosses(10,10,6) = 33.25
tosses(10,10,7) = 37.25
tosses(10,10,8) = 41
tosses(10,10,9) = 44.42
tosses(10,10,10) = 47.57

[Syntax]

[HIDE="answer"]This seems pretty easy to tackle using a formula for the expected value of a geometric distribution, where a tie in any round is defined as "success"(p=.25) and anything other than a tie is a "failure"(q=.75).

The formula for the mean is 1/(1-p). So, 1.333 tosses.[/HIDE]


...but montey said it's non-trivial, so I'm probably not correctly understanding the problem.



[edit] yeah...I misunderstood alright. my solution only works if they all bring only one coin.

[RedLeader]

	Originally Posted by Monte314 To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	This is a non-trivial problem, but is amenable to a number of avenues of attack. For the time being, I am observing....

This is problem comes with a difficulty rating of: (
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
)^5

It's not my original problem, no. In has an interesting history. But if I say too much on that, y'all might be able to cheat
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


The numerical answers look solid, but ya of course we're going for analytic
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.


---

Hint:

( Show Spoiler )

You'll probably want to think of a similar two-player game which can be solved for analytically and compare its recursion with that of the three-player game to infer a solution. Proving the recursion solution is unique is the really hard part
To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

[Latro]

My current efforts:

( Show Spoiler )

#!/usr/bin/python
#cointossexec.py
#runs cointoss for various inputs
from cointoss import *
b = []
for i in range(5,30,5):

for j in range(5,30,5):

for k in range(5,30,5):

b.append(cointoss(100,[i,j,k]))

print(b)

Then in MATLAB:
i = 1;
for x=5:5:25
for y=5:5:25
for z=5:5:25
A(i,: ) = [x,y,z];
i = i+1;
end
end
end

Take b as Python outputs it and do:
b = b';
Then:
x = A'*A \ A'*b;
norm(A*x-b)
turns out to be large relative to norm(b); norm(b) is about 1200 while norm(Ax-b) is about 400. So it doesn't seem to be linear, even with only 125 arguments. On the other hand, assuming linearity I'm getting something fairly close to 2(x+y+z), so it should theoretically be relatively close to that, at least close-ish to the origin.

It is definitely not of the form ax^2+by^2+...+fz, as doing that gives me negative coefficients which are nonsense obviously.

A considerably better interpolation appears to be about 0.135*(xy+yz+xz), but it still isn't great, being off by on average 12 units in each run...