3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

By stars and bars theorem 2,

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Al.G. Jul 12 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.