Xpectation Mania #1

Let $X_{n,j}$ be the expected number of additional tosses needed to end up with a streak of $n$ Heads in a row given that the current streak of Heads is of length $j$ . Then $X_{n,n} = 0$ and (conditioning on the outcome of the next toss): $X_{n,j} \; = \; \tfrac12(1 + X_{n,j+1}) + \tfrac12(1 + X_{n,0}) \hspace{1.5cm} 0 \le j \le n-1$ so that $\begin{aligned} 2X_{n,j} - X_{n,j+1} & = \; 2 + X_{n,0} \\ \frac{X_{n,j}}{2^j} - \frac{X_{n,j+1}}{2^{j+1}} & = \; \frac{2 + X_{n,0}}{2^{j+1}} \\ X_{n,0} - \frac{X_{n,j}}{2^j} & = \; \sum_{k=0}^{j-1}\frac{2 + X_{n,0}}{2^{k+1}} \; = \; (2 + X_{n,0})(1 - 2^{-n}) \\ f(n) \; = \; X_{n,0} & = \; 2(2^n-1) \end{aligned}$ which makes $f(8) = 2(2^8-1) = \boxed{510}$ .

Alternatively, if we consider the first $n$ tosses, then there could be anything between $0$ and $n$ tails before we get the first head. Thus we deduce that (we are conditioning on the possibility of there being $j-1$ Heads, followed by a Tail (for $1 \le j \le n$ ), or else there are $n$ Heads, in the next few tosses): $\begin{aligned} f(n) & = \; \sum_{j=1}^{n} \frac{1}{2^j}\big(j + f(n)\big) + \frac{1}{2^n}\times n \\ & = \; \sum_{j=1}^{n} \frac{j}{2^j} + \frac{n}{2^n} + (1 - 2^{-n})f(n) \\ 2^{-n}f(n) & = \; 2 - 2^{1-n} \\ f(n) & = \; 2(2^n-1) \end{aligned}$ (again).