Let the probability of obtaining head, when a coin is tossed, be $p$. Let the coin be tossed, many times, independently and
$X_n :=$the number of flips it takes to get a run of $n$ successive heads.
How do I find $E(X_{n+1}|X_n=k) $ ?
I'm completely clueless here, I don't know what is the joint p.m.f. of $X_n$ and $X_{n+1}$. Or is there any clever way to do it ?
Please help
Consider the event $\{X_n=k\}$. The next flip can be head with probablity $p$. In this case $X_{n+1}=k+1$. Or the next flip can be tail with probability $1-p$. Then we begin to flip a coin again after $k+1$ trials, and wait for the next possibility to get a run of $n+1$ successive heads. In this case we will wait in average $k+1+\mathop{\mathbb E}[X_{n+1}]$ tosses.
So $$\tag{1}\label{1} \mathop{\mathbb E}(X_{n+1}\mid X_n=k) = p\cdot (k+1) + (1-p)\cdot (k+1 + \mathop{\mathbb E}[X_{n+1}]). $$ If you have a value $\mathop{\mathbb E}[X_{n+1}]$ you can use it here. If not, one can use Law of total expectation to obtain recurrence relation on $x_n=\mathop{\mathbb E}[X_{n}]$: $$ x_{n+1}=\mathop{\mathbb E}\mathop{\mathbb E}(X_{n+1}\mid X_n) =\mathop{\mathbb E}[ p\cdot (X_n+1) + (1-p)\cdot (X_n+1 + x_{n+1})] $$ $$ = p\cdot (x_n+1) + (1-p)\cdot (x_n+1 + x_{n+1}). $$ Rewrite it and get $x_{n+1}=\frac{x_n+1}{p}$. Since $x_1=\frac1p$, one can get $$ x_2=\frac1p+\frac{1}{p^2}, \ \ldots, \ x_{n+1} = \sum_{i=1}^{n+1} \frac{1}{p^i}=\frac{1-p^{n+1}}{p^{n+1}(1-p)}. $$ Finally you can use it in (\ref{1})