|
|
#1
10-26-2006, 05:16 PM
|
|||
|
|||
Randomizing with a coin
You are playing rock paper scissors, and you want to choose which to throw using a coin. You want a probability distribution of 1/3 for each type.
Is it possible to devise an algorithm for choosing what to throw based on a series of coin flips such that you are guaranteed to have a result in a finite number of coin flips? If not, prove. If so, what is the smallest number of coin flips in which you can guarantee a result that has a perfect 1/3 distribution for each type. e.g. If you flip twice, where head-head = rock, head-tail = paper, tail-head = scissors, and tail-tail = redo, then it may never terminate. 
|
|
#2
10-26-2006, 05:22 PM
|
|||
|
|||
|
Re: Randomizing with a coin
[ QUOTE ]
You are playing rock paper scissors, and you want to choose which to throw using a coin. You want a probability distribution of 1/3 for each type. Is it possible to devise an algorithm for choosing what to throw based on a series of coin flips such that you are guaranteed to have a result in a finite number of coin flips? If not, prove. If so, what is the smallest number of coin flips in which you can guarantee a result that has a perfect 1/3 distribution for each type. e.g. If you flip twice, where head-head = rock, head-tail = paper, tail-head = scissors, and tail-tail = redo, then it may never terminate. [/ QUOTE ] It's impossible to guarantee it in a finite number of coin flips.
|
|
#3
10-26-2006, 06:04 PM
|
|||
|
|||
|
Re: Randomizing with a coin
Care to attempt a proof?
|
|
#4
10-26-2006, 06:08 PM
|
|||
|
|||
|
Re: Randomizing with a coin
Not really. But you cannot represent 1/3 exactly in binary, and all coin flips can be represented in binary, so you have a problem.
|
|
#5
10-26-2006, 07:23 PM
|
|||
|
|||
|
Re: Randomizing with a coin
[ QUOTE ]
Not really. But you cannot represent 1/3 exactly in binary, and all coin flips can be represented in binary, so you have a problem. [/ QUOTE ] Well, you tried not to prove it, but then you accidentally proved it (essentially). Better luck not proving things next time!
|
|
#7
10-27-2006, 11:45 AM
|
|||
|
|||
|
Re: Randomizing with a coin
[ QUOTE ]
[ QUOTE ] Not really. But you cannot represent 1/3 exactly in binary, and all coin flips can be represented in binary, so you have a problem. [/ QUOTE ] Well, you tried not to prove it, but then you accidentally proved it (essentially). Better luck not proving things next time! [/ QUOTE ] I didn't prove why its impossible to represent it in binary though.
|
|
#8
10-27-2006, 01:29 PM
|
|||
|
|||
|
Re: Randomizing with a coin
[ QUOTE ]
I didn't prove why its impossible to represent it in binary though. [/ QUOTE ] Proof 1 (long division in binary): Dividing binary 11 into 1.00 gives 0.01 with a remainder of 1, or 0.01010101... Proof 2 (geometric series): Binary 0.01010101... = 1/4 + 1/16 + 1/64 + 1/256 + ... = sum [n = 1 to infinity] (1/4)^n = 1/(1 - 1/4) - 1 = 1/3 There can be no finite representation of this number in binary, since if we truncate this number after the nth binary digit, the least that we could increase the remaining number would be 2^-n, and this is equal to the binary number with all 1s from position n+1 to infinity, which would clearly be greater than the alternating series of 1s and 0s being replaced.
|
|
#9
10-27-2006, 02:36 PM
|
|||
|
|||
|
Re: Randomizing with a coin
[ QUOTE ]
I didn't prove why its impossible to represent it in binary though. [/ QUOTE ] Yes, I was taking that as given, but good point. For the OP, if you flip a coin at most n times, this creates 2^n possible outcomes, equally likely. This number is not divisible by 3 because the prime factorization of 2^n is "2^n", which does not contain any "3^k".
|
|
#10
10-27-2006, 04:37 PM
|
|||
|
|||
|
Re: Randomizing with a coin
You need a 3 sided coin., wherein each side if of equal surface area, equal shape, and equally positioned equidistant from the center of mass.
The result is a somewhat football shaped curvilinear object. AB
|
 |
|
|
Linear Mode
