# Consecutive strings of heads problem

We toss a fair coin $n$ times and record the outcome as a sequence of H and T. We say that there is a run of heads if there is a consecutive string H...H which starts either at the first toss or after the coin lands tails and which ends either at the last toss or before the coin lands tails. For example, the sequence HTHHTHHHHTTHH has four runs of heads. Find the expected number of runs of heads.

So far I have:

Suppose the probability that all $K$ tosses have the same type of toss equal to the probability of all heads in $K$ tosses + probability of all tails in $K$ tosses.

Sets of subsequent $K$ tosses $=(n-k+1)$

Expected number of runs of heads equals the number of subsequent $K$ tosses times the probability that one set of $K$ tosses is a streak $= (n-k+1)\times 2\times (1/2)^k$

But I am really not sure about my solution, is this the right way to do this kind of probability problem?

• Your attempt (what follows "So far I have") is hard to understand. Perhaps you should try to edit it to make it clear – leonbloy Feb 13 '16 at 21:44

First, I want to explain what was wrong with your answer. Your answer should just have $\left(\frac 1 2\right)^K$ (not $2*\left(\frac 1 2\right)^K$) since you just want streaks of heads, not tails. Also, your final answer has $K$ in it, so you need to sum this up from $K=0$ to $n$. However, even if you do that, you won't actually get the correct answer because just because you have a set of consecutive tosses that are all heads doesn't mean that it's actually a run of head. For it to be a run of head, it needs to either be the whole string, start from the beginning and have tails immediately after it, have tails immediately before and after it, or have tails immediately before it and end at the end. Since we need to deal with all of these different cases, doing this method is going to be rather confusing, so let's take a simpler approach.

For $n=1$, the answer is $\frac 1 2$ because there are two possibilities: $H$ which has $1$ run of head and $T$ which has $0$ runs of heads.

For $n > 1$, the answer is $\frac 1 2+\frac{n-1}{4}$ because we add $\frac 1 4$ to the expected number of runs of heads each time we add on a new coin toss. This is because the probability that we add a run of head by adding on another coin toss to a random string is the probability that the coin ends in tails and the probability that the next coin toss is heads. This is clearly $\frac 1 2*\frac 1 2=\frac 1 4$, which means the probability we add another run of heads with another coin toss is $\frac 1 4$ each time.

Thus, the end result is that the expected value of the number of runs of heads after $n$ coin tosses is $\frac 1 2+\frac{n-1}{4}=\frac{n+1}{4}$.

• +1 though you could say for positive integer $n$ the answer is $\dfrac{n+1}{4}$ – Henry Feb 13 '16 at 21:55
• @Henry I added that at the end. Thanks for the tip! – Noble Mushtak Feb 13 '16 at 22:02

We could count start-of-runs: Let $X_i\in \{H,T\}$, ($i=1,2\cdots n$) be the coin values. Let $T_i=1$ if $X_i=H$ and $X_{i-1}=T$; we further imagine we have a ghost initial coin $X_0=T$.

Then the number of Head runs is just $t =\sum_{i=1}^n T_i$

Now, $E(T_i)=1/4$ for $i>1$, and $E(T_1)=1/2$

(Notice that $T_i$ are not independent, but this does not matter, linearity of expectation is all we need) Then the expected number of Head runs is

$$E(t)=\frac{1}{2} +(n-1)\frac{1}{4}=\frac{n+1}{4}$$

With $z$ representing tails and $w$ representing heads and $u$ counting runs we get the generating function

$$\frac{1}{1-z} \left(\sum_{q\ge 0} \left(u \frac{w}{1-w} \frac{z}{1-z}\right)^q\right) \left(1+u\frac{w}{1-w}\right).$$

Actually we are not interested in the distinction between heads and tails once runs have been counted so we may use

$$\frac{1}{1-z} \left(\sum_{q\ge 0} \left(u \frac{z^2}{(1-z)^2}\right)^q\right) \left(1+u\frac{z}{1-z}\right).$$

This is

$$\frac{1-z+uz}{(1-z)^2} \frac{1}{1-uz^2/(1-z)^2} = (1-z+uz) \frac{1}{(1-z)^2 - uz^2}.$$

Note that putting $u=1$ we obtain $$\frac{1}{1-2z}$$

which is good news because it shows we have counted all strings.

Now for the expected number of runs differentiate with respect to $u$ and set $u=1$ first getting

$$\frac{z}{(1-z)^2 - uz^2} - (1-z+uz) \frac{1}{((1-z)^2-uz^2)^2} (-z^2).$$

and then

$$\frac{z}{1-2z} + \frac{z^2}{(1-2z)^2} = \frac{z(1-2z)+z^2}{(1-2z)^2} = \frac{z-z^2}{(1-2z)^2}.$$

We thus get for the expectation

$$\frac{1}{2^n} [z^{n-1}] \frac{1}{(1-2z)^2} - \frac{1}{2^n} [z^{n-2}] \frac{1}{(1-2z)^2} \\ = \frac{1}{2^n} n 2^{n-1} - \frac{1}{2^n} (n-1) 2^{n-2} = \frac{1}{2} n - \frac{1}{4} (n-1) = \frac{1}{4} (n+1).$$