17
$\begingroup$

There are seven days in a week. Let's say you want to pick one at random, such that each day has an equal chance of being picked as each other day. In other words, the goal is to obtain a uniform random 1/7 chance of picking any of the seven days.

But all you have is a coin and a six-sided die (not dice, you don't have 2 dice, you have only 1 die). What procedure of coin-flipping and/or die-rolling should you use to get a 1/7 chance?

(EDIT: I originally intended a coin that can only give a 1/2 result. However, there was a decent out-of-the-box answer about rollable coins that I found pretty useful.)

I know of two ways to do this, but they're slightly out-of-the-box solutions. I consider them valid solutions but want to see what you guys think. Of course, I'll let people try to answer first before revealing my solutions.

Hint: don't try anything like trying to pick a random number in your head. The only things you can use are the coin and die.

EDIT: I'm going to post the four answers I know of in the most compact and simple way (in my humble opinion). Everyone who answered so far has given the equivalent of one of these answers:

Method 1.

Roll the die and flip the coin. This gives 12 possibilities: 1T, 2T, 3T, 4T, 5T, 6T, 1H, 2H, 3H, 4H, 5H, 6H. Assign seven days of the week to seven of those values. If the result is one of the remaining five, just repeat the process until you get a valid value. This has a 5/12 (41.67%) chance of repeating.

Method 2.

Flip the coin three times (and be sure to record it in order of course). This gives 8 possibilities: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. Assign seven days of the week to the first seven of those values. If your result is the eighth value, repeat the process until you get a valid value. This has a 1/8 (12.5%) chance of repeating.

Method 3.

Roll the die twice (and be sure to record them in order because a 2 and 5 is not the same thing as a 5 and 2 in the sample space!). This gives 36 possibilities: 1&1, 1&2, 1&3, 1&4, 1&5, 1&6, 2&1, 2&2, 2&3, 2&4, 2&5, 2&6, 3&1, 3&2, 3&3, 3&4, 3&5, 3&6, 4&1, 4&2, 4&3, 4&4, 4&5, 4&6, 5&1, 5&2, 5&3, 5&4, 5&5, 5&6, 6&1, 6&2, 6&3, 6&4, 6&5, 6&6. Assigned 7 days of the week, but do that 5 times. This uses up 35 values. If your two rolls results in the 36th value, just repeat the process until you get a valid value. This has a 1/36 (2.78%) chance of repeating, which is much smaller than the previous two methods.

Method 4:

Roll the coin. If it's a 7-sided rollable coin, then just see which side ends up closest to some arbitrary direction, like north, or arbitrary marker, such as a stick in the ground. If it's a circular coin, you could theoretically mark the coin to divide it into 7 sectors and then see which sector points towards your arbitrary thing. There was also an idea of constructing a Roulette Wheel with 7 sectors. I know I said you only have the coin and die, but then you could just label some sectors on the ground and use that as your roullette wheel, and presumably find some way to confine the coin there or just roll again if it escapes. So I think this idea too is valuable.

Some concluding thoughts...

Now that I think about it, you could extend the multiple rolls/tosses. If you flipped the coin 6 times, that's 64 possibilities, and 63 is evenly divisible by 7 so you can assign days of the week to that, and just repeat if u get the 64th value (1 out of 64 chance = 1.56%!). You could roll the die 4 times for 1,296 possibilites. 1,295 is divisible by 7, so assign days of the week evenly to all those values, and just repeat if u get the 1,296th value (1 out of 1,296 chance = 0.08%!!). You can probably go even further with them, but it's a trade off of doing more rolls/tosses, which takes a longer time and might take longer to compute the result, than just taking the 1/36 chance of having to repeat via the two-roll method, for example.

$\endgroup$
15
  • 1
    $\begingroup$ This puzzle illustrates a cool concept! If you want to read more the generation of arbitrary random variables with just a fair coin, see if you can find "The Complexity of Nonuniform Random Number Generation," by Donald Knuth and Andrew Yao. $\endgroup$ – Mike Earnest Jun 13 '15 at 4:48
  • 2
    $\begingroup$ This gets asked on Math.SE every so often: math.stackexchange.com/questions/1273214/…, math.stackexchange.com/questions/1314460/…, probably some others... $\endgroup$ – Micah Jun 13 '15 at 6:21
  • 7
    $\begingroup$ What's the significance of asserting that there is only one die? Can't I roll it $n$ times to simulate having $n$ dice? $\endgroup$ – David Richerby Jun 13 '15 at 13:53
  • 2
    $\begingroup$ relevant post on math.se $\endgroup$ – Glen_b Jun 14 '15 at 7:11
  • 1
    $\begingroup$ Related questions are also posted on RPG.SE from time to time (1, 2), though apparently no one asked about simulating a d7 yet. $\endgroup$ – Bubbler Jan 29 at 6:49

15 Answers 15

19
$\begingroup$

There is a way that doesn't use the dice (3+ coin-flips):

  • Flip the coin three times and record 1 or 0 for heads or tails.
  • If all three numbers are zero start again.
  • Otherwise read the 1s and 0s as a binary number. Its value will be from 1 to 7 inclusive with each number having an equal probability of occurring.

Here's a summary of Mike's answer (2+ dice-rolls):

  • Roll the dice twice call the results π‘Ž and 𝑏. If both results are 1 roll again.
  • Otherwise calculate (π‘Ž - 1) Γ— 6 + (𝑏 - 1) Divide that number by 7 to find the remainder. The remainder is in the range 0 to 6 inclusive, add 1 if you want 1 to 7.
$\endgroup$
5
  • $\begingroup$ Yep you got one of the solutions! There is another though, and it might be a more practical solution. Also, there might be a question if, in a purely mathematical sense, is it a valid algorithm? Because theoretically it could never end (you could get all zeros many times in a row). However, I think it's a valid solution. $\endgroup$ – DrZ214 Jun 13 '15 at 1:54
  • $\begingroup$ @DrZ214 No more or less so than the possibility that your coin lands on its side and your die balances on its corner for every roll in any other solution, though, or that the universe undergoes false vacuum decay in the middle of your throw, or whatever. $\endgroup$ – Jason C Jun 13 '15 at 5:25
  • 1
    $\begingroup$ @DrZ214 Theoretically it always ends, with probability 1. The probability that you will repeatedly get all zeroes, forever, is finite and is exactly zero. So, no, there is no issue here. $\endgroup$ – Thomas Jun 13 '15 at 10:24
  • 1
    $\begingroup$ @DrZ214 On average, the procedures given are very efficient: you need to repeat the coin-tossing procedure an average of 8/7=1.14 times and the dice-throwing procedure an average of 36/35=1.03 times to get an actual answer. If you're in the UK, you're about four times more likely to win the national lottery (about one in 14 million) than to have the dice procedure fail five times in a row (about one in 60 million). $\endgroup$ – David Richerby Jun 13 '15 at 12:43
  • $\begingroup$ @DrZ214 mathematically, yes, these are algorithms. They're randomized algorithms of the Las Vegas type. They always terminate with a valid result (a day of the week) and they terminate in finite expected time under the assumption that your coins and dice are fair. $\endgroup$ – hobbs Jun 14 '15 at 18:35
6
$\begingroup$

Roll the die twice, to generate a random number between 0 and 35. Specifically, subtract one from each roll, and have the first roll be the "tens" digit of a number in base 6, and the second roll be the ones digit.

If the result nonzero, return the remainder of the result (mod $7$). If the result is zero, then repeat until it is nonzero.

This gives one of the numbers $0$-$6$ with equal probability, which correspond to the seven days of the week.

This process will take $\frac2{1-\frac1{36}}\approx 2.06$ rolls on average.

$\endgroup$
11
  • $\begingroup$ Yep you got the other solution! Because 36 is so close to 35 (divisible by 7). This is probably more practical than the die because you only have a 1/36 chance of having to repeat it, instead of 1/8. Nevertheless, in a purely mathematical sense, is it a valid algorithm? Because theoretically it could never end (you could get zero many times in a row). However, I think it's a valid solution because it will certainly work in real life. $\endgroup$ – DrZ214 Jun 13 '15 at 1:58
  • 2
    $\begingroup$ It could never end, but this has a probability of zero of happening. This process will stop almost surely. $\endgroup$ – Mike Earnest Jun 13 '15 at 1:59
  • 7
    $\begingroup$ Whether or not this counts as a solution, it is the best you can do: no finite process with a die and coin can simulate a uniform seven way choice. $\endgroup$ – Mike Earnest Jun 13 '15 at 2:31
  • 1
    $\begingroup$ @JustinMorgan it probably has to do with the prime factors of 6 and 2, which are 2, 3, and 6. Multiply up these numbers any way you want, however many times you want, and you will never get a number with a factor of 7. This is one reason I considered my puzzle to be a bit clever. $\endgroup$ – DrZ214 Jun 13 '15 at 2:48
  • 3
    $\begingroup$ @DrZ214 That's exactly what it is. The number of possible outcomes must be evenly divisible by 7. With repeating, it's possible to use any die to simulate any other die. What's really interesting is doing it without repeating. In two dimensions any polygon with a multiple of 7 sides works, using modulo as in this method. None can in three dimensions, or four, or five. In 6 dimensions, and any dimension one less than a multiple of seven, the simplex (equivalent of a tetrahedron) works. In dimensions that are a multiple of 7, the n-cube works. No other shapes in any other dimension work. $\endgroup$ – evankh Jun 13 '15 at 4:43
5
$\begingroup$

Here's an answer that may take more steps to complete but is a lot more intuitive to think about:

Roll the die and flip the coin simultaneously. If the coin lands on heads, read the die value. If the coin lands on tails and the die lands on 1, get the value 7. Else, repeat the process.

$\endgroup$
4
  • $\begingroup$ This gives the following distribution: Heads 1,2,3,4,5,6. Tails 7,repeat, repeat, repeat,repeat, repeat. I like it, but it's less efficient than the 2 dice method as you're rejecting 5/12 of tries instead of 1/36. $\endgroup$ – Level River St Jun 13 '15 at 13:47
  • $\begingroup$ @steveverrill Yes, but it is a lot easier to think about, especially during board games / RPGs, when not every participant is good at maths. $\endgroup$ – user12205 Jun 13 '15 at 14:45
  • $\begingroup$ @ace the sample space is 12 possibilities. You've basically assigned days of the week to 7 of those possibilities, and the remaining 5 are invalid so you repeat. The ultimate result is a uniform 1/7 chance, but because you have a 5/12 chance of repeating (pretty close to 50%), I don't think it's as good as Bob's and Mike's solutions (which have only a 1/8 and 1/36 chance of repeating respectively). $\endgroup$ – DrZ214 Jun 13 '15 at 22:22
  • 1
    $\begingroup$ @DrZ214 This solution is not meant to be efficient, in a mathematical sense. It is meant to be simple to understand, even if you are playing games with mathematically <s>handicapped</s> not-so-talented people. Imagine explaining the mathematical formula to kids trying to play your board game. Or imagine the players spending five minutes per dice roll trying to figure out what value the dice represent, then realize they have made an arithmetic mistake three rounds later. I'm not implying any solution is better - it depends on the circumstances, which is why I wrote this extra answer. $\endgroup$ – user12205 Jun 14 '15 at 1:50
5
$\begingroup$

This is a slightly lateral-thinking answer, and is definitely against the spirit of the question, if not its letter. But there's a lot to recommend this approach, enough that I felt it was worth providing.

Now, I need to begin by admitting that this approach is only convenient if you happen to live in Westeros, from Game of Thrones. (And if you do, my condolences).

However, to make up for that requirement, it's worth pointing out that this approach requires no maths or probability calculations at all. Additionally, it only ever requires a single roll. No rerolls, no use of base-6 numbers, etc. All of which is probably a bit of a relief to you if you do happen to live in Westeros, as statistically you've probably had no mathematical schooling at all. (again, my condolences)

But those of us living in the real world can use this method too; it just requires us to first purchase a very particular (and slightly expensive) licensed coin.

In the mythos of the show, one common coin is the Copper Star of Robert Baratheon

Image of the coin

Notably, the "tails" side of the coin depicts a seven-pointed star.

So all one needs to do in order to generate an evenly distributed 1/7 chance with a die and a coin is:

  1. Number the points of that star from 1-7.
  2. Roll the die and the coin together into the rolling area.
  3. If the coin lands face-up, flip it over to be face-down (without looking!).
  4. Imagine a line drawn from the center of the coin to the center of the die. See which of the seven points of the star on the coin is closest to that line, and that's your result.

See? Probability can be easy, if you're not wedded to solving it with maths!

$\endgroup$
7
  • $\begingroup$ (of course, the critical flaw with this answer is that if you live in Westeros, the days of the week appear not to have names, or any precise number. So while you have the perfect coin with which to randomly select a day of the week, and it's commonly available, you don't have the days of the week from which to select!) $\endgroup$ – Trevor Powell Feb 10 '16 at 12:40
  • 1
    $\begingroup$ You could do the same type of thing with a heptagonal coin, such as a 20p from the UK. $\endgroup$ – f'' Feb 10 '16 at 13:06
  • $\begingroup$ @f'' That's awesome; I had no idea there were 7-sided coins out there in the real world! I clearly need to get out and see more of the world! More 7-sided coins $\endgroup$ – Trevor Powell Feb 10 '16 at 13:10
  • $\begingroup$ I'm impressed with this answer but not 100% convinced of its authenticity. Can you perform this method say 100 times and record each outcome? If it's authentic, you should get pretty close to a uniform spread (Sunday happens about 14 times, Monday about 14 times, etc). BTW don't you need an enclosed rolling area so the coin and die bounce but stay near each other? $\endgroup$ – DrZ214 Feb 11 '16 at 7:07
  • 1
    $\begingroup$ update: A few minutes testing with real (albeit not the one pictured) coins suggests that this strategy would work better on a hard surface than a soft one, and better with heavy coins than light ones. (hypothesis: soft surfaces or light coins tend to result in the coin interacting with the tabletop less; they just bounce once and settle, whereas a heavier coin will bounce many times and roll around while maintaining contact with the table). My Australian 50c piece on a hardwood table randomised quite well, in casual testing, but less so on a bed, and less so with a smaller coin. $\endgroup$ – Trevor Powell Feb 12 '16 at 23:48
3
$\begingroup$

In general, you can roll any real probability with a coin. Write out the decimal expansion of the probability, say its .1010101 etc. Have the first coin flip determine the first digit after the decimal, then the second flip determines the second digit, etc. If at any point the number determined by the coin flips can be proven to be larger or smaller than the probability then we are done and we choose based on larger or smaller.

$\endgroup$
4
  • $\begingroup$ This is better than one might think. Note that the average number of throws is two. $\endgroup$ – ttw Jun 30 '17 at 4:21
  • $\begingroup$ @ttw: surely the average is log(7)/log(2) ~= 2.8..., for an unbiased number 1..7. Otherwise that would violate Shannon's Theorem. See Shannon entropy of a fair die, which is the N=6 case. $\endgroup$ – smci Jan 29 at 21:15
  • $\begingroup$ @smci You are talking about generating a random number from 1 to 7, while ttw asserts that this method generates a Bernoulli distribution random number (i.e. 0 or 1) in an average of two steps (which is what this answer describes). $\endgroup$ – WhatsUp Feb 1 at 11:32
  • $\begingroup$ @WhatsUp: surely you only get Bernoulli distribution when you add the trials, not concatenate them into a vector. So I don't see that's what ttw is saying. Also surely Faraz means binary expansion not decimal expansion, otherwise you couldn't model fractions like 1/7 = 0.14286... $\endgroup$ – smci Feb 2 at 5:52
1
$\begingroup$

Throw the die into the corner of a box, giving you 8 possibilities. Add together the scores of the three exposed faces around the exposed corner:

     +---+                   +---+
   6 | 3 | 9              14 | 3 | 11
 +---+---+---+           +---+---+---+
 | 2 | 1 | 5 |           | 5 | 6 | 2 |
 +---+---+---+           +---+---+---+
   7 | 4 | 10             15 | 4 | 12
     +---+                   +---+

Now divide the score by 7 and take the remainder. Every number 0-6 occurs once, except 0, which occurs twice. Roll again on 14.

7 (or 14)-->0    (Roll again on 14.)   
       15-->1 
        9-->2  
       10-->3
       11-->4  
       12-->5 
        6-->6       
$\endgroup$
2
  • $\begingroup$ If you're going to use a box type arrangement would it be more effective to have a circle divided into seven parts and spin the coin, using the pattern on its head side to give a direction and thus point to which day of the week you want? $\endgroup$ – Jack Aidley Jun 14 '15 at 12:22
  • $\begingroup$ @JackAidley That would require making something (accurate drawing), whereas most people should have a box lying around. Also, how would you keep the coin in the centre of the circle? $\endgroup$ – Level River St Jun 14 '15 at 13:53
1
$\begingroup$

Generalizable suboptimal incremental-roll approach

[Gotta present this after being inspired by 2012rcampion's answer to a different question and by FarazMasroor's unacknowledged partial answer here, which would have benefited from more (and more accurate) detail. This also turned out to be eerily similar to an answer at Mathematics SE.]

Here's a close-to-optimal approach that adapts readily to any desired outcome distribution with any-sided dice. A random fraction between 0 and 1 is generated to fairly pick a point on an arbitrary inverse cumulative distribution function.

Start with fractions for $\,\textsf{Monday}=0/7\,$ through $\,\textsf{Sunday}=6/7\,$ in their base 6 expansions.

$$\begin{array}{rcr} \textsf{ Monday}= 0/7=.000000\textrm{...}\!\:_6 &~~& \textsf{ Friday}= 4/7=.323232\textrm{...}\!\:_6 \\ \textsf{ Tuesday}= 1/7=.050505\textrm{...}\!\:_6 && \textsf{ Saturday}= 5/7=.414141\textrm{...}\!\:_6 \\ \textsf{Wednesday}= 2/7=.141414\textrm{...}\!\:_6 && \textsf{ Sunday}= 6/7=.505050\textrm{...}\!\:_6 \\ \textsf{ Thursday}= 3/7=.232323\textrm{...}\!\:_6 \end{array}$$

Now begin rolling repeatedly, appending each result as the next digit of a lengthening base-6 fraction, treating each roll of ‘$6$’ as the digit $0$.

Keep rolling as long as the cumulative digit sequence matches one of the days' base-6 fractions listed above. When a digit fails to match, select the day with the largest fraction that is below what resulted from the rolls. The exception to these rules is when the first two rolls amount to $.00\!\:_6$, in which case call it a $\textsf{Monday}$ and be done.

This means that we are done after 2 rolls unless those rolls amount to some day's fraction's first 2 digits:

$$ .05\!\:_6 \qquad .14\!\:_6 \qquad .23\!\:_6 \qquad .32\!\:_6 \qquad .41\!\:_6 \qquad .50\!\:_6 \qquad $$

This gives a 6/36 = 1/6 chance of needing a 3rd roll. Each subsequent roll also leaves a compounded 1/6 chance of needing yet another roll. So:

$$\begin{array}{c} \textsf{average number of rolls} ~=~ 2 + \frac16 \Bigl( 1 + \frac16 \bigl( 1 + \frac16 ( 1 + \dots ) \bigr) \Bigr) ~=~ 2.2 \end{array}$$

Example

If the first 2 rolls were ‘$1$’ and ‘$5$’, the randomly-selected day would be $\textsf{Wednesday}$ because $.15\!\:_6$ does not begin any day's fraction and:

$$\textsf{Wednesday}=.141414\textrm{...}\!\:_6~<~.15\!\:_6~<~.232323\textrm{...}\!\:_6=\textsf{Thursday}$$

If those rolls were ‘$1$’ and ‘$4$’, however, we would roll again because $\textsf{Wednesday}$'s fraction begins with $.14\!\:_6$. If the next roll comes up ‘$0$’, which produces $.140\!\:_6$, the randomly-selected day would be $\textsf{Tuesday}$:

$$\textsf{Tuesday}=.050505\textrm{...}\!\:_6~<~.140\!\:_6~<~.141414\textrm{...}\!\:_6=\textsf{Wednesday}$$

Variation with alternating die rolls and coin flips

This is in the full spirit of the puzzle's title. Use a hybrid of bases 6 and 2, where the first fractional digit is in base 6, the next in base 2, then base 6, then 2 again, and so on. This is effectively base 12 with pairs of numerals.

$$\begin{array}{r} \textsf{ Monday}=0/7= ~.00~00~00~00~00~00~ ~~00~00~00~00~00~00~...\!\,_{6\backslash2} \\ \textsf{ Tuesday}=1/7= ~.01~40~30~50~11~21~ ~~01~40~30~50~11~21~...\!\,_{6\backslash2} \\ \textsf{Wednesday}=2/7= ~.11~21~01~40~30~50~ ~~11~21~01~40~30~50~...\!\,_{6\backslash2} \\ \textsf{ Thursday}=3/7= ~.21~01~40~30~50~11~ ~~21~01~40~30~50~11~...\!\,_{6\backslash2} \\ \textsf{ Friday}=4/7= ~.30~50~11~21~01~40~ ~~30~50~11~21~01~40~...\!\,_{6\backslash2} \\ \textsf{ Saturday}=5/7= ~.40~30~50~11~21~01~ ~~40~30~50~11~21~01~...\!\,_{6\backslash2} \\ \textsf{ Sunday}=6/7= ~.50~11~21~01~40~30~ ~~50~11~21~01~40~30~...\!\,_{6\backslash2} \end{array}$$

For a die roll, again treat ‘$6$’ as $0$. For a coin flip, call heads $0$ and call tails $1$.

Similar to before, repeatedly accumulate digits, alternately rolling and flipping, as long as the sequence of digits matches some day's (other than $\textsf{Monday}$'s) fraction:

