# 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 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.

• "you need to get that different thing $k$ times now" Not necessarily "that different thing" but it is true that one starts anew hence your intuition is correct. +1.
– Did
Commented Aug 12, 2016 at 13:12
• +1 for not only answering your own question, but doing so in a much slicker way than Marko Reidel's method.
– J.G.
Commented Aug 18, 2018 at 19:49

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 -
$$$$\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)$$\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{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} 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{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} Thus, $$$$\mathbb{E}[N_k] = \mathbb{E}[N] = \frac{m^k - 1}{m-1}$$$$ Which completes the proof.

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