Simulating an n-sided die with two coins

[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 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.

[gavinksong]

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

[dgreening]

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]?

[k-man]

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:

1. P1ⁿP2^m
2. (1-P1)ⁿP2^m
3. P1ⁿ(1-P2)^m
4. (1-P1)ⁿ(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]

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.

[bonanova]

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:

1. P1ⁿP2^m
2. (1-P1)ⁿP2^m
3. P1ⁿ(1-P2)^m
4. (1-P1)ⁿ(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)?

[gavinksong]

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:

1. P1ⁿP2^m
2. (1-P1)ⁿP2^m
3. P1ⁿ(1-P2)^m
4. (1-P1)ⁿ(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.

[dgreening]

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:

1. P1ⁿP2^m
2. (1-P1)ⁿP2^m
3. P1ⁿ(1-P2)^m
4. (1-P1)ⁿ(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.

 

[bonanova]

Not a red herring; a demonstration for a simple case.

I'll not say more until a proof is posted one way or another.

[bonanova]

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?

[gavinksong]

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³=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)

[bonanova]

@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

[bonanova]

That's a solution for one case.

[bonanova]

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?

[gavinksong]

@k-man

 

First, flip a fair coin five times. Then, flip a coin with 6/7 bias for heads once.

 

There are 2⁶ = 64 possible outcomes.

- 32 of these outcomes occur with probability (1/2⁵)(6/7) = 6/224.

- The other 32 occur with probability (1/2⁵)(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).