wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Coin toss dice roll
        
(Message started by: Mike_V on Nov 6^th, 2009, 8:18am)

Title: Coin toss dice roll
Post by Mike_V on Nov 6^th, 2009, 8:18am

So, this feels like it should be a classic, but I did a search and didn't see anything, so I'll post it. This is a problem I was asked on an interview a few days ago. I still have no answer, so I leave it to you guys.

Basically, the question was how to simulate a dice roll using just coin tosses. (Both dice and coin are perfectly fair.) The tricky part is guaranteeing that your coin toss algorithm will end. (Ie a solution that could theoretically go on forever (however unlikely) isn't valid.)

Any ideas? If it's not possible, can that be proven?

Title: Re: Coin toss dice roll
Post by Vondell on Nov 6^th, 2009, 8:41am

[hide]Wouldn't flipping a coin 6x (or = to the # of sides the die/dice may have) and assigning either heads or tails to represent the pips on the die/dice be the simplest solution?[/hide]

Title: Re: Coin toss dice roll
Post by pex on Nov 6^th, 2009, 8:54am

on 11/06/09 at 08:41:36, Vondell wrote:

[hide]Wouldn't flipping a coin 6x (or = to the # of sides the die/dice may have) and assigning either heads or tails to represent the pips on the die/dice be the simplest solution?[/hide]

That wouldn't simulate the roll of a fair die though.

on 11/06/09 at 08:18:23, Mike_V wrote:

Any ideas? If it's not possible, can that be proven?

If we need a finite algorithm, it's not possible.

[hide]Say that the algorithm is guaranteed to terminate in M coin tosses. There are 2^M possible resulting sequences of heads and tails, and we want to map each of them to one of the numbers {1,2,3,4,5,6}.

To simulate a fair die, the same number of sequences should map to each of these six numbers. But 2^M is not divisible by 6 for any integer value of M. Contradiction.[/hide]

Title: Re: Coin toss dice roll
Post by R on Nov 8^th, 2009, 1:09am

I ditto pex. We cannot guarantee that the algorithm will terminate but we can only maximize the probability.
To simulate a dice, with coin toss, we will need to discard 2^M % 6 = r values. Rest of the 2^M - r value can easily be mapped to {1,2,3,4,5,6}. If we choose a large M such that r is the least possible. For example, for 2³², r = 2. The probability that the unmapped values (say 2³²-1 and 2³²-2) will occur is very less. Even if they occur in first iteration; in the successive iterations of the algorithm the probability of halting will further increase.

Title: Re: Coin toss dice roll
Post by Vondell on Nov 9^th, 2009, 8:05am

How about this?

For a standard d6 (six sided die for you non-gamers), I believe it can be done in 3 coin tosses.

First, flip a single coin and assign heads and tails to odd and even however you wish...it doesn't really matter which.
So H=even T=odd
50% chance on coin and 50% chance odd/even on die
Flip comes up heads(even).
There are only 3 even #'s on a die...2,4,6.
This is where the other 2 coin flips come in. With 2 coins, there are only 3 possible outcomes (repetitions inclusive) HH,HT,TT.
Assign an outcome to a # and flip. 1/3 for die and 1/3 for 2 coins...seems fair to me. ;D

This also works for different xd w/ the appropriate # of coin tosses after determining even/odd.

Title: Re: Coin toss dice roll
Post by Grimbal on Nov 9^th, 2009, 8:10am

on 11/09/09 at 08:05:08, Vondell wrote:

Assign an outcome to a # and flip. 1/3 for die and 1/3 for 2 coins...seems fair to me. ;D

From the ;D I'd say you know perfectly well what is wrong with this method. ;)

I have another method:

Toss a coin. Write down the time (0:00 to 23:59). Divide the hour figure by 4 and add 1. That is your simulated die value.

Don't repeat it too often. And do it only when you have absolutely no idea what time it is.

Title: Re: Coin toss dice roll
Post by towr on Nov 9^th, 2009, 8:31am

If you have two coins, you can grind the edge of one down so it is a cylinder that equally likely ends up one either side or the edge, and the other so it cannot land on it's edge. ::)

Title: Re: Coin toss dice roll
Post by pex on Nov 9^th, 2009, 8:54am

Use the coin to buy a die.

Title: Re: Coin toss dice roll
Post by grad on Feb 3^rd, 2010, 7:46am

[hide]So, I will use 3 coins and consider the following:

HHH = 1
HHT = 2
HTH = 3
HTT = 4
THT = 5
TTH = 6
THH = Cancel the toss and start a new one
TTT = Cancel the toss and start a new one

Each case has a probability of 1/8 = 12.5% but if you cancel the last two cases then their probabilities are split equally among the remaining six, that is 12.5 + (25/6) = 16.667% which is the probability of a fair dice.[/hide]

Title: Re: Coin toss dice roll
Post by pex on Feb 3^rd, 2010, 7:57am

on 02/03/10 at 07:46:09, grad wrote:

THH = Cancel the toss and start a new one
TTT = Cancel the toss and start a new one

on 11/06/09 at 08:18:23, Mike_V wrote:

a solution that could theoretically go on forever (however unlikely) isn't valid.

Title: Re: Coin toss dice roll
Post by grad on Feb 3^rd, 2010, 8:51am

Well, there's 25% chance that you restart the procedure, so in -let's say- 10 canceled tosses the probability that you get again THH or TTT is about 0,0001%. I understand that theoretically it could go on forever but actual computer algorithm that simulate dice rolling in online casinos are based in this principle.

Title: Re: Coin toss dice roll
Post by Grimbal on Feb 3^rd, 2010, 8:55am

As pex proved, it is not possible with a fair coin. I was wondering whether a loaded coin could do better.

Suppose you could chose the probability of the coin, could you now simulate a die perfectly? I have no idea, and it looks difficult to me. What about a fair 3-way outcome (1/3 chances each)?

Title: Re: Coin toss dice roll
Post by Grimbal on Feb 3^rd, 2010, 9:11am

OK, I got the 3-way outcome.
[hide]With a loaded die with p=0.242130 (computed), you can toss 4 times.
HHHH and TTTT are outcome 1
HTTT, TTTH, HHTT, HTHT, HTTH, HTHH, HHTH are outcome 2
TTHT, THTT, THHT, THTH, TTHH, HHHT, THHH are outcome 3.

p is the solution of p^4+(1-p)^4=1/3

PS: You also can apply the following rule
HHHH -> 1
HHHT -> 3
HHT -> 2
HT -> 2
TH -> 3
TTH -> 3
TTTH -> 2
TTTT -> 1
[/hide]

Title: Re: Coin toss dice roll
Post by towr on Feb 3^rd, 2010, 9:52am

Too bad we can't give the coin an imaginary bias. Then we could manage that with just two coinflips.

Title: Re: Coin toss dice roll
Post by SMQ on Feb 3^rd, 2010, 10:12am

on 02/03/10 at 09:11:53, Grimbal wrote:

OK, I got the 3-way outcome.

You can use the same trick to get a fair 6-sided die toss from five biased coin tosses. [hide]Assign HHHHH and TTTTT to one value and choose p such that p⁵ + (1-p)⁵ = 1/6. Since the remaining combinations of heads and tails each occur either five or ten times, assign them evenly to the remaining five cases.
[/hide]
Edit: and this general strategy should work to obtain a fair n-sided die toss from n-1 biased coin tosses when n-1 is prime.

--SMQ

Title: Re: Coin toss dice roll
Post by Grimbal on Feb 4^th, 2010, 1:22am

I suspected a solution like that on my way home.

P would be 0.303340053.

Then I wondered what would happen with n=3 and saw what towr had in mind.

Title: Re: Coin toss dice roll
Post by travelnjones on Jun 20^th, 2012, 12:08pm

Hi math folks

I know this is an old thread, I have a solution that sort of works. I am not sure what is written i see most of text in this post as blanked out. I hope i am not copying anyone's solution but I have something up on my blog that explain how to use coins as dice.

I am just a role player who didn't have dice one day so i am not sure if my long solution works out to make the probability correct. If you figure it does or doesn't please let me know

my full method is up on my blogspot page which is crescentstar . blogspot .com

Here is the text of my basic idea

So you are going to need a ton of coins of one variety and a single coin of another variety. I use pennies and quarters myself. While this could be performed with several successive coin flips I normally use a hand full of coins to speed it up. As a note if you really dont care about probablility you can use pente stones as well, you just need two colors. One will represent the pennies and the other the quarter.

Ok the first step in this is to devide the dice you are wishing to simulate by two. A nice thing about this method is it can represent any even dice so you can do the whole RPG dice set, but also weird stuff like a d14. Next you will take that many pennies. Then you will add your quarter. Shake em all up and toss them out just like you would in AD&D. From here assign 1 to heads and 2 to tails. For the quarter Heads is 0 and tails is -x. In this case x is the number of pennies thrown minus 1. Now you just add them up.

You will see this is not correct as per a single dice roll. but taking a quick look at the rolls possible for a D6 you will see it creates a bell curve not represented on dice.

Penny 1: Penny 2: Penny 3: Quarter 0 / -2
2 2 2 = 6 4
2 2 1 = 5 3
2 1 1 = 4 2
1 1 1 = 3 1

This makes the break down of roll probablility something like the following

1= 12.5% 2= 12.5% 3= 25% 4= 25% 5= 12.5% 6= 12.5%

jameslrickel@gmail.com

Title: Re: Coin toss dice roll
Post by towr on Jun 20^th, 2012, 12:58pm

The intended solution is one were all "sides" have an equal probability.
It's not really that hard, as long as you don't mind a potential infinite number of coin tosses ;)

Title: Re: Coin toss dice roll
Post by travelnjones on Jun 20^th, 2012, 1:57pm

Here is the URL for my write up i think i came up with a solution for that. It would require coin flips equal to the number of dice sides. I am not entirely sure my solution works to fix the problem.

I am new so i don't know if it will allow me to add a URL i may have to break it up

http://crescentstar.blogspot.com/2012/06/using-coins-to-simulate-dice.html

Title: Re: Coin toss dice roll
Post by travelnjones on Jun 20^th, 2012, 3:24pm

I think i had some stuff wrong in there. I am not sure I have ironed it out yet. I needed to clarify a couple of points and work out something I updated the page on my blog to hopefully clear it up.

Some of my problem when figuring out the probability is I am not sure how to count the three penny flips.

I am not sure how to count penny 1 ending up heads and the other 2 pennies coming up tails.

Is that the same as penny one coming up tails, penny two coming up head and penny three coming up tails

or are those two instance that should be counted individually?

Title: Re: Coin toss dice roll
Post by towr on Jun 20^th, 2012, 11:04pm

I think the most important think to realize as that all the probabilities you can get after a finite number of coin tosses involves a power of two, it's always N / 2^k. What you want is 1/6, but 6 is not a power of two and doesn't divide a power of two. So any scheme that uses a finite number of coin tosses won't be able to achieve the exact 1/6th probability.

Title: Re: Coin toss dice roll
Post by travelnjones on Jun 21^st, 2012, 3:17pm

Yeah i see what you are saying. Actually in mapping out how the coin flips are going I really see exactly what you are saying. I am just pushing the probability to one number or another.

I can get close to the the correct percentages with some logic tricks but I never am going to get an even spread.

I was using coin flips shift numbers which shifted probability. If i used some weird caveats I got closer to dice but would never iron it out. Basically i was creating special cases where the previous coin flip was counted which restricted the branching and in my last flip added another caveat which looked at the original "roll" I was making with my pennies and quarters. It does get close using this method but never an even spread of percentages across numbers like dice present.

Title: Re: Coin toss dice roll
Post by towr on Jun 21^st, 2012, 11:02pm

The trick to get an even spread is to keep adjusting forever. But of course, that would be impractical (impossible even) if you try to do it in one go. The easiest way to do is, is to flip 3 coins, map HHH, HHT, HTH, HTT, THH, THT to 1,2,3,4,5,6; and if you get TTH or TTT, then just start again.
The chance you have to restart in each round is 1 in 4, so the probability that more rounds are needed quickly decreases (1 in 16 for at least 2 rounds, 1 in 64 for at least 3 rounds, etc).

You can modify your scheme in a similar way; get as close to an even spread as you want and then just push the final adjustments of the probabilities to a next round.

Title: Re: Coin toss dice roll
Post by 0.999... on Jun 22^nd, 2012, 9:14am

Divide your coin into 60^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/smallcirc.gif} sections, roll it on its side, after it drops measure which section has a point that lies the farthest away.

Title: Re: Coin toss dice roll
Post by marsh8472 on Sep 14^th, 2012, 12:48am

on 06/22/12 at 09:14:34, 0.999... wrote:

Divide your coin into 60 sections, roll it on its side, after it drops measure which section has a point that lies the farthest away.

hmm that's probably the only way ;D but there's a chance there will be 2 points that are equally far away but you can use a coin toss for the tie breaker there.