# Expected number of fair coin tosses until 2 consequitive heads, a non-recurseive solution

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

The "$$+1$$" is wrong. You are essentially trying to find the integral solutions to the equation

$$x_0+x_1+\cdots+x_{k+1} = n-2k$$

with the constraint $$0\leq x_i \leq n-2k$$.

Here $$x_i$$ is the number of $$0$$'s in the i'th placeholder. Notice that once you fix $$k$$, you only need to worry about placing the $$n-2k$$ zeros.

The number of solutions of $$x_1+\cdots+x_{k'} = n'$$ where $$0\leq x_i\leq n'$$ is $${n'+k'-1\choose k'-1}$$.

For us, $$n'=n-2k$$ and $$k'=k+1$$, so the number of solutions is $${n-k\choose k}$$.

• Thank you! I see where my mistake is now. Where I say The total number of positions to "put stuff", I use the number of the delimiters ($k+1$) instead of to the number of head-tail pairs ($k$). I need to use the latter, as head-tail pairs is what I'm putting, and not delimiters. I've seen the "integral solutions problem" but I'm often bugged by where (and whether) to add a $+1$ so I usually try to think in terms of delimiters and "raw" positions. – Al.G. Jul 12 at 8:26