[bushindo]

You have 4 biased coins. They look identical. They have the following respective probability to land up head: 1/5, 2/5, 3/5, 4/5. You accidentally jumbled the four coins together and now you don't know which is which.

Lets say that you have to determine the coin's identities by flipping them and observe the outcomes. Assume you can flip as many times as you like, and you can choose any coin at any flip.

1) what's lowest expect number of flip required to identify 1 coin with 95% certainty? that is, you want the lowest expected number of flips to correctly identify 1 coin 95% of the time.

Hard bonus.

2) What is the lowest expected number of flips required to correctly identify all 4 with 95% certainty?

[CaptainEd]

Perhaps this is obvious, but I need to know what is meant by "identify 1 coin with 95% accuracy". Do you mean:

(a) grab a coin at random; do some experiments; announce whether it is the 1/5, 2/5, etc.; and have probability at least .95 that it has that weight, or

(b) grab a weight at random (put 4 pieces of paper in a hat, one saying "1/5", one saying "2/5", etc.); locate a coin that you believe has that weight; announce it; and have probability at least .05 that that coin is the one with that weight.

Edited July 13, 2009 by CaptainEd

[bushindo]

Perhaps this is obvious, but I need to know what is meant by "identify 1 coin with 95% accuracy". Do you mean:

(a) grab a coin at random; do some experiments; announce whether it is the 1/5, 2/5, etc.; and have probability at least .95 that it has that weight, or

(b) grab a weight at random (put 4 pieces of paper in a hat, one saying "1/5", one saying "2/5", etc.); locate a coin that you believe has that weight; announce it; and have probability at least .05 that that coin is the one with that weight.

The interpretation in part a) is correct.

[Guest]

now I dont know if this matters but can you use the other coins. For example if you flip each coin once it gives you a good amount of information (though since i havent done it, i have no idea how much). Is the puzzle do what ever you want untill you can announce with 95% certainty one of the coins identities? or rather how many flips does it take to be able to identify one coin (you dont have to choose which one till the end) with 95% certainty no matter what the outcome of the flips?

i think this is right but i have a feeling that this problem could take a decent amount of work and i hate doing work on the wrong problem

[bushindo]

You can flip whichever coin you like at any turn. The goal is to be able to identify any coin with 95% correct probability. Obviously, if you happen to start with the 1/5 or 4/5 coin, it would take less flips to be certain of the coin's identiy. The interesting part here is whether you should just pick a coin and continue flipping until it's identity is clear, or should you flip each coin once or twice first to get some information about their identities.

Edited July 14, 2009 by bushindo

[Guest]

would'nt it be easy enough to grab any coin and flip it 5 times and know which one is which? If a coin is biased at being a head 20% of the time, after 5 flips would'nt it always be 1 head and 4 tails? Or does'nt it work that way? If it does then I'll say 5 flips to identify 1 coin, and 20 flips to identify all 4.....as usual, if it seems too simple for me it's usually wrong...

[Guest]

Probability laws dictate that in 5 flips any of these coins can flip all heads or all tails.

However, 95% of the time, they will be distributed as expected if you flip the coins a certain number of times.

You have to use statistical mathematics here to determine that minimum number of times.

[Guest]

so let's run through a test. let's say a take one of the four coins and flip it 5 times in a row, and all 5 times it lands on heads.

the probability of this happening with the 1/5 coin is (1/5)^5 = .00032.

with (2/5)^5 = .01024.

with (3/5)^5 = .07776.

with (4/5)^5 = .32768.

so then proportionality wise, this would result in the following

.00032 +.01024 +.07776 +.32768 = 0.416,

.00032/.416 = .00077 so we can fairly safely eliminate this coin.

.01024/.416 = .02462 so we can fairly safely eliminate this coin as well.

.07776/.416 = 0.1869 so this doesn't quite fit in the 95 percentile, and we can't eliminate it yet.

.32768/.416 = 0.7876 so its highly likely to be this coin, but not quite likely enough.

based solely on this, i'd say you'd need to flip a single coin between 8 -10 times.

[superprismatic]

You have 4 biased coins. They look identical. They have the following respective probability to land up head: 1/5, 2/5, 3/5, 4/5. You accidentally jumbled the four coins together and now you don't know which is which.

Lets say that you have to determine the coin's identities by flipping them and observe the outcomes. Assume you can flip as many times as you like, and you can choose any coin at any flip.

1) what's lowest expect number of flip required to identify 1 coin with 95% certainty? that is, you want the lowest expected number of flips to correctly identify 1 coin 95% of the time.

Hard bonus.

2) What is the lowest expected number of flips required to correctly identify all 4 with 95% certainty?

35 (35 if you're flipping the 1/5 or 4/5 coins; 45 if you're flipping the 2/5 or 3/5 coins)

Edited July 19, 2009 by superprismatic