29
$\begingroup$

So earlier today I came across Elchanan Mossel's Dice Paradox, and I am having some trouble understanding the solution. The question is as follows:

You throw a fair six-sided die until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers?

Quoted from Jimmy Jin in "Elchanan Mossel’s dice problem"

In the paper it goes on to state why a common wrong answer is $3$. Then afterwards explains that this problem has the same answer to,

"What is the expected number of times you can roll only $2$’s or $4$’s until you roll any other number?"

I don't understand why this is the case. If the original problem is asking for specifically a $6$, shouldn't that limit many of the possible sequences?

I also attempted to solve the problem using another method, but got an answer different from both $3$ and the correct answer of $1.5$.

I saw that possible sequences could have been something like:

$$\{6\}$$ $$\{2,6\}, \{4,6\}$$ $$\{2,2,6\}, \{2,4,6\}, \{4,2,6\}, \{4,4,6\}$$ $$\vdots$$

To which I set up the following summation and solved using Wolfram Alpha:

$$\text{Expected Value} =\sum_{n=1}^\infty n\left( {\frac{1}{6}} \right)^n 2^{n-1} = 0.375$$ Obviously this is different and probably incorrect, but I can't figure out where the error in the thought process is.

Any help on understanding this would be greatly appreciated.

A blog post discussing the problem can be found here.

$\endgroup$
4
  • $\begingroup$ really really late reply, but can someone explain this? repl.it/repls/UsedScalyTurtledove $\endgroup$
    – Quintec
    Dec 1, 2017 at 2:40
  • $\begingroup$ @thecoder16 Your code should not throw away odd rolls. Instead, if an odd roll is seen, you should declare the sequence in progress to be unsuccessful, and omit it from your running total when a 6 is eventually rolled. See the edit to my answer. $\endgroup$
    – grand_chat
    Mar 3, 2018 at 2:33
  • $\begingroup$ @grand_chat yeah, thanks, I solved this problem a while ago :) $\endgroup$
    – Quintec
    Mar 3, 2018 at 18:36
  • $\begingroup$ hey there--this is Jimmy Jin. I wanted to thank everyone for pointing out the confusing parts! I've since updated my writeup. My original goal in using the "subtraction" idea was to explain why most people get the wrong answer by oversimplifying to the space of a single die roll. But as @MichaelHardy pointed out below, this is actually the right principle except on the enriched space of a sequence of die rolls. $\endgroup$
    – gogurt
    May 29, 2018 at 23:36

8 Answers 8

17
$\begingroup$

When you roll a die until $6$ appears, you can represent the sample space as all possible finite sequences from the set $\{1, 2, 3, 4, 5, 6\}$ ending in $6$, with probability of any sequence of length $k$ being $(1/6)^k$. The original question is asking for

$(1)$ the expected length of a sequence conditional on all throws being even.

You've correctly enumerated all sequences from $\{2,4,6\}$ that end in $6$, and calculated the sum $$\sum_{n=1}^\infty n\left( {\frac{1}{6}} \right)^n 2^{n-1} = 0.375$$ properly, but you forgot to divide this by the probability of the event you are conditioning on, which is $$ \sum_{n=1}^\infty\left(\frac16\right)^n2^{n-1}=1/4. $$ So your approach does yield the correct answer, namely $4\times 0.375=1.5$.

The act of conditioning on all throws being even is tantamount to restricting the sample space to all possible finite sequences from the set $\{2, 4, 6\}$ that end in $6$, and rescaling the probability function (by a factor $4$) so that this new sample space has total mass $1$.

As for the Jin paper, he claims that the original question $(1)$ is equivalent to

$(2)$ the expected number of times you can roll only $2$'s or $4$'s until you roll a $6$.

I disagree with $(2)$; it is incorrect to compute an unconditional expectation, as he just explained in his previous paragraph. He still needs an expectation conditional on some event, and I would argue the original question $(1)$ is equivalent to computing

