If I repeatedly roll a fair, $X$-sided die, on average how many rolls should I expect to make before I happen to roll the same value $N$ times in a row?
I've found questions on here with answers when $X=2$, or where $N=2$, or where you're looking for a specific result $N$ times in a row; I'm interested in the situation where I don't care what the specific value is, I just want it to be $N$ times in a row. The closest I can find is Suppose we roll a fair $6$ sided die repeatedly. Find the expected number of rolls required to see $3$ of the same number in succession., but I can't quite figure out how to generalize it beyond $N=3$.
Answer
Let $E_k$ denote the expected number of rolls that are still needed if $k$ rolls have passed with equal result. We write recurrence relations for $E_k,0\leq k\leq N-1$ and calculate the wanted expectation $E=E_0$ from them.
We obtain
\begin{align*}
E_0&=E_1+1\tag{1}\\
E_1&=\frac{1}{X}(E_2+1)+\frac{X-1}{X}(E_1+1)\\
E_2&=\frac{1}{X}(E_3+1)+\frac{X-1}{X}(E_1+1)\\
E_3&=\frac{1}{X}(E_4+1)+\frac{X-1}{X}(E_1+1)\tag{2}\\
&\ \ \ \vdots\\
E_{N-3}&=\frac{1}{X}(E_{N-2}+1)+\frac{X-1}{X}(E_1+1)\\
E_{N-2}&=\frac{1}{X}(E_{N-1}+1)+\frac{X-1}{X}(E_1+1)\\
E_{N-1}&=\frac{1}{X}+\frac{X-1}{X}(E_1+1)\tag{3}\\
\end{align*}
Comment:
In (1) we note that any roll of the $X$-sided die will do.
In (2) we are in the situation that a run of length $3$ is given. With probability $\frac{1}{X}$ we get a run of length $4$ and with probability $\frac{X}{X-1}$ we get a different result and start with a run of length $1$.
In (3) we get a run of length $n$ with probability $\frac{1}{X}$ and can stop or we are back at the beginning and start again with a run of length $1$.
This system can be easily solved. We iteratively obtain be respecting all equations from above besides the last one (tagged with (3)).
\begin{align*}
E_1&=E_0-1\\
E_2&=E_0-(1+X)\\
E_3&=E_0-(1+X+X^2)\\
E_4&=E_0-(1+X+X^2+X^3)\\
&\ \ \ \vdots\\
E_{N-1}&=E_0-(1+X+X^2+\cdots+X^{N-2})\\
&=E_0-\frac{X^{N-1}-1}{X-1}\tag{4}\\
\end{align*}
From equation (4) and (3) we finally conclude
\begin{align*}
E_{N-1}&=E_0-\frac{X^{N-1}-1}{X-1}\\
(1-X)E_0+XE_{N-1}&=1
\end{align*}
from which
\begin{align*}
\color{blue}{E=E_0=\frac{X^N-1}{X-1}}
\end{align*}
follows.
Note: This approach is a generalisation of @lulu's answer of this MSE question. In fact we get as small plausibility check with $N=3$ and $X=6$ the result
\begin{align*}
E=\frac{6^3-1}{6-1}=\frac{215}{5}=43.
\end{align*}
in accordance with @lulu's result.
[Add-on] The strongly related problem: Rolling a fair $X$-sided die until we get a run of length $N$ of a specific value can be solved by the system above with the first equation (1) replaced with
\begin{align*}
E_0&=\frac{1}{X}(E_1+1)+\frac{X-1}{X}(E_0+1)
\end{align*}
which gives the result
\begin{align*}
\color{blue}{E=E_0=\frac{X\left(X^N-1\right)}{X-1}}
\end{align*}
This is also plausible compared with the result above, since the probability to roll a specific value is $\frac{1}{X}$.
No comments:
Post a Comment