So the question asks:
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?
Best Answer
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}$.