$$\begin{array}{r} \textsf{average number of alternating rolls and flips} ~=~ \phantom{2.636363...} \\ 2 + \frac6{12} \Bigl( 1 + \frac16 \bigl( 1 + \frac12 \bigl( 1 + \frac16 \bigl( 1 + \frac12 ( 1 + \dots ) \bigr) \bigr) \bigr) \Bigr) ~=~ 2.636363... \end{array}$$

Comparison to an optimal(?) system with alternating die rolls and coin flips

A less-inspired (but optimal?) system uses an average of approximately 2.479 alternating rolls and flips. Without coin flips, the same approach matches the average of 2.057 die rolls posted in other solutions.

This table outlines a repeated 12-action pattern of whether or not a day will be selected by each successive die roll or coin flip.

\begin{array}{lcccccc} &\textrm{ } &\textrm{ } &\textrm{ } &\!\!\textrm{Potential} &\!\!\textrm{Left- } &\textrm{Proba- }\! \\[-.5ex] &\!\textrm{Probability} &\!\textrm{Continued }\! &\textrm{Combined } &\!\textrm{outcomes }\! &\!\!\textrm{over } &\!\textrm{bility } \\[-.5ex] &\!\textrm{of reaching} &\textrm{potential } &\!\textrm{potential } &\textrm{assigned } &\!\!\textrm{potential} &\textrm{of con- }\! \\[-.5ex] \!\!\!\textrm{Action} &\textrm{the action } &\textrm{outcomes } &\!\textrm{outcomes } &\textrm{to days } &\textrm{outcomes } &\textrm{tinuing } \\[1ex] \textrm{roll}_1 & 1 ~~ \!& & 6 & 0 & 6 & 6/6~ \\ \rlap{\textrm{(cycle begins)}} \\ \bf\textbf{flip}_2 & 1 ~~ \!&\bf 6 &\bf 12 &\bf 7 &\bf 5 &\bf 5/12 \\ \textrm{roll}_3 & 5/12 \!& 5 & 30 & 28 & 2 & 2/30 \\ \textrm{flip}_4 & 1/36 \!& 2 & 4 & 0 & 4 & 4/4~~\\ \textrm{roll}_5 & 1/36 \!& 4 & 24 & 21 & 3 & 3/24 \\ \textrm{flip}_6 & 1/288 \!& 3 & 6 & 0 & 6 & 6/6~~\\ \textrm{roll}_7 & 1/288 \!& 6 & 36 & 35 & 1 & 1/36 \\ \textrm{flip}_8 & 1/10368 \!& 1 & 2 & 0 & 2 & 2/2~~\\ \textrm{roll}_9 & 1/10368 \!& 2 & 12 & 7 & 5 & 5/12 \\ \textrm{flip}_{10}& 5/124416 \!& 5 & 10 & 7 & 3 & 3/10 \\ \textrm{roll}_{11}& 1/82944 ~\!& 3 & 18 & 14 & 4 & 4/18 \\ \textrm{flip}_{12}& 1/373248 \!& 4 & 8 & 7 & 1 & 1/8~~\\ \textrm{roll}_{13}& 1/2985984\!& 1 & 6 & 0 &\bf 6 & 6/6~~\\ \rlap{\textrm{(cycle repeats)}} \\ \bf\textbf{flip}_{14}&\bf1/2985984\!&\bf 6 &\bf 12 &\bf 7 &\bf 5 &\bf 5/12 \\ \textrm{roll}_{15}& 5/35831808\!&\bf 5 & 30 & 28 & 2 & 2/30 \\[-1ex] \textrm{flip}_{16}& \vdots &\vdots&\,\vdots&\vdots&\vdots&\vdots\; \\[-1ex] ~~~\vdots \end{array}

The row for $\bf\textbf{flip}_{14}$ , for example, shows that:
$\bf 1/2985984$ is the probability that this coin flip will be required.
$\bf 6$ equally-likely continuing outcomes, die rolls {1,2,3,4,5,6 }, are carried forward from the previous action, $\textrm{roll}_{13}$ .
$\bf 12$ potential combined outcomes, {1,2,3,4,5,6 } × { H,T }, are now considered for this coin flip's 2 possible results, {Heads,Tails}.
$\bf 7$ of the potential ordered outcomes are arbitrarily assigned to select a day:
    {1& H } = Mon, { 2 & H } =Tues, ..., { 6  & H } = Sat and {1&T } = Sun.
$\bf 5$ unassigned potential ordered outcomes, { 2 &T, 3 &T, ..., 6 &T }, remain left over to combine with the next action if the present action doesn't complete the process by selecting an assigned day.
$\bf 5/12\:$ is the corresponding probability of proceeding to the next action, $\textrm{roll}_{15}$.

If the next action is necessary, the row for $\textrm{roll}_{15}$ shows that the $5$ unassigned potential ordered outcomes from $\textrm{flip}_{14}$ are combined with the possible results of a new die roll to produce $30$ new potential ordered outcomes:
    { 2 &T&1,   3 &T&1,  ...,  6 &T&1,
      2 &T& 2 , 3 &T& 2 , ...,  6 &T& 2 ,
       $^\vdots$
      2 &T& 6 , 3 &T& 6 , ...,  6 &T& 6 }
