50
$\begingroup$

Suppose you roll a (fair, 6-sided, perfectly ordinary) die repeatedly until you roll a 6. As is well known, the expected (i.e., long-term average over many trials) number of rolls required is 6.

Now suppose we ask this question conditional on never having rolled any odd numbers. That is, suppose you learn that someone has followed the procedure above, and that they rolled only even numbers up to the point where they rolled that 6. What is the expected number of rolls they took?

(That is: What is the expected number of rolls taken to roll a 6, conditional on having got no odd numbers in the process of rolling that 6? The question is not anything like "what's the expected number of rolls next time, given that you didn't get any odd numbers last time?". I've added this paragraph and slightly reworded the question above because it seems from comments that some readers interpreted the question in an unintended way.)


This question is interesting because there is an extremely tempting wrong answer.

Some history: The question seems to have first been asked by Elchanan Mossel while teaching an undergraduate probability course at the University of Pennsylvania in 2014-15. Gil Kalai posted it on his blog as part of his Test Your Intuition series, and then posted a followup. There is interesting discussion in the comments of both. And here is a nice little article about the question, in PDF form.

WARNING: All the links in the paragraph above may take you to places that give away some or all of the solution. If you want to solve the puzzle for yourself, don't follow those links until you've done it.


[See this Meta question for some relevant PSE-specific context, which in particular explains why this is community wiki. An older question has been merged into this one, and it's possible that some details of answers or comments may look odd as a result.]

$\endgroup$
19
  • 10
    $\begingroup$ This is a poorly formulated puzzle. The problem is that we are first given a random number generator with specific properties. The formulation strongly implies that we have a fair six-sided die. We know the properties of such a die: when rolled it will give a result of 1 to 6, each with an equal 1/6 probability, and the result is independent of previous results. But then you go on to say that when rolling this particular die, the distribution of results will not be that, and you are not specific why the die will have a non-standard result distribution. (continued) $\endgroup$
    – MichaelK
    Commented Sep 11, 2017 at 13:42
  • 3
    $\begingroup$ In other words: we cannot be sure what the distribution function of this die actually is. Why are we getting only evens? Is the die unfair so that it only rolls evens? Is someone excluding results when odds are rolled? Do we reset the throw count when odds are rolled? Is there any other reason for the non-uniform result distribution? So it is a poorly formulated puzzle, and I hold the opinion that we do not have the information we need to answer it. $\endgroup$
    – MichaelK
    Commented Sep 11, 2017 at 13:44
  • 12
    $\begingroup$ @MichaelKarnerfors The problem is completely unambiguous as long as you are familiar with conditional probability. If X is a random variable and A is an event, then the expected value of X conditioned on A is $\sum_{n=0}^\infty nP(X=n\cap A)/P(A)$. Here, X is the number of rolls and A is the event that all rolls are even. This is equivalent to both your "exclude roll counts" and "reset throw count" interpretations. $\endgroup$ Commented Sep 11, 2017 at 15:40
  • 3
    $\begingroup$ Yes. To define the event A and random variable X, you must first define the sample space, S, that they live in. Define S to be the set of all finite sequences of die rolls where the last roll is 6 and no previous rolls are 6. Then A is the subset of such sequences which are all even, and X is the function which returns the length of a sequence. This is how the stopping condition is taken into account. @MichaelKarnerfors $\endgroup$ Commented Sep 11, 2017 at 16:57
  • 5
    $\begingroup$ The question does not imply any such thing. That isn't how conditional probability works. It may -- or may not -- be instructive to consider the following question. A fair die is rolled until it comes up 6. Conditional on its having come up 6 on the first roll, how many rolls did it take? Of course the answer to this question is 1, even though it's a fair die and only comes up 6 one-sixth of the time. And yes, coming up 6 on the first roll would be "just a stroke of luck". This is a question about probability, after all. $\endgroup$
    – Gareth McCaughan
    Commented Dec 3, 2017 at 2:59

7 Answers 7

43
$\begingroup$

The answer is indeed...

         112 rolls

            ...because the question is equivalent to...

What is 1 more than the average number of consecutive rolls of only 2s and/or 4s before any other roll terminates the series?

One way to see this equivalence is to note that only 2/4 streaks terminated by 6 are considered. (A first-roll 6 terminates a 2/4 streak of length 0.) Yet the average length of those streaks is the same as of streaks terminated by 1, 3 or 5. Collect all such streaks, including those terminated by 6, and the result is all streaks of 2/4, each with the same expected length.

  Calculations:

    E = expected number of consecutive even rolls up to and including the first 6
     = (expected number of consecutive 2s and/or 4s) + (one more roll of 6)
     = T + 1
where
    T = expected number of consecutive 2s and/or 4s before some other roll
     = (probability of 2 or 4)   ×   (1 for this roll + expected subsequent 2s and/or 4s)
     = 13 (1 + T)
   so
    T = 12
   thus
    E = T + 1
     = 112

$\endgroup$
12
  • 4
    $\begingroup$ Note to possibly add in a future edit: The expected number of rolls is surprisingly small, but that is because most often it will include just 1 roll, a lone 6, as odd numbers are more likely than non-6 even numbers to precede any 6. $\endgroup$
    – humn
    Commented Sep 10, 2017 at 18:09
  • $\begingroup$ Why is the probability of a 2 or 4 only 1/3? Surely if you have been told that all throws were not odd that leave the chance of it being a 2 or 4 as 2/3? $\endgroup$
    – Chris
    Commented Sep 11, 2017 at 14:38
  • 1
    $\begingroup$ Ah... So I think in my interpretation rolls of 1,3,5 are strictly forbidden to occur whereas in your interpretation they may occur but cause the sequence to be discarded and discounted from the results? $\endgroup$
    – Chris
    Commented Sep 11, 2017 at 15:22
  • 2
    $\begingroup$ Sigh, @Chris, all too often the primary puzzle is to figure out what is the actual intended puzzle. Many solutions, too, only make sense to the solver and the puzzle's poser, until comments help point out how much was incorrectly assumed to have been clear. I'm looking forward to adding "discussion" to this solution thanks to your comments. $\endgroup$
    – humn
    Commented Sep 11, 2017 at 15:30
  • 3
    $\begingroup$ As Mike mentioned on the comments to the main question, @Chris, this is not at all ambiguous if you're familiar with conditional probability, but what it basically means is - someone rolled a fair die until they rolled a 6. If I give you the extra information that only evens were rolled, how does this change your expectation of the number of throws? (this does not change the fairness of the die, or the rolling procedure. it's just extra information about how this particular roll went) $\endgroup$
    – ffao
    Commented Sep 11, 2017 at 21:31
40
+200
$\begingroup$

This surprisingly beguiling puzzle may also be solved with a surprisingly unsophisticated approach. Symmetry, by itself, predicts the average length of evens-only sequences ending with 6 to be...

                  ...1 12  throws.

Start with T  many random throws: 2153664315121226553111444142566363625461525 . . 3644464461

Sift them into 4 groups that, due to symmetric criteria, are each expected to include T4  throws.

Every 1 and any preceding 2s/4s:   21......1.121......1114441.............1... . . .........1
Every 3 and any preceding 2s/4s:   ...3..43..........3............3.3......... . . 3.........
Every 5 and any preceding 2s/4s:   ..5......5......55........425......25...525 . . ..........
Every 6 and any preceding 2s/4s:   ....66.......226.............66.6.6..46.... . . .64446446.

The last group, of 6s and their preceding 2s/4s, precisely contains every evens-ending-with-6 sequence considered by the puzzle.   The number of such sequences is just the original number of 6s, as every 6 is in exactly one such sequence.   From 6’s symmetry with the other 5 equally-likely throws —1, 2, 3, 4 and 5 — that number is expected to be T6  sequences.

Thus...

(Average length)   =   (number of throws in these sequences)   /   (number of sequences)

         =   T4 throws   /   T⁄ 6 sequences

         =   1 12  throws /sequence.


Notes

The expected number of rolls seems suspiciously small but, as seen among the example throws above, it reflects the likelihood that most evens-ending-with-6 sequences will be just 1 roll long, a lone 6. This does make sense after all by noting that each sequence-ending 6 has 46  chance of following a 1, 3, 5 or 6(!) that allows no prior rolls to count in that 6’s sequence.

The condition “all throws gave even numbers” is a potent red herring that suggests 6s have equal status to 2s and 4s.   Their status is not equal, however, after retaining all 6s originally rolled but discarding the 34  of 2s/4s that did not lead to 6s.

This solution’s approach does have a loose end, literally, as commented by Artur Kirkoryan. Any stretch of T  throws could end with a streak of 2s/4s that might extend to become a qualifying sequence of any length if allowed to continue. That comment and Deusovi’s reminder to take density into account lead to the realization that possible 2s/4s loose ends would need an infinite expected length to make a difference because any bounded expectation would have a vanishing effect as T  increases without limit. This further leads to acknowledgment that the evens-ending-with-6 sequences in question are only assumed, not proven, to have a finite expected length. Presumption of their nonetheless having a bounded expectation forces any 2s/4s loose ends to also have a bounded expectation and thus not undermine this solution’s approach.

This solution ensued from surprise at the match between the 4 kinds of non-2s/4s throws and the 14  fraction of undiscarded throws exhibited by a Lisp routine’s simulating a million throws at a time.

 ( defun RollEm (many)
   ( let ( (i many) (sixes 0) (streakSum 0) (streak 0) )
     ( while  (>= (setq i (1- i)) 0)
              ( pcase  (1+ (random 6))
                       (   2  ( setq streak   (1+ streak)             ) )
                       (   4  ( setq streak   (1+ streak)             ) )
                       (   6  ( setq sixes    (1+ sixes)              )
                              ( setq streakSum (+ streakSum streak 1) )
                              ( setq streak     0                     ) )
                       ( else ( setq streak     0                     ) )
     )        )
     ( insert ( format "\n%d (%d%%) undiscarded throws / %d streaks  =  %.3f\n"
                       streakSum
                       ( / ( + (* 200 streakSum) many) (* 2 many) )
                       sixes
                       ( / (float streakSum) sixes )
 ) ) )        )

 (RollEm 1000000)     249372 (25%) undiscarded throws / 166527 streaks  =  1.497
        ""            250234 (25%) undiscarded throws / 166972 streaks  =  1.499
        ""            249503 (25%) undiscarded throws / 166256 streaks  =  1.501
        ""            250777 (25%) undiscarded throws / 166953 streaks  =  1.502
        ""            249947 (25%) undiscarded throws / 166791 streaks  =  1.499
$\endgroup$
6
  • 8
    $\begingroup$ Wow, what a brilliant solution! $\endgroup$
    – Deusovi
    Commented Sep 12, 2017 at 16:26
  • 1
    $\begingroup$ This is very nice analysis and I upvoted the answer, but I am not convinced the argument is very rigorous. We still have to argue that the various halted 2-4 sequences are represented the same way in the long term, and justify taking T to infinity. I assume there is a theorem which states something like this, e.g. "if we have a sequence of experiments one after another, grouped by outcomes, then the statistical length of the experiment in group X, converges to the truth average, under certain conditions". Once again, I like this argument, but I think I like your first solution more:) $\endgroup$ Commented Sep 14, 2017 at 19:10
  • 1
    $\begingroup$ True about not treating infinity rigorously here, @Artur Kirkoryan. I wanted to disagree but remembered the simple example of comparing the population counts of primes versus whole numbers. Finite comparisons produce increasingly large disparities in favor of wholes whereas an infinite comparison comes out perfectly equal. $\endgroup$
    – humn
    Commented Sep 14, 2017 at 19:23
  • 1
    $\begingroup$ "An infinite comparison comes out perfectly equal"? Only in terms of cardinality. In terms of natural density (which I'd argue is more natural (pun completely intended) in this case), the natural density of the primes is 0, which seems perfectly consistent with disparities increasing as $n\to\infty$. $\endgroup$
    – Deusovi
    Commented Sep 17, 2017 at 23:40
  • 1
    $\begingroup$ I might understand your comments even better now, @Artur K and $\raise-.2ex\unicode{x40}$Deusovi, and have added a Note about them. $\endgroup$
    – humn
    Commented Sep 19, 2017 at 20:06
15
$\begingroup$

Let $X_n$ be the event that the dice takes $n$ rolls to get the first 6, given all the rolls are even. Let $A_n$ be the event that it takes $n$ rolls to get the first 6, and let $B$ be the event that all rolls up to the first 6 are even.

$P(X_n)=P(A_n|B)=\dfrac{P(B|A_n)P(A_n)}{P(B)}$ (using Bayes' theorem)

Now:

$P(A_n)=\dfrac{1}{6}\cdot\left(\dfrac{5}{6}\right)^{n-1}$ (since the first $n-1$ rolls are not 6 and the last roll is)

$P(B)=\displaystyle\sum^\infty_{i=0}\dfrac{1}{6}\cdot\left(\dfrac{1}{3}\right)^{i}$ $=\dfrac{1}{6}\cdot\displaystyle\sum^\infty_{i=0}\left(\dfrac{1}{3}\right)^{i}$ $=\dfrac{1}{6}\cdot\dfrac{3}{2}=\dfrac{1}{4}$ (since at each stage there is a 1 in 3 chance that the roll is 2 or 4 and a 1 in 6 chance of getting a 6 at each roll)

$P(B|A_n)=\left(\dfrac{2}{5}\right)^{n-1}$ (since the last roll is even but for all the other rolls there are 2 even outcomes and 3 odd outcomes)

So $P(A_n|B)$ $=\dfrac{\dfrac{1}{6}\cdot\left(\dfrac{2}{5}\right)^{n-1}\cdot\left(\dfrac{5}{6}\right)^{n-1}}{\dfrac{1}{4}}$ $=\dfrac{2}{3}\cdot\dfrac{2^{n-1}\cdot5^{n-1}}{5^{n-1}\cdot6^{n-1}}$ $=\dfrac{2}{3}\cdot\left(\dfrac{1}{3}\right)^{n-1}$

Now, we wish to find

\begin{align} \sum^{\infty}_{i=1}i\cdot P(X_i) &=\sum^{\infty}_{i=1}i\cdot\dfrac{2}{3}\cdot\left(\dfrac{1}{3}\right)^{i-1} \\ &=2\cdot\sum^{\infty}_{i=1}i\left(\dfrac{1}{3}\right)^{i} \\ &=2\cdot\sum^{\infty}_{i=0}\left(\left(\dfrac{1}{3}\right)^{i}\cdot\sum^{\infty}_{j=1}\left(\dfrac{1}{3}\right)^{j}\right) \\ &=2\cdot\sum^{\infty}_{i=1}\left(\dfrac{1}{3}\right)^{i}\cdot\dfrac{3}{2} \\ &=3\cdot\sum^{\infty}_{i=1}\left(\dfrac{1}{3}\right)^{i} \\ &=\dfrac{3}{2} \end{align}

So it takes on average 1.5 rolls for the dice to get a 6, given that all the rolls are even.


Gamow wants me to keep my previous solution: if you want to see it, here it is. It is wrong because the definition of $B_n$ is faulty - for example, a sequence such as 26143 isn't counted in $B_5$ when it should be, and a sequence such as 24(16) is counted in $B_2$ when it shouldn't be, since we are given that all the rolls up to the first six are even, not that the rolls up to a certain point are even.

$\endgroup$
5
  • $\begingroup$ Could you explain how ∑[1;∞]i(1/3)^i = ∑[0;∞]((1/3)^i⋅∑[1;∞](1/3)^j) ? thx $\endgroup$
    – sousben
    Commented Sep 10, 2017 at 17:20
  • $\begingroup$ @Sousben We are adding 1/3+2/9+3/27+4/81…=1/3+1/9+1/27+1/81…+1/9+1/27+1/81+1/243…+1/27+1/81+1/243+1/729…+1/81+1/243+1/729+1/2187……=1x(1/3+1/9+1/27+1/81…)+1/3x(1/3+1/9+1/27+1/81…)+1/9x(1/3+1/9+1/27+1/81…)+1/27x(1/3+1/9+1/27+1/81…)… $\endgroup$
    – boboquack
    Commented Sep 10, 2017 at 21:17
  • $\begingroup$ Can you explain P(B) a bit more? I'd have expected it to depend on N since you are considering the chances of all N rolls being even. ie it would just be 1/3*(2/3)^n-1. $\endgroup$
    – Chris
    Commented Sep 11, 2017 at 14:45
  • 1
    $\begingroup$ @Chris the reason why it's not the chance of all n rolls being even is because that counts configurations such as 26, 264, 2642 etc as part of $P(B)$ multiple times where in reality they should only be counted once as 26. $\endgroup$
    – boboquack
    Commented Sep 11, 2017 at 21:16
  • $\begingroup$ Great answer! I wish you would have kept the first version, where the result was "3 rolls on average". (That's also the answer I came up with, and with which most other people come up. It takes some time to accept that this is wrong.) $\endgroup$
    – Gamow
    Commented Sep 12, 2017 at 6:24
9
$\begingroup$

I believe the answer is

$\frac{3}{2}$

This is computational calculation, so it is not statistical answer.

Here is the simple code

It is for the people who try to find it probabilistically.

Here is the probabilistic solution:

First of all, we know that the probability of getting 6 on the first roll is $\frac{1}{6}$, then getting 6 after an even roll is $\frac{2}{6}\frac{1}{6}$, and so on as the equation below:

$P_n=\left (\frac{1}{6} \right )\left (\frac{2}{6} \right )^{n-1}$

so if we calculate all possible solutions and sum them we will get the probability set among all other possibilities (such as getting odd after getting some even):

$\sum_{1}^{\infty }\left (\frac{1}{6} \right )\left (\frac{2}{6} \right )^{n-1}=0.25$

So if we multiply this by $4$ we will normalize the probability and find the actual expected value of getting $6$ given that all the rolls are even as below such as;

  1. Getting $6$ in the first roll expected value:

$E_1=4\left (\frac{1}{6} \right )\left (\frac{2}{6} \right )^{1-1}=\frac{2}{3}$

  1. Getting $6$ in the second roll (requires not getting $6$ in the first roll)

$E_2=\left [1-4\left (\frac{1}{6} \right )\left (\frac{2}{6} \right )^{1-1} \right ]+4\left (\frac{1}{6} \right )\left (\frac{2}{6} \right )^{2-1}=\frac{5}{9}$

In general, we can generalize the formula as below,

$E=\sum_{1}^{n}(1-A_{n-1})+B_n$

$A_{n}$ represents the sum of previous normalized probabilities and $B_{n}$ is the normalized probability of getting 6 at that roll.

firstly:

$A_n=\sum_{1}^{n}(4\times\frac{1}{6}\frac{2}{6}^{n-1})=1-3^{-n}$

secondly,

$B_n=4\times\frac{1}{6}\frac{2}{6}^{n-1})=2\times 3^{-n}$

so

$E_{2,\inf}=\sum_{2}^{\inf}(1-1-3^{1-n})+2\times 3^{-n}=\frac{5}{6} $

lastly, we are going to add the first result since the general sum will work after 1:

$ E=E_1+E_{2,\inf}=\frac{2}{3}+\frac{5}{6}=\frac{3}{2}$

So if we sum all possible outcome expected values, we will get the actual expected value of getting $6$ given that all the rolls are even:

$E =\sum_{1}^{\infty}E_n=\frac{3}{2}$

$\endgroup$
4
  • 1
    $\begingroup$ Whether your code is correct or not is hard to tell without comments, but it's easy to see that the output is 1 greater than the value you've given here. $\endgroup$ Commented Sep 10, 2017 at 8:22
  • $\begingroup$ If all the rolls are even, the probability of getting 6 tends to 1, so I don't follow your argument. $\endgroup$
    – boboquack
    Commented Sep 10, 2017 at 9:48
  • $\begingroup$ @boboquack it is not actually ignoring getting odd rolls. just i normalize the probability. i will explain it more after i arrive home $\endgroup$
    – Oray
    Commented Sep 10, 2017 at 9:52
  • $\begingroup$ In any case, the probability of getting 6 tends to 1, and after normalising should be 4, then...? $\endgroup$
    – boboquack
    Commented Sep 10, 2017 at 9:53
6
$\begingroup$

Somewhat related to Oray's solution.

The answer is

$\frac{3}{2}$

Why?

The average chance to get a 6 can be modelled using an infinite sum:
$$\sum_{n=0}^\infty \frac{1}{3} \times \frac{2}{3} ^ r$$
Where $\frac{1}{3}$ is the chance to get a 6, $\frac{2}{3}$ is the chance to not get a 6 and $r$ is the number of fails.
This is equivalent to a geometric series with $a_0 = \frac{1}{3}$ and $r=\frac{2}{3}$
$$\begin{align}S_\infty &= \frac{ar}{1-r}\\ &= \frac{\frac{1}{3} \times \frac{2}{3}}{1-\frac{2}{3}}\\ &= \frac{\frac{1}{3} \times \frac{2}{3}}{\frac{1}{3}}\\ &= \frac{2}{3}\end{align}$$
The average number of rolls needed is just $\frac{1}{S_\infty} = \frac{1}{\frac{2}{3}} = \frac{3}{2}$

$\endgroup$
4
  • $\begingroup$ Where do you get S∞=ar/(1−r) from? I read that lim N→∞ = a(1−r^(N+1))/(1−r) here: math.stackexchange.com/questions/29023/value-of-sum-limits-n-xn in which case the result would be 1 throw which is obviously wrong. $\endgroup$
    – sousben
    Commented Sep 10, 2017 at 13:10
  • $\begingroup$ @sousben wait never mind, this is not right - I need to divide by number of rolls too, I mean it's only logical the chance to get 6 is 100% in the long run $\endgroup$
    – somebody
    Commented Sep 10, 2017 at 13:27
  • $\begingroup$ Thanks it all makes sense now, I was making the same mistake as you and couldn't understand my result... $\endgroup$
    – sousben
    Commented Sep 10, 2017 at 13:30
  • $\begingroup$ This works out in this case, but I'm not sure that it works generally. If we get rid of the evenness condition (i.e., if we wanted the number of throws before seeing a 6 when throwing a dice normally and including all throws), I believe this approach would give 6/5? And it would give 2 if we discarded all throws that weren't, say, either 1 or 6. Seems like in the end it just inverts the probability to not get a 6 on one roll. $\endgroup$ Commented Sep 10, 2017 at 18:00
4
$\begingroup$

Going by definition of what is the expected number we get

$$ \sum_{n=1}^{\infty} n \cdot 1/3 \cdot (2/3)^{n-1} = 3 $$
where 1/3 part is the probability to get "6" after reaching the n'th roll and $ (2/3)^{n-1} $ - probability to reach that step.

Edit: well, it looks like the "reroll" [only the steps that produce odd number] and "reset" [the whole sequence] interpretations are not equal and the later is the intended meaning of the question. Under the later the probability to roll "6" on each step is in fact

not equal to 1/3 as in the first case.
Let $p_1$ be the conditional probability to roll "6" (equal for all steps because after roll of "2" or "4" all outcomes are still conditionally as probable as before the roll, just with the chain of rolls being longer by one). Conditional probability to roll "2" or "4" would be of course $1-p_1$.
Let "A" be the event that the first roll is "6", "B" be the event that the sequence ended on "6" and did not contain any odd numbers.
$$ \begin{align} p_1 & = P(A|B) \\ & = P(A \& B)/P(B) \\ & = (1/6)/(P(B)) \end{align}$$ $$ P(B)= \sum_{n=1}^{\infty} 1/6 \cdot (2/6)^{n-1}=1/4 $$ $$ p_1=(1/6)/(1/4)=2/3 $$ which is indeed rather counterintuitive.

The final answer in this approach:

$$ \sum_{n=1}^{\infty} n \cdot p_1 \cdot (1-p_1)^{n-1}=\sum_{n=1}^{\infty} n \cdot 2/3 \cdot (1/3)^{n-1}=3/2$$

$\endgroup$
3
$\begingroup$

I was struggling to get my head around this so I decided to test it programatically to see if I had misunderstood the question. Here's the code:

#!/usr/bin/perl

use strict;
use warnings;

my $die_size = 6;
my $number_of_runs = 100000;
my $total_count = 0;

sub count_rolls {
    my $number_of_rolls = 0;
    my $number_rolled = 0;
    while ($number_rolled != $die_size) {
        $number_of_rolls++;
        $number_rolled = 1 + int rand($die_size);
        if ($number_rolled % 2 == 1) {
            return count_rolls();
        }
    }
    return $number_of_rolls;
}

for (1..$number_of_runs) {
    my $roll_count = count_rolls();
    $total_count += $roll_count;
}

my $mean_count = $total_count / $number_of_runs;
print "$mean_count\n";

Try it online!

The result this gives is:

1.5

Hopefully this is helpful to anyone else who is a bit confused here.

$\endgroup$

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