# 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 Aug 12 '16 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. Aug 18 '18 at 19:49

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

for m>1 , since we have m outcomes done k times isn’t that m^k by multiplication principle