Of those combinations, $28$ would select days while $2$ will be left over, leaving a $2/30$ chance of requiring yet another action, $\textrm{flip}_{16}$.

Compounding the table's rightmost column of continuation probabilities gives:

\begin{array}{l} \textsf{average number of alternating rolls or flips} = \\ \qquad 1 + \frac6{6} \Bigl( 1 + \frac5{12} \bigl( 1 + \frac2{30} \bigl( 1 + \frac4{4} \bigl( 1 + \frac3{24} \bigl( 1 + \frac6{6} \bigl( 1 + \frac1{36} \bigl( 1 + \frac2{2} ( 1 + \ldots ) \bigr) \bigr) \bigr) \bigr) \bigr) \bigr) \Bigr) \\ \phantom{\textsf{average number of alternating rolls or flips}} = 2.4794153... \end{array}

Incidentally, the same calculation with no coin flips is:

\begin{array}{l} \textsf{average rolls for die only} = 1 + \frac66 \Bigl( 1 + \frac1{36} \bigl( 1 + \frac66 \bigl( 1 + \frac1{36} ( 1 + \ldots ) \bigr) \bigr) \Bigr) \\ \phantom{\textsf{average rolls for die only}} = 2.0\overline{571428} \end{array}

$\endgroup$
1
  • $\begingroup$ Nice, I came up with a similar method for a previous question. The "dice rolls as decimals" idea is a really powerful one. I'm currently working on seeing if there's a way to optimally choose between the dice and coin at each step, any ideas? $\endgroup$ – 2012rcampion Feb 9 '16 at 3:38
