1
$\begingroup$

In Expected number of rolls until a number appears $k$ consecutive times, the formula was given to be $E[k] = \frac{6^k - 1}{5}$. You can prove this formula using induction like in the accepted answer.

Is there a method to actually derive this expression from scratch (without using induction)?

$\endgroup$
3
  • 3
    $\begingroup$ The question you linked to is actually about the expected number of rolls until a number appears $k$ consecutive times, although the important modifier "consecutive" was misleadingly left out of the title. The answer $\frac{6^k-1}5$ is for $k$ consecutive appearances. If that's the problem you're interested in, you should clarify your question by adding the word "consecutive" in the right places. On the other hand, if you're interested in the waiting time until some number has appeared $k$ times (not necessarily consecutively), that's another question. $\endgroup$
    – bof
    Commented Apr 17, 2021 at 6:19
  • $\begingroup$ I hope your question was for consecutive appearances. That's what I worked out, seeing the link. Pl clarify immediately what you intended, and make necessary amendments. $\endgroup$ Commented Apr 17, 2021 at 11:55
  • $\begingroup$ @bof Ahhhh I missed that part. I was unfortunately interested in the non-consecutive case. I'll change this question to the consecutive case anyways since someone already answered. $\endgroup$
    – roulette01
    Commented Apr 17, 2021 at 13:01

2 Answers 2

5
$\begingroup$

Consider the case of getting some number $n-1$ consecutively. For eg. $5 5 5 ... 5 \_ $

The last $n$th roll, can either be a $5$ or it may not be $5$. In the first case, a number has appeared n consecutive times and you stop. While, in the second, it becomes the start of a new sequence.

Now, denote $E_n$ as the expected number of die rolls to get some number (any number) $n$ times consecutively

Hence, $$E_n = \frac16\cdot(E_{n-1} + 1) + \frac56 \cdot (E_{n-1} + E_n)$$

$$\implies E_n = 6E_{n-1} + 1 $$

$$Let \quad E_n = a\cdot6^n+b$$ Using the trivial base cases: $E_0 = 0, E_1 = 1$, we get the solution

$$\implies\boxed{ E_n = \frac{6^n - 1}5}$$


Interesting Observation: $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ Let the expected number of die rolls to get $n$ consecutive sixes (or any particular number) be $E^{'}_n \quad$ $$\implies E^{'}_n = 6\cdot E_n$$

$\underline{\text{Proof for the above observation:}}$

First, wait until you see $n$ consecutive of anything. This is expected to take $E_n$ trials. Now two possibilities arise. Either you rolled $n$ consecutive sixes (probability $\frac 16$) or you didn't and hence start over (probability $\frac 56$). Formulating the above algebraically,

$$E^{'}_n=\frac 16\cdot E_n+\frac 56\cdot (E^{'}_n+E_n)\implies 6E^{'}_n=E_n+5E^{'}_n+5E_n\implies E^{'}_n=6E_n$$

$\endgroup$
3
  • $\begingroup$ Regarding the last part, while the answer is correct, I either haven't understood your reasoning properly or don't find it compelling. There is something special about the choices of stopping events beyond them having the same expected time (namely, that none of the strings end with a prefix any of the others) that allows us to "just divide by $6$" to get the minimum. For instance the expected time for coinflips to get HHT and THH are both 8, but the expected time to get one or the other is $6.5,$ not $4.$ $\endgroup$ Commented May 6 at 19:49
  • $\begingroup$ @spaceisdarkgreen I have provided the proof for the claim. I hope this reasoning is correct and compelling enough :) $\endgroup$ Commented May 6 at 20:33
  • 1
    $\begingroup$ Yes, that works for me... the key point being "and hence start over" is true in this case but doesn't hold in the HHT /THH example. $\endgroup$ Commented May 6 at 20:41
1
$\begingroup$

$\underline{\text{Rolls needed for (say) 6 to appear k consecutive times}}$

Denote by $e_1$ the expected value of getting $6$ on a die roll, then $e_1 =\frac{1}{p} = 6\;$ by the geometric distribution.

From there, we have $\frac16$ chance of getting double $6$, else back to scratch with a wasted throw, so $\;e_2 = e_1 +\frac16\cdot1 + \frac56(e_2 +1) \to\; e_2 = 6(e_1+1)$

We compute for $(k-1)$ more successive sixes using recursion

$\displaylines {e_2 = 6(e_1+1)=6+6^2\\e_3= 6(e_2+1) = 6 + 6^2+6^3\\e_4 = 6(e_3+1) = 6 + 6^2 +6^3+6^4\\ ... ...\\e_k = 6(e_{k-1}+1) = 6+6^2+ ... + 6^{k} = \frac{6(6^{k}-1)}{6-1},k>1}$

This formula is for a particular number, eg $6$

$\endgroup$
4
  • $\begingroup$ Wait is $e_k$ the expected number of tosses to get a fixed number k times in a row, or the expected number of tosses it takes to any number $k$ times in a row? $\endgroup$
    – roulette01
    Commented Apr 17, 2021 at 15:49
  • $\begingroup$ In eithe rscenario, I think there's an issue with this formula because for $k=1$, your solution is undefined. $\endgroup$
    – roulette01
    Commented Apr 17, 2021 at 16:34
  • $\begingroup$ There are a lot of issues with this answer. @trueblueanil Please have a look at it again. One noticeable inconsistency is the final equation: $e_k = 1 + e_{k-1}$ $\endgroup$ Commented May 4 at 18:59
  • $\begingroup$ @DevanshAgarwal: Yes, thanks, I have amended, also taking into account roulette01 observations $\endgroup$ Commented May 9 at 18:40

You must log in to answer this question.

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