bonanova Posted March 10, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 gavinksong Posted April 9, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 dgreening Posted March 10, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 k-man Posted March 10, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 10, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 11, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 gavinksong Posted March 11, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 dgreening Posted March 11, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 12, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 13, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 gavinksong Posted March 13, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 13, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 bonanova Posted March 21, 2015 Author Report Share Posted March 21, 2015 That's a solution for one case. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted March 29, 2015 Author Report Share 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 Link to comment Share on other sites More sharing options...

0 gavinksong Posted March 31, 2015 Report Share 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 Link to comment Share on other sites More sharing options...

## Question

## bonanova

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 afair coin.Is there a general way to produce

outcomes, each with 1/nprobability, using two coinsnand finite number of flips? You are allowed to use a different pair of coins for each

.nIf it is

notalways possible, find a value offor which it is not possible and provenimpossibility for it.

## Link to comment

## Share on other sites

## 14 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.