Trying to find the expected number of fair coin tosses until 2 consequitive heads fall, I didn't come up with the recursive solution initially and used a more 'iterative' or 'brute-force' approach, which lead me to a different answer, without any hints where I might be wrong. I couldn't find a similar solution on the Internet, to which I could compare mine, so I'd love if someone could point me to the flaw in my logic. Here is my attempt:
Let $X$ be the random variable for which I'm searching the expected value $\text{E}X$.
I'm building a series $\sum_0^\infty n \cdot P(X=n)$, and my goal is to find the probabiity that a game lasts $n$ tosses - $P(X = n)$, for all $n \in \mathbb N$.
The general form of a single play is as follows: $$ \underbrace{\dots 0\,1\,0 \dots 0\,1\,0\dots0}_{n \,\text{tosses}}\;1\,1 $$ i.e. a bunch of heads, surrounded by tails, and two heads at the end. Denote the number of tosses before the final two heads with $n$. It is clear there are at least 2 tosses in a single (successful) run, and $n \ge 0$. For convenience I use $n$ for the tosses before the final two heads, and not for the length of the whole run.
Now I need to count the possible plays for any given length (starting from 2), and the answer is then: $$\text{E}X := \sum_{t=0}^\infty t \cdot P(X=t) = \sum_{n=0}^\infty (n+2) \cdot \frac{\text{No. of valid non-final parts of length } n}{2^{n+2}}$$
(The second sum in fact skips runs of length 0 and 1 as they contribute nothing to the expected value.)
The number of valid plays of length $n$ I find by looking at all possible cases for the number of heads in the non-final part of the string - let's call that $k$. For a given $n$, the number of non-final heads can be at most half of $n$, since each head must be followed by a tail.
Let's fix an $n \in \mathbb N$ and a number of heads $k \in [0,\lfloor \frac{n}{2}\rfloor]$. The picture in my head is like this:
$$ \|\,(10)\,\|\,(10)\,\|\,\dots\,\|\,(10)\,\| \; 1\, 1 $$
where "$\|$"s represent the $k + 1$ placeholders for the $n-2k$ tails I must arrange around the $k$ head-tail pairs in a $(n + 2)$-toss-long play.
The total number of positions to "put stuff" (tails and head-tails pairs) is $(k + 1) + (n-2k) = n - k + 1$.
Moreover, every configuration is uniquely described by the positions of the $k$ head-tail pairs, and all possible positions of $k$ head-tail pairs make up a valid toss sequence.
Therefore, given $n$ and $k$, the number of valid runs with $k$ non-final tails of length $n+2$ is $\binom{n-k+1}{k}$. (These 2-3 lines were a part I suspected for some time that it could be wrong, but I cannot see any mistakes here.)
Letting $k$ range over $[0, \lfloor \frac{n}{2} \rfloor]$, the probability that a play lasts $n + 2$ tosses is:
$$P(X = n+2) = \frac{\sum_{k=0}^{ \lfloor n / 2 \rfloor} \binom{n-k+1}{k}}{2^{n+2}}$$ And finally, the series for the expected value:
$$\text{E}X = \sum_{n=0}^\infty n \cdot P(X=n) = \sum_{n=0}^\infty \left(\frac{n+2}{2^{n+2}}\cdot\sum_{k=0}^{ \lfloor n / 2 \rfloor} \binom{n-k+1}{k}\right)$$
Giving this to Wolfram Mathematica, I see that it quickly converges to $8.888...$. After 2 or 3 random attempts to "make it work" I found that removing the "+ 1" part in the binomial coefficient produces the correct answer (6), so I thought this part could be wrong. There should definitely be a $+1$ in it, though (for the reasons I explained above), and I think it's just a coincidence that I get the correct answer this way.
As much as I hope that is not the case, it's possible that only my code is wrong, here's it for reference: https://pastebin.com/iuPW7f8H (I couldn't make it compute the actual limit so I checked the result for some sample points).
(I use the words 'run' and 'play' interchangably for a single sequence of tosses in a valid experiment as said in the problem, please let me know if there's a more standard term for this.)
