probability - How many tries on average before I see the same value $N$ times in a row?

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}$.