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.


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.

  • 1
    $\begingroup$ "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. $\endgroup$ – Did Aug 12 '16 at 13:12
  • $\begingroup$ +1 for not only answering your own question, but doing so in a much slicker way than Marko Reidel's method. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.