14
$\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?

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 three 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, 7T, 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.

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 2 roll method, for example.

$\endgroup$
  • $\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
  • $\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
  • 5
    $\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
  • $\begingroup$ @DavidRicherby yes u can use it as many times as u want. But it's important to note that you have to record it in order because a 2 and a 5 is not the same result as a 5 and a 2. We only tend to think that way because most board games sum up the dice (and A+B = B+A), but in the sample space, they are not the same. $\endgroup$ – DrZ214 Jun 13 '15 at 23:03
  • $\begingroup$ @DrZ214 - Yet it's possible to devise a method that relies only on the sum, and not the order. $\endgroup$ – J.R. Jun 14 '15 at 1:09

13 Answers 13

16
$\begingroup$

There is way that doesn't use the dice.

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 Mikes's answer:

Roll the dice twice call the results a and b. If both results are 1 roll again.

Otherwise calculate $(a-1)\times6+(b-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$
  • $\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$
  • $\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$
  • $\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$ – ace_HongKongIndependence 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$ – ace_HongKongIndependence 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$
  • $\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
2
$\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$
  • $\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
1
$\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$
  • $\begingroup$ This is basically the same as my answer. $\endgroup$ – ace_HongKongIndependence 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
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$
  • $\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$

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

enter image description here

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):

enter image description here

This method has two main advantanges:

  • 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$
  • $\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$

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$
  • $\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$
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$
  • $\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$

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$
  • $\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

protected by Community Jun 14 '15 at 1:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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