$(2')$ the expected number of times you can roll only $2$'s or $4$'s until you roll any other number, given that the other number is $6$.

The reason is that conditioning on the event "the other number is $6$" results in the same restricted sample space as before. In fact his subsequent argument that it suffices to compute the unconditional expectation

$(3)$ the expected number of times you can roll only $2$'s or $4$'s until you roll any other number.

(i.e., that $(2') = (3)$, which is what he actually proves) is relevant only if we intend $(2')$ instead of $(2)$.


EDIT: Here's a Python simulation of the experiment, based on code provided by @thecoder:

import random

times = 0 #number of times a successful (all-even) sequence was rolled
rolls = 0 #total of all number of rolls it took to get a 6, on successful sequences
curr = 0
alleven = True

for x in range(0, 100000):

  num = random.randint(1,6)
  if num % 2 != 0:
    alleven = False
  else:
    if num == 6:
      if alleven:
        times += 1
        rolls += curr + 1
      curr = 0
      alleven = True
    else:
      curr += 1

print(rolls * 1.0 / times)
#1.51506456241
$\endgroup$
0
10
$\begingroup$

Part of Jimmy Jin's explanation is right, but his account of "the subtraction fallacy" is unfortunate. Conditioning does consist of discarding part of the sample space.

Suppose one throws a die repeatedly and gets this sequence: $$ 2, 5, 3, 2, 1, 4, 3, 6 $$ Next suppose one excludes the odd numbers: $$ \require{cancel} 2, \xcancel5, \xcancel3, 2, \xcancel1, 4, \xcancel3, 6 $$ One then has this sequence: $$ 2,2,4,6 $$ The average length of this sequence will be $3.$

But now suppose you get this sequence: $$ 2, 5, 3, 2, 1, 4, 3, 6 $$ Then try again and get this: $$ 3,2,5,2,1,6 $$ Then try again and get this: $$ 2,4,4,2,6 $$ Then discard the first two since one got odd numbers before getting a $6:$ $$ \xcancel{2, 5, 3, 2, 1, 4, 3, 6} $$ $$ \xcancel{3,2,5,2,1,6} $$ But keep that last one: $$ 2,4,4,2,6 $$ Among the ones you keep the average length is $3/2,$ not $3.$

You are in fact excluding that part of the sample space in which at least one odd number appears before the first $6,$ and in what's left of the sample space the average position of the first $6$ is $3/2.$ Thus Jimmy Jin is wrong about the "subtraction fallacy."

However, he is right that the average position of the first $6,$ given that only even numbers appear, is $3/2.$

In sequences pared down by excluding all the odd numbers that appear, the average position of the first $6$ is $3.$

$\endgroup$
2
  • 2
    $\begingroup$ Just wanted to thank you Michael for pointing this out (this is Jimmy). My intention was to highlight the incorrect deletion of the sample space treating the problem through the lens of a single die roll. I'm in complete agreement that the correct perspective is the sequential one. I've since updated the writeup to clear this up! $\endgroup$
    – gogurt
    May 30, 2018 at 0:12
  • $\begingroup$ How do you conclude that the average length in the restricted sample space is 3/2? $\endgroup$
    – Roland
    May 28, 2019 at 8:44
1
$\begingroup$

I think I found another reasonable explanation (would appreciate feedback on this) that clicks in better in my brain:

I also tried adding up the lengths with the probabilities, and I got this:

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

Here, $n$ is the length of the sequence itself, $1/6$ would be the probability of the last throw being a 6, and $(2/6)^{n-1}$ is the probability that every previous throw is a $2$ or a $4$. However, what I was missing is that you need not count anything where previous throws are $1$, $3$, or $5$. So, this becomes:

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

where $(2/3)^{n-1}$ is the probability that previous throws are $2$ or $4$, but not $6$. I don't know if my reasoning is correct, but I can follow this a bit better than other explanations.

$\endgroup$
1
$\begingroup$

Here is a correct and intuitive way to understand it. Suppose you roll a die about a million times and record the rolls as one long string of numbers. Every $6$ in there is the end of a legal sequence of some length $L$. The probability that the number before the $6$ is $1,3,5$ or $6$ is $\frac46$. In this case the $6$ is the end of a legal sequence of length $1$, i.e., only the $6$ itself. So the probability that $L=1$ is $\frac23$.

That leaves probability $\frac13$ for a longer sequence with $L$ being $2$ or more when there is at least one $2$ or $4$ preceeding the $6$. The expected length is thus $L = \frac23 \cdot 1 + \frac13 \cdot (2 + TF)$ where $TF$ is the expected length of the run of further $2$’s and $4$’s preceeding the $2$ or $4$ we already found, including run length $0$ if there are no further $2$’s and $4$’s.

Next we determine TF, the expected length of a run of $2$’s and $4$’s only. The probability that the run length is $0$ is $\frac23$. The probability that the run length $1$ is $\frac13 \cdot \frac23$ since we first need a $2$ or $4$, and then something that is not a $2$ or $4$. That leaves probability $\frac13 \cdot \frac13$ for a run length of $2$ or more $2$’s and $4$’s. For the “or more” part we can use $TF$ itself again. This leads to $TF = (\frac23 \cdot 0 + \frac13 \cdot \frac23 \cdot 1 + \frac13 \cdot \frac13(2 + TF)$. Rewriting we get $\frac89TF = \frac29 + \frac29 = \frac49$ so that $TF = \frac12$. Substituting $TF$ in $L$ we get expected sequence length $L = \frac23 + \frac13 \cdot (2 + \frac12) = \frac23 + \frac56 = 1.5$.

$\endgroup$
0
$\begingroup$

Possible Confusion

To see the problem with simply ignoring the odd rolls, let's simplify things and consider a three sided die and the probability of rolling a $\{3\}$ or a $\{2,3\}$.

Only roll $\boldsymbol{2}$ or $\boldsymbol{3}$

If we are not ignoring $1$'s, the probability of rolling a $\{3\}$ is $\frac13$ and the probability of rolling a $\{2,3\}$ is $\frac19$. That is, if $E$ is the event that we have only rolled a $\{3\}$ or a $\{2,3\}$, $$ \begin{align} \operatorname{Pr}(\{3\}|E)&=\frac{\frac13}{\frac13+\frac19}=\frac34\tag{1a}\\ \operatorname{Pr}(\{2,3\}|E)&=\frac{\frac19}{\frac13+\frac19}=\frac14\tag{1b} \end{align} $$

Ignore rolls of $\boldsymbol{1}$

However, if we are ignoring $1$'s, rolling any other number may also involve rolling and ignoring any number of $1$'s. Denote these by $\langle1\rangle$. Then, $$ \operatorname{Pr}(\{\langle1\rangle,2\})=\operatorname{Pr}(\{\langle1\rangle,3\})=\left[\sum_{n=0}^\infty\left(\frac13\right)^n\right]\frac13=\frac12\tag2 $$ $(2)$ is exactly what we get when rolling $2$'s and $3$'s on a two sided die. The probability of rolling a $\{\langle1\rangle,3\}$ is $\frac12$ and the probability of rolling a $\{\langle1\rangle,2,\langle1\rangle,3\}$ is $\frac14$. That is, if $F$ is the event that we have only rolled $\{\langle1\rangle,3\}$ or $\{\langle1\rangle,2,\langle1\rangle,3\}$, $$ \begin{align} \operatorname{Pr}(\langle1\rangle,\{3\}|F)&=\frac{\frac12}{\frac12+\frac14}=\frac23\tag{3a}\\ \operatorname{Pr}(\{\langle1\rangle,2,\langle1\rangle,3\}|F)&=\frac{\frac14}{\frac12+\frac14}=\frac13\tag{3b} \end{align} $$ Therefore, saying that we roll only $2$ and $3$ is not the same as ignoring rolls of $1$.


Mean and Variance

Back to the six-sided die, rolling $2$'s and $4$'s before a $6$.

The probability of a successful run of length $k$ is $$ \frac16\frac1{3^{k-1}}\tag4 $$ That is, $k-1$ $2$'s or $4$'s, probability $\left(\frac26\right)^{k-1}$, followed by a $6$, probability $\frac16$.

Thus, the mean of $k$, the length of a run, is $$ \begin{align} \frac{\sum\limits_{k=1}^\infty\frac16\frac{k}{3^{k-1}}}{\sum\limits_{k=1}^\infty\frac16\frac1{3^{k-1}}} &=\frac{\frac16\frac1{\left(1-\frac13\right)^2}}{\frac16\frac1{1-\frac13}}\tag{5a}\\ &=\frac{\frac38}{\frac14}\tag{5b}\\[12pt] &=\frac32\tag{5c} \end{align} $$ Furthermore, the mean of $k(k-1)$ is $$ \begin{align} \frac{\sum\limits_{k=1}^\infty\frac16\frac13\frac{k(k-1)}{3^{k-2}}}{\sum\limits_{k=1}^\infty\frac16\frac1{3^{k-1}}} &=\frac{\frac16\frac13\frac2{\left(1-\frac13\right)^3}}{\frac16\frac1{1-\frac13}}\tag{6a}\\ &=\frac{\frac38}{\frac14}\tag{6b}\\[12pt] &=\frac32\tag{6c} \end{align} $$ Therefore, the mean of $k^2$ is the sum of the mean of $k$ and the mean of $k(k-1)$: $$ \begin{align} \frac{\sum\limits_{k=1}^\infty\frac16\frac{k^2}{3^{k-1}}}{\sum\limits_{k=1}^\infty\frac16\frac1{3^{k-1}}} &=\frac32+\frac32\tag{7a}\\ &=3\tag{7b} \end{align} $$ The variance is the mean of the squares minus the square of the mean: $$ 3-\left(\frac32\right)^2=\frac34\tag8 $$

$\endgroup$
0
$\begingroup$

Suppose we roll the die $N$ consecutive times: \begin{align*} & N/6 &&\text{Average number of 6 throws.}\\ & 3N/6 &&\text{Average number of even throws.}\\ & \frac{3N/6}{N/6}=3 &&\text{Average number of even throws to get a 6.} \end{align*} Another way: Now let $N$ be the number of throws until you get a 6: $$P(N=n\mid all\,\,throws\,\,even)=\frac{2^{n-1}}{3^n};\quad E[N\mid all\,\,throws\,\,even]=\sum\frac{2^{n-1}}{3^n}n=3$$

$\endgroup$
2
  • $\begingroup$ “Given that all rolls are even” is not the same as “only even numbers can be rolled”. The former says that odd numbers can be rolled, but it happens that only even numbers were rolled. The latter says odd numbers cannot be rolled (essentially, leaving a three-sided die). $\endgroup$
    – robjohn
    Apr 1 at 17:18
  • $\begingroup$ @robjohn you are right. The correct answer is 3/2. $\endgroup$
    – Speltzu
    Apr 2 at 2:50
0
$\begingroup$

It is not entirely clear what your question is.

In general, if you want to compute the expectation of a random variable with respect to a probability (measure) $P$, say $L$ (length), you compute $E L = \sum_n n P[L=n]$.

The formula at the end of your question computes $n$ times the probability of rolling a sequence of the form $\{2,4\}^{n-1} 6$, but this probability is not the same as $P[L=n] = ({5 \over 6})^{n-1} {1 \over 6}$, so you are not computing the expectation of $L$.

If we let $E$ be the event that all rolls are even, then we see that $E$ is any sequence of the form $\{2,4\}^{n-1} 6$ and $P E = {1\over 4}>0$ and so we can talk about the conditional expectation with respect to $E$. Now we have $E(L \mid E) = \sum_n n P(L=n \mid E) = \sum_n n {P([L=n] \cap E) \over PE} = { { 3 \over 8} \over {1 \over 4} } = {3 \over 2}$.

The issue is that with a 3 sided die the probability of rolling a $6$ is ${1 \over 3}$ but with a 6 sided die the probability is ${ 1 \over 6}$.

$\endgroup$
-2
$\begingroup$

The correct answer is 3. Most people seem to forget to apply the condition as the condition states: "all rolls gave even numbers", ie. "each and every roll gave even number". Apply this to each roll, and you very quickly and easily get the answer 3.

People seem to have ideas about how to construct the experiment: "discard sequences with odd numbers at the end", or "if you roll an odd number then stop and start again" or "if you roll an odd number then discard this roll and roll again" or whatever other method. However, note that the original question never says so, and never even considers these situations. Instead, it is giving us a condition, and this condition is a FACT, a GIVEN. Even numbers already occurred. So we cannot just introduce odd numbers in the experiment, just because our general encyclopedic knowledge is that a die also has odd numbers.

Note also that a fair die has equal probabilities only when unconditioned. After applying the condition, obviously the probability of odd numbers becomes zero. The fact that the die is fair tells us that the probability of even numbers is still equal, and it is now 1/3. So for a fair die: P(1|even)=P(3|even)=P(5|even)=0 and P(2|even)=P(4|even)=P(6|even)=1/3.

Unconditioned experiment: $$ E = \sum_{n=0}^\infty nP(Length=n) = \sum_{n=0}^\infty nP(1st\ roll\ not\ 6\ \cap...\cap\ nth\ roll\ is\ 6) = \sum_{n=0}^\infty nP(1st\ roll\ not\ 6)*...*P(nth\ roll\ is\ 6) = \sum_{n=0}^\infty n\left( \frac{5}{6}\right)^{n-1}\frac16 = 6 $$

Conditioned experiment: $$ E = \sum_{n=0}^\infty nP(Length=n\ |\ all\ rolls\ even) = \sum_{n=0}^\infty n\frac{P(Length=n\ \cap\ n\ rolls\ even)}{P(n\ rolls\ even)}= \sum_{n=0}^\infty n\frac{P(1st\ roll\ not\ 6\ \cap...\cap\ nth\ roll\ is\ 6\ \cap\ 1st\ roll\ even\ \cap...\cap\ nth\ roll\ even)}{P(n\ rolls\ even)}= \sum_{n=0}^\infty n\frac{P(1st\ roll\ not\ 6\ \cap\ 1st\ roll\ even)*...*P(nth\ roll\ is\ 6\ \cap\ nth\ roll\ even)}{P(n\ rolls\ even)} =\sum_{n=0}^\infty n\frac{P(1st\ roll\ 2\ or\ 4)*...*P(nth\ roll\ is\ 6)}{P(n\ rolls\ even)}= \sum_{n=0}^\infty n\frac{\left( \frac{2}{6}\right)^{n-1}\frac16}{\left( \frac{1}{2}\right)^{n}}= \sum_{n=0}^\infty n\left( \frac{2}{3}\right)^{n-1}\frac13=3 $$

$\endgroup$
1
  • $\begingroup$ Please see the first section of my answer "Possible Confusion". The answer really is $\frac32$. $\endgroup$
    – robjohn
    Mar 30 at 20:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .