2
$\begingroup$

I am trying to calculate the expected number of rolls of a 6-sided die before getting a 2 followed immediately by a 3. Here's my solution,

Let the $E[N] = x$,

$x = \frac{1}{36}\left[ 2 + (1+1+x-1) + 4(x+2) \right] + \frac{30}{36}[x+1]$.

The first term is from the cases (1st toss, 2nd toss): (2,3), (2,2), (2, 1/4/5/6), and the second term is from when 1st toss is not a 2. This equation leads to x = 41. But, this is the wrong answer. The correct answer is 42. I think the mistake is in the $(1+1+x-1)$ term, but I am not sure why. I found a solution on the internet which says that this term is simply $(x+2)$. This doesn't make sense because $x$ is the unconditional expectation, whereas once we see that the 2nd toss is also a 2, there is obviously less number of rolls required to get a pattern of $23$. Can someone please explain this?

$\endgroup$

2 Answers 2

5
$\begingroup$

Let $A$ be the expected number of still needed rolls continuing from a state that has not yet made any progress towards ending the chain, either as a result of having just rolled a number which is not a $2$ and having not just ended, or as a result of having just started the game. Let $B$ be the expected number of still needed rolls from the state that you have just recently rolled a $2$.

You have that $A=\frac{5}{6}(1+A)+\frac{1}{6}(1+B)$ and that $B=\frac{1}{6}(1)+\frac{1}{6}(1+B)+\frac{4}{6}(1+A)$

The first coming from the observation that while at the starting position, you either effectively remain at the starting position having rolled anything except a $2$ and then still need an additional $A$ expected rolls in addition to the roll(s) you've already made. For the second, you can either go from the second state to the winning end state, stay in the second state, or go back to the first.

Solving gives $A=36$ and $B=30$, so the answer to your question is $36$


Since there remains confusion, here is a quick and dirty javascript simulation, performing the experiment $100000$ times, resetting between each attempt. Running the simulation confirms the result to be near $36$

totalNumOfRolls = 0;
for(i=0;i<100000;i++){
prevRoll = 0;
curRoll = 0;
while (prevRoll != 2 || curRoll != 3){
prevRoll = curRoll;
curRoll = Math.floor(Math.random()*6)+1;
totalNumOfRolls++;
}
}
console.log(totalNumOfRolls/100000)
$\endgroup$
7
  • $\begingroup$ There are three interesting things to me about this question. (1) The answer of 36 is the naive "geometric" answer -- that is, the answer that you'd get if you threw (distinguishable) dice only in pairs and counted how many pairs you'd have to throw to see the desired result. My first instinct was that this meant 36 could not be right! And yet, I'm convinced by your argument and I confirmed it with my own independent simulation. (2) The OP believed in advance the other answer to be right. Why? (3) There are 3 answers by 20k+ rep users to this question, which is remarkable. $\endgroup$ Commented Apr 20, 2020 at 18:51
  • 1
    $\begingroup$ @AaronMontgomery The OP having put in effort of his own certainly helps to draw attention, but to clear up confusion caused by clear mistakes of OP or other users or even in this case exercise authors or teachers (the op mentioned the "correct answer" was supposedly 42) is another big driving force in terms of attracting answers. $\endgroup$
    – JMoravitz
    Commented Apr 20, 2020 at 18:56
  • $\begingroup$ @Jmoravitz Thanks for clearing this up for me! I knew something was wrong with my solution but wasn't able to find it. The textbook I am working on doesn't have solutions to exercises. So, I was referring to a website on the internet and that clearly has the wrong solution. $\endgroup$ Commented Apr 20, 2020 at 19:17
  • 1
    $\begingroup$ If you asked the same question about the string $33$, then the answer would be $42$ rolls. The fact that the string $23$ has no proper initial substrings which equal a final substring (of itself), means that the expected waiting time is just the reciprocal of the frequency $1/36$, i.e. $36$ rolls. When there are proper initial/final overlaps (e.g. the substring $3$ for the string $33$) the expected waiting time is longer (in general it's sum of reciprocals of frequencies of all the overlapping substrings, including the whole string). $\endgroup$
    – Ned
    Commented Apr 20, 2020 at 19:19
  • $\begingroup$ Very clear and nice (+1) :-) $\endgroup$ Commented Apr 20, 2020 at 19:28
3
$\begingroup$

Since there are already other answers that use linearity of expectation directly to generate a simple equation for the sought-after value, let’s bring the big guns to bear instead. The process can be modeled by a three-state absorbing Markov chain with transition matrix

$$P = \begin{bmatrix}\frac56&\frac16&0\\\frac46&\frac16&\frac16\\0&0&1\end{bmatrix} = \begin{bmatrix}Q&R\\\mathbf 0&1\end{bmatrix}.$$

From the start state, if we roll a two, we advance to the next state, otherwise stay in the start state. That’s the first row of $P$. From the “I just rolled a two” state, we can either roll a three and end, roll a two and stay in the “I just rolled a two” state, or roll anything else and go back to the start state. That’s the second row. The third row says that “I rolled a three immediately after a two” is an absorbing state: once we get there, we stay in that state forever.

Using the standard techniques described here, we compute the fundamental matrix $$N = (I-Q)^{-1}= \begin{bmatrix}30&6\\24&6\end{bmatrix}.$$ This matrix consists of the expected number of visits to each state before reaching the absorbing state. If we start the process in the first state, then, the expected number of steps until absorption is the sum of the entries in the first row of $N$, namely, $36$.

$\endgroup$

You must log in to answer this question.

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