Expectation value of trials needed to get $k$ consecutive outcomes Suppose that independent trials, each of which is equally likely to have any of $m$ possible outcome, are performed until the same outcome occurs $k$ consecutive times. If $N$ denotes the number of trials, show that
$$E[N] = \frac{m^k-1}{m-1}$$
This is a homework question. I was trying to reverse engineer this into a GP but without success.
I also tried an induction approach to $k$. For getting one outcome, the number of trials needed is always $1$, so $k=1$ is a trivial case. Now assume that the expectation value of trials needed for $k$ consecutive outcomes is $E[N]$, then how do I find the update to $E[N]$ for $k+1$. 
I am very confused on the approach. Looks like a one-liner would do. Please help.
 A: I figured it out.
Say you've got $k$ identical outcomes for the first time after $N_k$ trials. Now, if you want the $(k+1)^{th}$ outcome in the next turn, the probability is $\frac{1}{m}$ and the number of extra turns needed is $1$ so the expectation of $N_{k+1}$ conditionally on this is $N_k + \frac{1}{m}$. 
Now what if you don't get the same outcome on this next try? You get a different outcome hence you start all over again and you need an extra number steps with mean $E[N_{k+1}]$.
To sum up, $E[N_{k+1} \mid N_k] = N_k + \frac{1}{m} +E[N_{k+1}](1-\frac{1}{m})$.
This recursion gives $E[N_{k+1}] = E[N_k] + \frac{1}{m} +E[N_{k+1}](1-\frac{1}{m})$, hence $E[N_{k+1}] = mE[N_k] + 1$, which, together with $E[N_1]=1$, yields the desired identity.
A: This is a classic problem of Expectation Trick which states that $\mathbb{E}[\mathbb{E}[X|Y]] = \mathbb{E}[X]$. Generally, the main catch in these problems is finding the conditioning variable ($Y$). 
For the problem at hand, we can define $N_{k} = \text{Number of trials to get } k \text{ consecutive identical outcomes}$. We will find $\mathbb{E}[N_{k}|N_{k-1}]$ and then use the trick. 
By first principles, we have - 
$$\begin{equation}
\mathbb{E}[N_k|N_{k-1}=n_{k-1}] = \sum_{n_k}n_kP\left(n_k|N_{k-1}=n_{k-1}\right)
\end{equation}\label{base_eq}$$
Now, there are 2 cases:

*

*Case 1: If the output of $(n_{k-1}+1)^{th}$ trial is the same as that of the last $k-1$ trials, then we will have $k$ consecutive identical outcomes, and we are done! The number of trials required in this case will be $(n_{k-1}+1)$ and the probability of this happening is $\frac{1}{m}$.

*Case 2: If the output of $(n_{k-1}+1)^{th}$ trial is not the same as that of the last $k-1$ trials, then the world is reset! We will have to again wait for $k$ consecutive identical outcomes. The number of trials required in this case will be $n_{k-1} + \mathbb{E}[N_{k}]$ with probability $1 - \frac{1}{m}$.