1
$\begingroup$

I'm posting this solution since it is really different from what has been posted so far. Not because it is efficient. It isn't.

We are working in rounds. Initially each day is in round 0. Now we toss a coin for each day. If the coin lands on heads the day moves on to the next round. We repeat this for every new round, until we end up with a round having only one day left. This day is the answer. If accidentally we end up with a round having no days left at all, we repeat the previous round.

Why does this yield a uniform distribution? We have treated each day the same way.

$\endgroup$
1
$\begingroup$

I'm two years too late, but I feel like this is easier to explain to people playing a board-game with low probability of repeating:

Roll the dice twice (or two dice):

  • If both are 6, roll both again and start over.
  • Else If the first number is 6 -> Sunday
  • Else look at the second number:
    • 1 => Monday
    • 2 => Tuesday
    • ...
    • 6 => Saturday

Each option (excluding the $1/36$ chance of a re-roll) has the chance of $5/35 = 1/7$.

While this is the same in spirit to some of the other answers, pragmatically this method is easier than the tables proposed.

$\endgroup$
1
$\begingroup$

Roll two dice (or roll the die twice) and flip the coin. Sum the dice. Use this table to figure out the result.

Dice Sum Coin Result
5 or 7 H 1
5 or 7 T 2
6 H or T 3
8 H or T 4
9, 10, 11, or 12 H 5
9, 10, 11, or 12 T 6
3 or 4 H or T 7
2 H or T Redo

