BrainDen.com - Brain Teasers
• 0

# Simulating an n-sided die with two coins

## Question

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.

## Recommended Posts

• 0

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:

- 2M "large" outcomes of probability (1/2M)(1-1/N) and

- 2M "small" oucomes of probability (1/2M)(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*2M.

To simplify the problem, let's pretend that we're actually assigning balls to bins, where each of N bins can hold 2M units of space, each of 2M large balls take up N-1 units of space, and each of 2M small balls take up 1 unit of space.

Since K*(N-1) < 2M 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 2M - K*(N-1) < K, we can throw the remaining 2M - 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 by gavinksong
• 2
##### Share on other sites

• 0

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

##### Share on other sites

• 0

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. P1nP2m
2. (1-P1)nP2m
3. P1n(1-P2)m
4. (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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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. P1nP2m
2. (1-P1)nP2m
3. P1n(1-P2)m
4. (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)?
##### Share on other sites

• 0

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. P1nP2m
2. (1-P1)nP2m
3. P1n(1-P2)m
4. (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.

##### Share on other sites

• 0

Red Herring!???

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. P1nP2m
2. (1-P1)nP2m
3. P1n(1-P2)m
4. (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.

##### Share on other sites

• 0

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

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

##### Share on other sites

• 0

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?

##### Share on other sites

• 0

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

##### Share on other sites

• 0

@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 by bonanova
##### Share on other sites

• 0

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 needed coins are [a] fair coin and 1/n coin.

But how?

##### Share on other sites

• 0

@k-man

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

There are 26 = 64 possible outcomes.

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

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.