bonanova 83 Report post Posted March 10, 2015 A fair coin permits the selection of the first two counting numbers 1, 2 each with the probability 1/2. A cubic die permits the selection of the first six counting numbers 1, 2, ..., 6 each with the probability of 1/6. What if we want to select equally from 1, 2, 3 with probability of 1/3? That's easy with a single roll of a die, counting modulo 3. But could it be done instead using two coins (that are not necessarily fair coins)? Yes. Use a coin with 1/3 - 2/3 probability, along with a fair coin. Mark the first coin with a "1" on the 1/3 side and "2 or 3" on the 2/3 side. Mark the fair coin with a "2" on one side and "3" on the other. Flip the uneven coin. If it comes up "1" we have the outcome of 1. If it comes up "2 or 3" flip the fair coin, and we have the outcome of 2 or 3. Each outcome has a 1/3 chance. Is there a general way to produce n outcomes, each with 1/n probability, using two coins and finite number of flips? You are allowed to use a different pair of coins for each n. If it is not always possible, find a value of n for which it is not possible and prove impossibility for it. Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted April 9, 2015 (edited) Say we want to simulate an N sided die. First, flip a fair coin M times, such that N-1 < 2^{M}/K < N for some K. Then, flip a coin with a 1/N bias for tails once. This splits the probability space into: - 2^{M} "large" outcomes of probability (1/2^{M})(1-1/N) and - 2^{M} "small" oucomes of probability (1/2^{M})(1/N) We have to assign these outcomes to the faces of the die such that the probability of each face sums to 1/N. Notice that all of the above outcomes have a common denominator of N*2^{M}. To simplify the problem, let's pretend that we're actually assigning balls to bins, where each of N bins can hold 2^{M} units of space, each of 2^{M} large balls take up N-1 units of space, and each of 2^{M} small balls take up 1 unit of space. Since K*(N-1) < 2^{M} for some K, we can first assign K large balls into each of the first N-1 bins without running out of large balls or overflowing the bins. Since 2^{M} - K*(N-1) < K, we can throw the remaining 2^{M} - K*(N-1) large balls into the last bin without overflowing it. Finally, we can fill out the remaining space in the bins with the 1-unit balls. Edited April 9, 2015 by gavinksong 2 Quote Share this post Link to post Share on other sites
0 dgreening 5 Report post Posted March 10, 2015 Question The OP implies that the unfair coin in your example goes to one side 2 out of 3 time. Can you choose the coing such that you get a specific degree of "unfairness" [e.g., Heads 3 out of 5 times]? Quote Share this post Link to post Share on other sites
0 k-man 26 Report post Posted March 10, 2015 It's not possible for n=7. Suppose it was possible and we found 2 coins with probabilities P1 and P2. Using these 2 coins we can generate events with probabilities that can be expressed as one of the following: P1^{n}P2^{m}(1-P1)^{n}P2^{m} P1^{n}(1-P2)^{m} (1-P1)^{n}(1-P2)^{m} Since 7 is prime, the only way to generate probability 1/7 is to have either P1 or P2 equal 1/7. But if one of the coins has probability distribution of 1/7:6/7 then the other coin must allow us to generate 6 equally likely outcomes, which is impossible. Note that the 1/7:6/7 coin is useless after the first flip. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 10, 2015 Question The OP implies that the unfair coin in your example goes to one side 2 out of 3 time. Can you choose the coing such that you get a specific degree of "unfairness" [e.g., Heads 3 out of 5 times]? Yes. You are allowed to use a different pair of coins for each n. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 11, 2015 It's not possible for n=7. Suppose it was possible and we found 2 coins with probabilities P1 and P2. Using these 2 coins we can generate events with probabilities that can be expressed as one of the following: P1^{n}P2^{m}(1-P1)^{n}P2^{m} P1^{n}(1-P2)^{m} (1-P1)^{n}(1-P2)^{m} Since 7 is prime, the only way to generate probability 1/7 is to have either P1 or P2 equal 1/7. But if one of the coins has probability distribution of 1/7:6/7 then the other coin must allow us to generate 6 equally likely outcomes, which is impossible. Note that the 1/7:6/7 coin is useless after the first flip. Divide probability space into pieces that can be joined together to form seven pieces of equal size (probability 1/7 each)? Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted March 11, 2015 It's not possible for n=7. Suppose it was possible and we found 2 coins with probabilities P1 and P2. Using these 2 coins we can generate events with probabilities that can be expressed as one of the following: P1^{n}P2^{m}(1-P1)^{n}P2^{m} P1^{n}(1-P2)^{m} (1-P1)^{n}(1-P2)^{m} Since 7 is prime, the only way to generate probability 1/7 is to have either P1 or P2 equal 1/7. But if one of the coins has probability distribution of 1/7:6/7 then the other coin must allow us to generate 6 equally likely outcomes, which is impossible. Note that the 1/7:6/7 coin is useless after the first flip. bonanova's example is a red herring. Quote Share this post Link to post Share on other sites
0 dgreening 5 Report post Posted March 11, 2015 Red Herring!??? Please say it isn't true. It's not possible for n=7. Suppose it was possible and we found 2 coins with probabilities P1 and P2. Using these 2 coins we can generate events with probabilities that can be expressed as one of the following: P1^{n}P2^{m}(1-P1)^{n}P2^{m} P1^{n}(1-P2)^{m} (1-P1)^{n}(1-P2)^{m} Since 7 is prime, the only way to generate probability 1/7 is to have either P1 or P2 equal 1/7. But if one of the coins has probability distribution of 1/7:6/7 then the other coin must allow us to generate 6 equally likely outcomes, which is impossible. Note that the 1/7:6/7 coin is useless after the first flip. bonanova's example is a red herring. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 12, 2015 Not a red herring; a demonstration for a simple case. I'll not say more until a proof is posted one way or another. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 13, 2015 OK, I am willing to supply a huge clue, namely: for each n, the pair of coins that should be used. Is a clue desired? Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted March 13, 2015 Here's how I would do the first case. First, flip a fair coin twice. Then, flip a coin with 2/3 bias for heads once. There are 2^{3}=8 possible outcomes. Map each outcome to 1, 2, or 3 like this: 1 : HHH, HHT, HTT (probability 2/12 + 1/12 + 1/12 = 1/3) 2 : HTH, THT, TTT (probability 2/12 + 1/12 + 1/12 = 1/3) 3 : THH, TTH (probability 2/12 + 2/12 = 1/3) Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 13, 2015 (edited) @gavinksong k-man has correctly shown that 1/n can't be obtained from a single outcome. So we must show that 1/n can be always obtained by groups of outcomes: what two coins should be used, and how many times need each coin be tossed, while trying not to "waste" any outcomes. With two coins, probability space becomes a unit square. One dimension each for all the outcomes for each coin Your solution for n=3 maps as follows: Biased coin H T F +------+---+ a HH | 1 | 1 | i +------+---+ r HT | 2 | 1 | +------+---+ c TH | 3 | 2 | o +------+---+ i TT | 3 | 2 | n +------+---+ Edited March 15, 2015 by bonanova Added spoiler Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 21, 2015 That's a solution for one case. Quote Share this post Link to post Share on other sites
0 bonanova 83 Report post Posted March 29, 2015 Is there a general way to produce n outcomes, each with 1/n probability, using two coins and finite number of flips? You are allowed to use a different pair of coins for each n. The answer is yes. The needed coins are [a] fair coin and 1/n coin. But how? Quote Share this post Link to post Share on other sites
0 gavinksong 11 Report post Posted March 31, 2015 @k-man First, flip a fair coin five times. Then, flip a coin with 6/7 bias for heads once. There are 2^{6} = 64 possible outcomes. - 32 of these outcomes occur with probability (1/2^{5})(6/7) = 6/224. - The other 32 occur with probability (1/2^{5})(1/7) = 1/224. Each number from 1 to 6 can be mapped to by five outcomes of the first kind and two of the second kind (probability 5*(6/224)+2*(1/224) = 1/7). Number 7 can be mapped to by two outcomes of the first kind and twenty of the second kind (probability 2*(6/224)+20*(1/224) = 1/7). Quote Share this post Link to post Share on other sites
A fair coin permits the selection of the first two counting numbers 1, 2 each with the probability 1/2.
A cubic die permits the selection of the first six counting numbers 1, 2, ..., 6 each with the probability of 1/6.
What if we want to select equally from 1, 2, 3 with probability of 1/3?
That's easy with a single roll of a die, counting modulo 3.
But could it be done instead using two coins (that are not necessarily fair coins)?
Yes. Use a coin with 1/3 - 2/3 probability, along with a fair coin.
Is there a general way to produce n outcomes, each with 1/n probability, using two coins
and finite number of flips? You are allowed to use a different pair of coins for each n.
If it is not always possible, find a value of n for which it is not possible and prove
impossibility for it.
Share this post
Link to post
Share on other sites