There are 36 possible dice results, which doubles to 72 when you account for the coin result. Here is the table that shows each result has an equal probability (N is the number of ways each combination can happen):

Sum Coin N Assigned To
7
5
H
H
6
4
1
7
5
T
T
6
4
2
6
6
H
T
5
5
3
8
8
H
T
5
5
4
9
10
11
12
H
H
H
H
4
3
2
1
5
9
10
11
12
T
T
T
T
4
3
2
1
6
3
4
H or T
H or T
4
6
7
2 X 2 Try Again

This method has two main advantages:

  • a) The dice values can be summed, without regard to order (in other words, a 1-3 is the same as a 3-1 in this method)
  • b) There is a low percentage chance of a redo (1 in 36, or 2.778%)

The main disadvantage is probably that, without the table in front of you, it might be hard to remember that, say, Double 5's and Tails means "6", while a 5 and a 2 (i.e., a 7) plus Heads is a "1".

$\endgroup$
4
  • $\begingroup$ Not bad, I proly never would've thought up this way allowing you to sum dice. However, I think it's overall harder because of the chart and coin toss, despite the fact that its simpler to sum dice instead of record their order. The original 2 dice roll method has the exact same chance of a repeat, 1/36, and doesn't need the coin. Still, it is a valid way because you ultimately result in a uniform 1/7 chance for each day. $\endgroup$ – DrZ214 Jun 14 '15 at 1:32
  • $\begingroup$ It's true that other methods don't require a coin, but I kind of liked the way I added the coin in here. It seemed to fit more closely with the original question, which assumed we started with a die and a coin. $\endgroup$ – J.R. Jun 14 '15 at 2:10
  • $\begingroup$ Good point but it was kinda a trick question for that reason. The only ways I originally thought of was to use only the coin (3x) or only the die (2x), so I thought it was sorta a trick question. Now I'm not so sure anymore lol. My comment was basically to agree with your disadvantage, but your answer is valid and has expanded my knowledge. $\endgroup$ – DrZ214 Jun 14 '15 at 2:14
  • $\begingroup$ My table could be tweaked a little bit, too, so that all 9's and 12's result in a "5", and all 10's and 11's result in a "6". That way, if the two dice sum to 3, 4, 6, 8, 9, 10, 11, and 12, we don't need the coin, but if they sum to 5 or 7 we use the coin to determine which of the remaining two days is chosen. It's kind of a cool use of the coin-dice combination. $\endgroup$ – J.R. Jun 14 '15 at 2:22
