Conditional probability for consecutive Bernoulli trials

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).$$

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