Author |
Topic: Coin toss dice roll (Read 11897 times) |
|
Mike_V
Junior Member
Gender: 
Posts: 60
|
 |
Coin toss dice roll
« on: Nov 6th, 2009, 8:18am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
Don't specify the unspecified.
|
|
|
Vondell
Junior Member
Gender:
Posts: 78
|
|
Re: Coin toss dice roll
« Reply #1 on: Nov 6th, 2009, 8:41am » |
Quote Modify
|
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?
|
|
IP Logged |
Why is it that people ask for my two cents worth, and then only offer me a penny for my thoughts?
That deal sucks!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Coin toss dice roll
« Reply #2 on: Nov 6th, 2009, 8:54am » |
Quote Modify
|
on Nov 6th, 2009, 8:41am, Vondell wrote:| 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? |
|
That wouldn't simulate the roll of a fair die though.
on Nov 6th, 2009, 8:18am, Mike_V wrote:| Any ideas? If it's not possible, can that be proven? |
|
If we need a finite algorithm, it's not possible.
Say that the algorithm is guaranteed to terminate in M coin tosses. There are 2M 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 2M is not divisible by 6 for any integer value of M. Contradiction.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Coin toss dice roll
« Reply #3 on: Nov 8th, 2009, 1:09am » |
Quote Modify
|
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 2M % 6 = r values. Rest of the 2M - 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 232, r = 2. The probability that the unmapped values (say 232-1 and 232-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.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Vondell
Junior Member
Gender:
Posts: 78
|
|
Re: Coin toss dice roll
« Reply #4 on: Nov 9th, 2009, 8:05am » |
Quote Modify
|
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. 
This also works for different xd w/ the appropriate # of coin tosses after determining even/odd.
|
|
IP Logged |
Why is it that people ask for my two cents worth, and then only offer me a penny for my thoughts?
That deal sucks!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Coin toss dice roll
« Reply #5 on: Nov 9th, 2009, 8:10am » |
Quote Modify
|
on Nov 9th, 2009, 8:05am, Vondell wrote:
Assign an outcome to a # and flip. 1/3 for die and 1/3 for 2 coins...seems fair to me.
|
|
From the 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.
|
| « Last Edit: Nov 9th, 2009, 8:20am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin toss dice roll
« Reply #6 on: Nov 9th, 2009, 8:31am » |
Quote Modify
|
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. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Coin toss dice roll
« Reply #7 on: Nov 9th, 2009, 8:54am » |
Quote Modify
|
Use the coin to buy a die.
|
|
IP Logged |
|
|
|
grad
Newbie
Gender:
Posts: 14
|
|
Re: Coin toss dice roll
« Reply #8 on: Feb 3rd, 2010, 7:46am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Coin toss dice roll
« Reply #9 on: Feb 3rd, 2010, 7:57am » |
Quote Modify
|
on Feb 3rd, 2010, 7:46am, grad wrote:THH = Cancel the toss and start a new one
TTT = Cancel the toss and start a new one |
|
on Nov 6th, 2009, 8:18am, Mike_V wrote:| a solution that could theoretically go on forever (however unlikely) isn't valid. |
|
|
| « Last Edit: Feb 3rd, 2010, 7:57am by pex » |
IP Logged |
|
|
|
grad
Newbie
Gender:
Posts: 14
|
|
Re: Coin toss dice roll
« Reply #10 on: Feb 3rd, 2010, 8:51am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Coin toss dice roll
« Reply #11 on: Feb 3rd, 2010, 8:55am » |
Quote Modify
|
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)?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Coin toss dice roll
« Reply #12 on: Feb 3rd, 2010, 9:11am » |
Quote Modify
|
OK, I got the 3-way outcome.
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
|
| « Last Edit: Feb 3rd, 2010, 9:42am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin toss dice roll
« Reply #13 on: Feb 3rd, 2010, 9:52am » |
Quote Modify
|
Too bad we can't give the coin an imaginary bias. Then we could manage that with just two coinflips.
|
| « Last Edit: Feb 4th, 2010, 3:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Coin toss dice roll
« Reply #14 on: Feb 3rd, 2010, 10:12am » |
Quote Modify
|
on Feb 3rd, 2010, 9:11am, 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. Assign HHHHH and TTTTT to one value and choose p such that p5 + (1-p)5 = 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.
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
|
| « Last Edit: Feb 3rd, 2010, 10:33am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Coin toss dice roll
« Reply #15 on: Feb 4th, 2010, 1:22am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
travelnjones
Newbie
Posts: 4
|
|
Re: Coin toss dice roll
« Reply #16 on: Jun 20th, 2012, 12:08pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin toss dice roll
« Reply #17 on: Jun 20th, 2012, 12:58pm » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
travelnjones
Newbie
Posts: 4
|
|
Re: Coin toss dice roll
« Reply #19 on: Jun 20th, 2012, 3:24pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin toss dice roll
« Reply #20 on: Jun 20th, 2012, 11:04pm » |
Quote Modify
|
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 / 2k. 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
travelnjones
Newbie
Posts: 4
|
|
Re: Coin toss dice roll
« Reply #21 on: Jun 21st, 2012, 3:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin toss dice roll
« Reply #22 on: Jun 21st, 2012, 11:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Coin toss dice roll
« Reply #23 on: Jun 22nd, 2012, 9:14am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 22nd, 2012, 9:24am by 0.999... » |
IP Logged |
|
|
|
marsh8472
Newbie
Posts: 27
|
|
Re: Coin toss dice roll
« Reply #24 on: Sep 14th, 2012, 12:48am » |
Quote Modify
|
on Jun 22nd, 2012, 9:14am, 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 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print