Independent trials, each of which is a success with probability $p$, are performed until there are $k$ consecutive successes. Let $N_k$ denote the number of necessary trials to obtain $k$ consecutive successes, and show that:

$$\mathbb{E}(N_k|N_{k−1}) = N_{k−1} + 1 + (1 − p)\mathbb{E}(N_k).$$

up vote 2 down vote accepted

You are conditioning on $N_{k-1}$, which means you are conditioning on the fact that you have $k-1$ consecutive successes. Let $X \sim \text{Bern}(p)$ be the outcome of the next trial and consider the cases:

  • If $X=1$ then you now have $k$ consecutive successes;
  • If $X=0$ then you now have $0$ consecutive successes and you have to start all over again.

Hence, by application of the law-of-total probability you have:

$$\begin{equation} \begin{aligned} \mathbb{E}(N_k|N_{k-1}) &= \mathbb{P}(X=1|N_{k-1}) \mathbb{E}(N_k|N_{k-1},X=1) + \mathbb{P}(X=0|N_{k-1}) \mathbb{E}(N_k|N_{k-1},X=0) \\[6pt] &= p \mathbb{E}(N_k|N_{k-1},X=1) + (1-p) \mathbb{E}(N_k|N_{k-1},X=0) \\[6pt] &= p(N_{k-1}+1) + (1-p) (N_{k-1}+1 + \mathbb{E}(N_k)) \\[6pt] &= p(N_{k-1}+1) + (1-p) (N_{k-1}+1) + (1-p) \mathbb{E}(N_k) \\[6pt] &= N_{k-1}+1 + (1-p) \mathbb{E}(N_k). \\[6pt] \end{aligned} \end{equation}$$

I'll give you the basic reasoning here, but you can write it out formally yourself.

Let $N_k$ be the number of trials necessary to obtain $k$ consecutive successes.

We want to show

$$E[ N_k | N_{k-1}]= N_{k-1} + 1 + (1-p)E[N_k]$$

Firstly, given $N_{k-1}$, consider the possible values of $N_{k-1}+1$. If the trial immediately following the $N_{k-1}$'th trial is a success, then clearly $N_k = N_{k-1}+1$ with probability $p$.

Next, suppose the trial following $N_{k-1}$ is a failure. So that we have $N_{k-1}+1$ total trails with the last one being a failure. Well, since the last one is a failure, then by the independence of each trial, under this situation we would have the conditional expected number of trials until $k$ consecutive successes as

$$N_{k-1} + 1 + E[N_k]$$

Since we already have $N_{k-1} + 1$ trials, but the last one being a failure "resets" our expectation back to $E[N_k]$.

Hence you can express the original expectation as

$$E[ N_k | N_{k-1}]= p(N_{k-1} + 1) + (1-p)(N_{k-1} + 1 + E[N_k])$$

$$=N_{k-1} + 1 + (1-p)E[N_k]$$

This answer uses the law of total expectation: $E[ E[X|Y] ] = E[X]$. Here we take $Y$ as the result of the $N_{k-1}+1$ trial, and $X$ as $N_{k}|N_{k-1}$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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