Hence, the above expression will become -
$$\begin{equation}\begin{aligned}
\mathbb{E}[N_k|N_{k-1}=n_{k-1}] &= (n_{k-1}+1) \times \frac{1}{m} + (n_{k-1}+\mathbb{E}[N_k]) \times \left(1 - \frac{1}{m}\right) \\
&= n_{k-1} + \frac{1}{m} + \left(1 - \frac{1}{m}\right)\mathbb{E}[N_k]
\end{aligned}\end{equation}$$
Now, replace $n_{k-1}$ with $N_{k-1}$ (just to keep in mind that $n_{k-1}$ here, is now a random variable) and use - $\mathbb{E}[\mathbb{E}[N_k|N_{k-1}]] = \mathbb{E}[N_k]$
$$\begin{equation}\begin{aligned}
\mathbb{E}[N_k] &= \mathbb{E}[\mathbb{E}[N_k|N_{k-1}]] = \mathbb{E}\left[N_{k-1} + \frac{1}{m} + \left(1 - \frac{1}{m}\right)\mathbb{E}[N_k]\right] \\
&= \mathbb{E}[N_{k-1}] + \left(1 - \frac{1}{m}\right)\mathbb{E}[N_k] + \frac{1}{m} \\
\implies \frac{1}{m}\mathbb{E}[N_k] &= \mathbb{E}[N_{k-1}] + \frac{1}{m} \\
\implies \mathbb{E}[N_k] &= m\mathbb{E}[N_{k-1}] + 1 \\
&= m\left(m\mathbb{E}[N_{k-2}] + 1 \right) + 1 = m^2\mathbb{E}[N_{k-2}] + m + 1  \\
&= m^{k-1}\mathbb{E}[N_{1}] + m^{k-2} + m^{k-3} + \ldots + m + 1  &&\quad\text{(By Recursion)} \\
&= m^{k-1} + m^{k-2} + m^{k-3} + \ldots + m + 1  &&\quad\text{($\mathbb{E}[N_1] = 1$)} \\
&= \frac{m^k - 1}{m-1}
\end{aligned}\end{equation}$$
Thus,
\begin{equation}
\mathbb{E}[N_k] = \mathbb{E}[N] = \frac{m^k - 1}{m-1}
\end{equation}
Which completes the proof.
A: We use the following generating function for $k\ge 2:$
$$G(z, u) = z^k\times \sum_{q\ge 0} u^q (z+z^2+\cdots+z^{k-1})^q
\\ = z^k \sum_{q\ge 0} u^q z^q (1+z+\cdots z^{k-2})^q
\\ = z^k 
\sum_{q\ge 0} u^q z^q \frac{(1-z^{k-1})^q}{(1-z)^q}
\\ = z^k \frac{1}{1-uz(1-z^{k-1})/(1-z)}
= z^k \frac{1-z}{1-z-uz(1-z^{k-1})}.$$
As a sanity check we  should get one when we sum the probabilities
of first getting $k$ consecutive outcomes after $n$ trials. This is
$$m \sum_{n\ge 0} m^{-n} [z^n]
\left. z^k \frac{1-z}{1-z-uz(1-z^{k-1})} \right|_{u=m-1}
\\ = m \sum_{n\ge 0} m^{-n} [z^n]
z^k \frac{1-z}{1-z-(m-1)z(1-z^{k-1})}
\\ = m \sum_{n\ge 0} m^{-n} [z^n]
z^k \frac{1-z}{1-mz+(m-1)z^k}
\\ = m \frac{1}{m^k} \frac{1-1/m}{(m-1)/m^k}
= \frac{1}{m^k} \frac{m-1}{(m-1)/m^k} = 1$$
and the sanity check goes through. Now for the expectation we obtain
$$m \sum_{n\ge 1} n \frac{1}{m^n} [z^n]
\left. z^k \frac{1-z}{1-z-uz(1-z^{k-1})} \right|_{u=m-1}
\\ = \sum_{n\ge 1} n \frac{1}{m^{n-1}} [z^n]
z^k \frac{1-z}{1-z-(m-1)z(1-z^{k-1})}
\\ = \left.
\left(z^k \frac{1-z}{1-mz+(m-1)z^{k}}\right)'\right|_{z=1/m}
\\ = \left.\left(k z^{k-1} \frac{1-z}{1-mz+(m-1)z^{k}}
- z^k \frac{1}{1-mz+(m-1)z^{k}} 
\\ - z^k \frac{1-z}{(1-mz+(m-1)z^{k})^2} (k(m-1)z^{k-1}-m)
\right)\right|_{z=1/m}.$$
Using $\left.1-mz+(m-1)z^{k}\right|_{z=1/m} = (m-1)/m^{k}$
we get
$$\frac{k}{m^{k-1}} (1-1/m) \frac{m^{k}}{m-1}
- \frac{1}{m^k} \frac{m^{k}}{m-1}
- \frac{1}{m^k} (1-1/m) \frac{m^{2k}}{(m-1)^2}
\left(\frac{k(m-1)}{m^{k-1}}-m\right)
\\ = k - \frac{1}{m-1}
- \frac{1}{m^{k+1}} \frac{m^{2k}}{m-1}
\frac{k(m-1)}{m^{k-1}} 
+ \frac{1}{m^{k+1}} \frac{m^{2k}}{m-1} m
\\ = k - \frac{1}{m-1} - k + \frac{m^k}{m-1}.$$
We thus obtain the end result
$$\bbox[5px,border:2px solid #00A000]{
\frac{m^k-1}{m-1}}$$
