4
$\begingroup$

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.

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • 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
    Commented Aug 12, 2016 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.
    Commented Aug 18, 2018 at 19:49
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .