Jump to content
BrainDen.com - Brain Teasers
  • 0
bonanova

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.

Share this post


Link to post
Share on other sites

14 answers to this question

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
  • Upvote 2

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
  • 0

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. 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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
Added spoiler

Share this post


Link to post
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 answer is yes.

The needed coins are [a] fair coin and 1/n coin.

But how?

Share this post


Link to post
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).

Share this post


Link to post
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...