Author |
Topic: card simulation (Read 3759 times) |
|
lukes new shoes
Newbie
Gender: 
Posts: 34
|
 |
card simulation
« on: Nov 27th, 2002, 4:34pm » |
 Quote  Modify
|
what would be the best way to simulate the selection of a random card (from a standard pack of 52 cards) by rolling dice to generate the outcome?
|
|
 IP Logged |
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: card simulation
« Reply #1 on: Nov 27th, 2002, 5:21pm » |
Quote Modify
|
Other than using a 52 sided die? 4 sided die & 13 sided die?
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: card simulation
« Reply #2 on: Nov 27th, 2002, 7:30pm » |
Quote Modify
|
I believe a 52-sided die could be made by chopping the corners of polyhedron with the soccer-ball pattern of faces. The soccer-ball (truncated isocahedron) has 32 faces and 20 corners, so chopping off the corners forms 20 new faces for a total of 52. However, they would not be equally likely to come up when this was rolled.
It seems pretty clear to me that the intent of the question is to use a 6-sided die, and to make each of 52 different selections equally likely. By "best" way, it could mean easiest or the method requiring the fewest rolls on average.
Maybe the easiest is to roll 3 times. Multply the first roll by 36, add 6 times the second roll, and add the third roll. This gives a number from 1 to 216. If the number is greater than 208, roll all three again, and repeat until a value from 1 to 208 is obtained. The remainder when dividing this number by 52 is a random value from 0 to 51, which can be used to select a random card.
The expected number of rolls required can be slightly reduced at the expense of additional complexity.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #3 on: Nov 28th, 2002, 8:27am » |
Quote Modify
|
Kozo:
How would you use your 4-die and your 13-die?
on Nov 27th, 2002, 7:30pm, SWF wrote:| It seems pretty clear to me that the intent of the question is to use a 6-sided die, and to make each of 52 different selections equally likely. By "best" way, it could mean easiest or the method requiring the fewest rolls on average. |
|
To me it's not at all clear that the solution is supposed to use only 6-sided dice. It's not stated, so you're free to choose - ok, let's restrict ourselves to dice that actually exist. Is there a 13-sided die?
The condition that every card be chosen with the same probability is a must if one understands the question's use of "random" to mean uniformly distributed.
on Nov 27th, 2002, 7:30pm, SWF wrote:| Maybe the easiest is to roll 3 times. Multply the first roll by 36, add 6 times the second roll, and add the third roll. This gives a number from 1 to 216. |
|
Actually it gives a number from 43 to 258, right?
Considering the minimum value obtained, we arrive at 216 distinct values (surprise!), only 8 of which have us repeat the whole procedure. That's an efficiency of about 96% - quite good, but is there an even better way?
I'll think about it tonight if I can't sleep. 
|
| « Last Edit: Nov 28th, 2002, 8:31am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: card simulation
« Reply #4 on: Nov 28th, 2002, 8:51am » |
Quote Modify
|
on Nov 28th, 2002, 8:27am, wowbagger wrote:
To me it's not at all clear that the solution is supposed to use only 6-sided dice. It's not stated, so you're free to choose - ok, let's restrict ourselves to dice that actually exist. Is there a 13-sided die? |
|
Normal dice are 2,4,6,8,10,12,20. You can pretty much make any dice though, but it'll look odd, and role even odder, which is why they're hard to make..
If you had a 13 dice , the 4 dice could give the color, and the 13 dice the number.
if you use a 6,8 and 10-die you can get 97.5% chance at a good cast in the first try.. (480 values, 468 of which give you a card)
|
| « Last Edit: Nov 28th, 2002, 9:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #5 on: Nov 28th, 2002, 8:59am » |
Quote Modify
|
So if you have a 20-sided die handy and don't care to roll it 13 times:
You can do it in exactly 13 rolls.
It's always nice to have a solution that precludes any chances of never terminating. 
BTW: I remember that I've already seen a 100-sided "die". Well, it looks almost like a sphere of course.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: card simulation
« Reply #6 on: Nov 28th, 2002, 9:11am » |
Quote Modify
|
I find it hard to see how they could make a balance 100-sided die.. There's now way to make it from regular faces in a regular way..
hmm.. actually, you could make it as a sort of disc.. a 50 sided piramid with it's base on another 50 sided piramid..
of course you can make a similar thing with 26 faces on each side.. Which gives you a balanced 52 sided die.. (But it won't role all that well, and will be horrid in gameplay, not to mention large)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #7 on: Nov 28th, 2002, 9:48am » |
Quote Modify
|
The 100-sided die was actually made up of (at least) two parts: an outer shell an an inner part with the numbers on the faces.
I think it works like this: The inner part is free to move within the shell, while the shell always stops "rolling" with the same spot on top, marking one of the faces of the inner part by a circle as the result. But I really can't remember the details...
Wait, I found a pic on the net: http://www.deigames.com/100sided.html
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: card simulation
« Reply #8 on: Nov 28th, 2002, 11:59am » |
Quote Modify
|
Oops, I forgot to subtract 42. I incorrectly converted from how this would be done in C++ where the "dice" are numbered from 0 to 5.
The consensus seems to be that the question meant to include "dice" other than cubes. However I still find it hard to believe somebody who can't find a deck of cards would have all those dice.
With two rolls (8d and 20d) a card can be picked 97.5% without additional rolls.
With three rolls (6d, 20d, 20d) 99.67% of the time. With four rolls (6d, 20d, 20d, 20d) 99.9917%.
If the goal is to minimize expected number of rolls required. The expected number of times is 2.0513 by using 8d and 20d, and rerolling both if you fail on the first try. A better expectation is obtained (2.047 rolls expected) with a slight modification:
If 8d and 20d give a value greater than 156, the remainder is a random value from 1 to 4. If the remainder is 4, reroll both dice as before. If it is 1 to 3, combine it with a roll of 20d to give a value from 1 to 60. If greater than 52, remainder is a random value from 1 to 8, which is like a free roll from the 8d. Combine with a roll from the 20d and proceed as from the beginning of the process.
|
|
IP Logged |
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: card simulation
« Reply #9 on: Nov 28th, 2002, 4:46pm » |
Quote Modify
|
I'm still trying to figure out some non base-10 solution. Using a 6 sided die, you can simulate 2 sided die (odss/evens) and 3 sided die (1-6,2-5,3-4 pairs) and of course the 6 sided die. Maybe some mixture of weird base-n type solution?
You should be able to make any n sided die by getting a cylindrical shape with the required number of sides? (with the ends sharpened to a point of course) This is how they normally do a 3 sided die - 3 sided cylinder with pointy ends. Sort of looks like a pencil with both ends sharpened.
|
|
IP Logged |
|
|
|
luke's new shoes
Guest
|
it depends how u intepret the question. the best way to do it might be the most efficient way, or an easy to remember way might be the best way to someone else.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #11 on: Nov 29th, 2002, 2:23am » |
Quote Modify
|
on Nov 29th, 2002, 1:14am, luke's new shoes wrote:| an easy to remember way might be the best way to someone else. |
|
I like that interpretation. In this context it would be very useful to have a 13-sided die.
Here in Germany many traditional card games use a deck with fewer cards (and different names for J,Q,K): the numbers run from 7 on upwards while there are still four suits. I know the solution to this modification is below your standards, but I felt like sharing some trivia.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: card simulation
« Reply #12 on: Nov 29th, 2002, 5:57am » |
Quote Modify
|
OK how about how about using the first die with odd/even for red/black. Then using 3 dice of 1-6/2-5/3-4 triplet, you can generate a base-3 number between 1 to 27 (inclusive), so you have probability of 1/27 to re-roll to get something between 1 to 26.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: card simulation
« Reply #13 on: Dec 1st, 2002, 9:24pm » |
Quote Modify
|
Quote: So if you have a 20-sided die handy and don't care to roll it 13 times:
You can do it in exactly 13 rolls.
It's always nice to have a solution that precludes any chances of never terminating. |
|
I would dispute this. With 13 rolls of a d20, you have 2013 possible rolls. You're saying that you can map those rolls to the set {1..52} such that the same number of rolls maps to each number? That would require that 2013 be an exact multiple of 52, which of course it's not. Unless you have some die which is a multiple of 13, you cannot generate a uniform random card in a guaranteed-bounded number of rolls.
I've seen d100s, too, by the way... The ones I saw looked pretty much like golf balls. I'm almost certain that they're not perfectly fair, but they're a good enough approximation for most purposes.
By the way: I suspect that the optimal solution (i.e., minimum expected number of rolls) will never do things like using a single roll for red/black. That's throwing away information which you may as well use elsewhere. By the same token, assuming we're restricting ourselves to the standard dice set of 4,6,8,10,12,20, we might as well not use the 4, 6, or 10 at all, since these can be simulated by other dice with bonus information thrown in for free.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #14 on: Dec 2nd, 2002, 3:48am » |
Quote Modify
|
on Dec 1st, 2002, 9:24pm, Chronos wrote:
I would dispute this. With 13 rolls of a d20, you have 2013 possible rolls. You're saying that you can map those rolls to the set {1..52} such that the same number of rolls maps to each number? That would require that 2013 be an exact multiple of 52, which of course it's not. Unless you have some die which is a multiple of 13, you cannot generate a uniform random card in a guaranteed-bounded number of rolls. |
|
You're right. I retract my proposition. Always makes me wonder how I fall for a mantrap I've actually discerned already.
Interestingly, this seems to have gone unnoticed for quite a while...
Quote:| By the way: I suspect that the optimal solution (i.e., minimum expected number of rolls) will never do things like using a single roll for red/black. That's throwing away information which you may as well use elsewhere. By the same token, assuming we're restricting ourselves to the standard dice set of 4,6,8,10,12,20, we might as well not use the 4, 6, or 10 at all, since these can be simulated by other dice with bonus information thrown in for free. |
|
I see your point and I agree. Do you think that, by this very argument, one can claim that the optimal solution will use the d20 only?
Maybe one should define two distinct optimal (in the minimum expected number of rolls sense) solution problems:
Firstly using d6 only (as they are most likely available to anyone wanting to simulate random selection of a card using dice), secondly using the set {4, 6, 8, 10, 12, 20}.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: card simulation
« Reply #15 on: Dec 2nd, 2002, 5:23am » |
Quote Modify
|
If you role a d20 13 times only 20 times out of 8.192*1016 would you need to rerole, if that worth the bother (which it isn't in any real-life situation)
A normal dice is probably less fair..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: card simulation
« Reply #16 on: Dec 6th, 2002, 12:13am » |
Quote Modify
|
Quote:| I see your point and I agree. Do you think that, by this very argument, one can claim that the optimal solution will use the d20 only? |
|
That depends. Do you mean the solution for the specific deck-of-cards problem, or the solution for simulating an arbitrary die? In the latter case, we definitely don't want to restrict ourselves to the d20: A d12 will do a much better job of simulating a d12 than a d20 will.
I suspect that we'll also want to keep the d12 around for the 52 problem, but I can't prove it. I likewise suspect-without-proof that we can safely junk the d8. At worst, we can simulate a d8 with two rolls of a d20, and with oodles of extra information.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: card simulation
« Reply #17 on: Dec 6th, 2002, 1:45am » |
Quote Modify
|
on Dec 6th, 2002, 12:13am, Chronos wrote:
That depends. Do you mean the solution for the specific deck-of-cards problem, or the solution for simulating an arbitrary die? |
|
I was referring to the deck-of-cards problem. Even in this case the optimal solution doesn't always use the d20 only - if you consider the number of cards a variable.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove