6
$\begingroup$

Suppose we roll a fair six sided die repeatedly.

Find the expected number of rolls required to see $3$ of the same number in succession

From the link below, I learned that $258$ rolls are expected to see 3 sixes appear in succession. So I'm thinking that for a same (any) number, the rolls expected would be $258/6 = 43$. But I'm unsure how to show this and whether it really is correct.

How many times to roll a die before getting two consecutive sixes?

$\endgroup$
9
$\begingroup$

For $n\in \{0,1,2\}$ Let $E[n]$ denote the answer given that you are starting from a streak of $n$ consecutive rolls. The answer you want is $E=E[0]$, though you are never in state $0$ except at the start.

We note $$E[2]=\frac 16\times 1+\frac 56\times \left(E[1]+1\right)$$ $$E[1]=\frac 16\times \left(E[2]+1\right)+\frac 56\times \left(E[1]+1\right)$$

$$E=E[0]=E[1]+1$$

this system is easily solved and, barring error (always possible), yields $$\boxed {E=43}$$

$\endgroup$
  • 4
    $\begingroup$ This is very elegant (+1) - great answer!! $\endgroup$ – Satish Ramanathan Aug 31 '17 at 16:38
  • $\begingroup$ One issue that isn't really an issue: everything needs to be finite for this to work (cf optional stopping theorem) $\endgroup$ – cats Aug 31 '17 at 18:32
  • $\begingroup$ This is the (arch classical) approach used in the post mentioned in Byron's answer. $\endgroup$ – Did Aug 31 '17 at 18:40
6
$\begingroup$

From Did's answer here, the probability generating function $u_0(s)=\mathbb{E}(s^T)$ for the number of trials $T$ needed to get three consecutive values the same is
$$u_0(s)={s^3\over 36-30s-5s^2}.$$ Differentiating this and setting $s=1$ in the derivative shows that $\mathbb{E}(T)=43.$

$\endgroup$
4
$\begingroup$

We can treat this as a three-state absorbing markov chain: a length3 run has been seen, otherwise the current run is length2, current run is length 1. Transition matrix: $\begin{bmatrix}1&\frac{1}{6}&0\\0&0&\frac{1}{6}\\0&\frac{5}{6}&\frac{5}{6}\end{bmatrix}$

This is in standard form $\left[\begin{array}{c|c}I&S\\\hline0&R\end{array}\right]$

We turn our attention to the fundamental matrix $(I-R)^{-1} = \begin{bmatrix}1&-\frac{1}{6}\\-\frac{5}{6}&\frac{1}{6}\end{bmatrix}^{-1}=\begin{bmatrix}6&6\\30&36\end{bmatrix}$

After the first roll, we enter the markov chain in the third state. Adding the entries of the fundamental matrix corresponding to that column tells us the expected time until we reach an absorbing state, i.e. until we have a chain of three consecutive rolls of the same number.

Thus the expected number of rolls needed is $1+36+6=43$

$\endgroup$
4
$\begingroup$

Let $\mu$ denote the expectation of the expected number of rolls that are still needed if $2$ rolls have passed with distinct result.

Let $\nu$ denote the expectation of the expected number of rolls that are still needed if $2$ rolls have passed with equal result.

Then the expectation is: $$2+\frac56\mu+\frac16\nu$$

Here $\frac56$ is the probability that the first two numbers are distinct and $\frac16$ is the probability that they are equal.

Secondly we have the relations:

$$\mu=\frac56(1+\mu)+\frac16(1+\nu)=1+\frac56\mu+\frac16\nu\tag1$$ and: $$\nu=\frac161+\frac56(1+\mu)=1+\frac56\mu\tag2$$

The relations $(1)$ and $(2)$ lead easily to: $\mu=42$ and $\nu=36$.

Then $$2+\frac56\mu+\frac16\nu=43$$ is the final answer.


addendum:

(in the answers uptil now it was not used that you allready learned something).

Let $Y$ denote the number of rolls required to see three dice of the same number in succession and let $X$ denote the number of rolls required to see three dice with number $6$ in succession.

Then: $$Y\text{ and }\frac16X+\frac56(X+Y)=X+\frac56Y\text{ must have equal distribution.}\tag3$$

Here $\frac16$ is the probability of the event that the first time that three dice give the same number in succession they show number $6$ and $\frac56$ is the probability that do not show a number $6$.

$(3)$ rests on the observation that - if for the first time three equal numbers show up in succession - we are ready if $6$ happens to be that number and must actually start over again (with $X$ throws in our pocket) if not.

So we find $\mathbb EY=\mathbb EX+\frac56\mathbb EY$ or equivalently:$$\mathbb EX=\frac16\mathbb EY$$

You allready learned that $\mathbb EY=258$ and making use of that knowledge you find $$\mathbb EX=258/6=43$$ This confirms your thinking.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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