1
$\begingroup$

Out-of-the-box solutions using just the coin, mostly coin-rolling and not coin-flipping:

  1. You never said the coin was round. It could be a heptagon or Reuleaux (constant-width, hence easily rollable) heptagon, just like the British (or pre-Euro Irish) 50p coin or British 20p coin. (If it isn't, you could clip it into that, although that seems contrived.) Label the sides 1..7 clockwise starting from some recognizable point on the head or tail. Roll it.
    • NOTES: a Reuleaux polygon coin is both perfectly unbiased and rollable, unlike other approaches. Naively clipping the edges off a round coin would create something that was both biased and unrollable. And this actually cites the construction algorithm, it doesn't just conjecture that such a thing might be feasible.
    • you can read the result off a (labelled) polygonal coin near-instantly, unlike a round coin with a polygonal motif.
  2. Roll the coin around a circular track, like a roulette marble, which again has been predivided into seven (or 14, 28 etc.) equal sectors (or you could flip it in the air just to see where it lands and disregard the face it lands on, but the flipping movement is unlikely to be unbiased wrt where it lands).
  3. Even more far-out-of-the-box interpretations:
  • a) only works one-time (your question implied you only want to generate a random number once): use the year-of-issue of the coin, if you know the distribution of years-of-issue of that type of coin, and only if it happens to divide nicely into sevenths. (This is similar to generating random numbers from the 11-digit serial number on a US dollar bill, e.g. by summing and taking them modulo 7, although 11-digit serial nos are far better than coin year-of-issue).
  • b) or, to (repeatedly, unbiasedly) generate arbitrary random numbers (a la "Liar's Poker" with dollar-bill serial numbers), even more "out-of-the-box" interpretation is, we could say the coin has an n-digit RFID serial no.

British 50p coin British 50p coin

Old Irish 50p coin (pre-Euro, last used in 2001) enter image description here

UPDATE: some lists of polygon coins of the world 1) BezalelCoins 2) CoinBrothers

$\endgroup$
8
  • $\begingroup$ Your first solution has already been given, but I haven't seen the other two. $\endgroup$ – bobble Jan 29 at 15:36
  • 1
    $\begingroup$ @bobble: No it's not: a) the point of a reuleaux heptagon is the sides are self-numbering. Can read it instantly. b) I hadn't even seen that answer, and its answer is buried in the sixth pargraph under tons of offtopic chatter. $\endgroup$ – smci Jan 29 at 21:12
  • $\begingroup$ Your a) I'm confused by but if you say it's different, then fine. For b) - please read the other answers before answering an old question, to make sure that your answer is original or adds value in some other way. $\endgroup$ – bobble Jan 29 at 21:14
  • $\begingroup$ No I'm not 'confused'. There are coins that have seven faces. And moreover they are constructed in such a way (constant-width) to be easily rollable. I didn't just point out that was possible, I showed a real-world case. My answer is original and does add value, please stop talking down to me. I always skim the answers. First, methods 2 and 3 I mention are unique. Second, it's not my fault if a way overly chatty answer finally mentions the thing buried in its paragraphs. (I only now notice commenters from 2016 had mentioned the UK 20p - but that's not in the answer; they could have posted it) $\endgroup$ – smci Jan 29 at 21:24
  • $\begingroup$ The details of how a Reuleaux polygon is constructed to be constant-width, and thus easily rollable, are not trivial, and at first glance counterintuitive. This in itself is also noteworthy. Noone else posted that either. $\endgroup$ – smci Jan 29 at 21:26
0
$\begingroup$

Similar to Mike Earnest, I suggest rolling again on a double six, to give you 35 possibilities instead of 36. The question then becomes how to assign the 35 possibilities to the 7 scores you require. The following formula is reasonably easy to calculate, and does not involve any base conversions:

(7+Die1-Die2) mod 7

       Die 1
        1 2 3 4 5 6
        ===========
Die   1|0 1 2 3 4 5
2     2|6 0 1 2 3 4
      3|5 6 0 1 2 3
      4|4 5 6 0 1 2
      5|3 4 5 6 0 1
      6|2 3 4 5 6 X       X=roll again

As can be seen, each score from 0 to 6 appears in the table exactly 5 times.

In plain english, this becomes: "Roll the die twice. Subtract the second roll from the first (if this is not possible because it would give a negative number, add 7 to the value of the first roll before subtracting.) If you roll a double six, discard the score and roll again."

$\endgroup$
3
  • $\begingroup$ This is good and effectively the same as Mike Earnest's answer. Rolling the die 2x gives a sample space of 36. Assign Days 1 to 7 to 7 of those possibilities, and duplicate that 4 more times. That's 35 values. If you get the 36th value, just repeat. The tricky part is keeping track of the die and going in order! If I had given 2 dice, and they're both the same color, is it a 3 and a 4 or a 4 and a 3? Those two possibilities are not equivalent. Usually we don't worry about that cuz we usually sum dice in our traditional games, and A + B = B + A so order doesn't matter there. $\endgroup$ – DrZ214 Jun 13 '15 at 22:28
  • $\begingroup$ @DrZ214 It's the same as Mike Earnest's except the math is easier. It's possible to do this just as well with (Die1+Die2) mod 7 which is traditional adding and avoids the problem you mention. But it introduces another problem: you have to throw away exactly one of the six ways of getting 7: 6+1, 5+2, 4+3, 3+4, 2+5, 1+6. So on balance I think it's better to throw away the double six, and subtract. $\endgroup$ – Level River St Jun 13 '15 at 23:30
  • $\begingroup$ @DrZ214: Just throw two dice and the coin all at once. Redo as long as you get a {3,4,tail}. Add the dice and subtract 7 if it goes above 7. This method is faster to execute than any other method. I can't post an answer because it is protected, but it's almost the same as steveverill's anyway. $\endgroup$ – user21820 Jun 14 '15 at 13:29
0
$\begingroup$

Use this method:

  1. Assign a number on the die to each day of the week i.e. Day 1 = 1, Day 2 = 2 and so on.
  2. For the last two days (days six and seven) in the week, give them both the number 6.
  3. Roll the dice. If you land on the number 6, flip the coin and if its heads, pick day 6, if its tails, you pick day 7. Since the coin has a probability of 1/2, there is a probability of 1/12 of picking either day 6 or day 7 from the start.
  4. If it lands on any other number, flip the coin and if it lands on heads accept the number, if it lands on tails then repeat the whole process. Now every other day has a probability of 1/12 of being chosen as well.
$\endgroup$
3
  • $\begingroup$ This is basically the same as my answer. $\endgroup$ – user12205 Jun 13 '15 at 19:41
  • $\begingroup$ Sorry - hadn't read it. I agree my answer is quite similar in terms of the final probabilities but I guess mine offers a slightly different process tree. $\endgroup$ – Resquiens Jun 13 '15 at 19:49
  • 1
    $\begingroup$ Yea it's basically the same, but u scared me for a second. If you meant to accept all die values 1 - 5 regardless of what the coin does, and only bother with coin if u roll a 6, you will NOT get a uniform chance. You will get a 1/6 chance for days 1 - 5, but days 6 and 7 will both have a 1/12 chance because the coin effectively splits it in half. HOWEVER, i read your 4 rules carefully and that's not what you're saying. It's the same as Ace's answer so the end results will be valid 1/7 uniform randomness. Nevertheless, it has 5/12 chance of repeat, while other answers have only 1/8 or 1/36. $\endgroup$ – DrZ214 Jun 13 '15 at 22:20
0
$\begingroup$

I would use the following method

  1. roll the dice, then flip the coin
  2. if the coin is head, add 6 to the number on the dice.
    This gives you an outcome between 1 and 12 with uniform probability. now if the number is greater than 7 try again.

The way I came up with this solution is trying a simpler problem: getting a number between 1 and 5 with uniform probability with one dice. The solution is to roll the dice, if it is 6 roll again. Basically doing a "modulo" operation.

If you feel comfortable that the one-dice problem works, then the proposed solution working from something that gives you a 1-12 uniform distribution and converting it to a 1-7 uniform distribution also works.

This answer is the same as 'ace'.

A more interesting problem is to prove that there is a solution with a guaranteed finite number of trials. My answer would be no, given than 7, and 2 and 3 are co-prime (their greatest common divisor is 1)

$\endgroup$
1
  • $\begingroup$ This indeed gives a uniform 1/7 chance, but again, you have a 5/12 chance of having to repeat, while other solutions only have a 1/8 or 1/36 chance of repeating. $\endgroup$ – DrZ214 Jun 13 '15 at 22:30
0
$\begingroup$

What we consider "optimal" depends on what we consider the "costs" of various actions. If flipping the coin and rolling the die together has the same "cost" as doing one of them, then we might as well do both. This means that we're dealing with base 12. Each round, we can take the set of possibilities, split it into seven equal subsets, with some possibilities "left over". Each round, if we get one of the "left over" possibilities, we can go another round, and take the Cartesian product of that result and the "left over" possibilities from the previous round.

For the first round, we have five "left over" results. If we get one of those, there are 5*12=60 different combinations for our second round, with four "left over" possibilities. So on the third round, there are 48 combinations, with six "left over". And so on.

$\endgroup$
1
  • $\begingroup$ This seems to be the same as several other answers here, just without a specific system to divide possibilities. $\endgroup$ – bobble Jan 29 at 4:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.