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.

 

  Reveal hidden contents

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]

  Reveal hidden contents

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]

  On 3/10/2015 at 7:37 PM, dgreening said:

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]

  On 3/10/2015 at 8:56 PM, k-man said:

  Reveal hidden contents

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.

 

  Reveal hidden contents

Divide probability space into pieces that can be joined together to form seven pieces of equal size (probability 1/7 each)?

[gavinksong]

  On 3/10/2015 at 8:56 PM, k-man said:

  Reveal hidden contents

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.

 

  Reveal hidden contents

bonanova's example is a red herring.

[dgreening]

  Reveal hidden contents

Red Herring!???

Please say it isn't true.

  On 3/11/2015 at 5:47 AM, gavinksong said:

 

  On 3/10/2015 at 8:56 PM, k-man said:

  Reveal hidden contents

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.

 

  Reveal hidden contents

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. 

  Reveal hidden contents

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

 

  Reveal hidden contents

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.

 

  Reveal hidden contents

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

 

  Reveal hidden contents

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