6 Heads Followed by 6 Tails (Coin Flipping)

You throw a fair coin one million times. What is the expected number of strings of 6 heads followed by 6 tails?

There are $$1,000,000 - 11$$ possible slots for the sequence to occur. In each of these slots, the probability is $$2^{-12}$$. Due to linearity of expected value, the answer is therefore $$(1,000,000 - 11)\times2^{-12}$$.

I don't understand why this solution works. Shouldn't there be any consideration of the fact that at most only $$\dfrac{1,000,000 - 11}{12} \approx 83332$$ strings of 6 heads followed by 6 tails can occur. Can anyone please help me understand the solution?

• The source of this exercise should somewhere explain the concept of "linearity of expected value," the key word being "linearity." I recommend looking for that explanation. Nov 27 '21 at 13:50

Maybe it helps to do a simpler example, so let's do $$3$$ coin flips, and let's look at the expected number of times you get $$1$$ head followed by $$1$$ tail.

Now, there are $$8$$ possible outcomes:

$$TTT$$

$$TTH$$

$$THT$$

$$THH$$

$$HTT$$

$$HTH$$

$$HHT$$

$$HHH$$

Note that $$HT$$ occurs $$4$$ times, so the expected number of $$HT$$'s to occur is $$\frac{4}{8}=\frac{1}{2}$$

Now, notice that there are two 'slots' for an $$HT$$ to appear: the first two flips, or the second and third flip.

Also note that $$HT$$ occurs two times for the first two slots, so the expected number of $$HT$$'s for the first slot is $$\frac{2}{8}=\frac{1}{4}$$

And the same is true for the second slot. That is, the expected number of $$HT$$'s for the second slot is also $$\frac{1}{4}$$

And now note that $$\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$. That is: the expected number of $$HT$$'s occuring anywhere in the sequence is the expected number of $$HT$$'s to occur in the first slot added to the expected number of $$HT$$'s in the second slot. ... And of course this should be as such: we have $$4$$ $$HT$$'s total out of the $$8$$ equally likely strings, and that $$4$$ is the sum of $$2$$ and $$2$$. This is what they mean by the 'linearity of expected value'

So, the fact that you can have at most $$1$$ $$HT$$ in a sequence of $$3$$ is irrelevant.

The same thing happens in your problem: out of all possible outcomes, some of the $$HHHHHHTTTTTT$$ strings will occur in the first slot (throws $$1$$ though $$12$$), some will occur in the second slot (throws $$2$$ through $$13$$), etc. And in the end, you just end up adding all those. Again, the fact that you cannot have a $$HHHHHHTTTTTT$$ in the first and in the second slot at the same time is again irrelevant.

Let's work with smaller numbers so I can type all the possibilities. Say you flip a coin $$7$$ times and you're asked about the number of times you get a string of $$(H,T,H)$$. Well, the following outcomes are what you would be on the lookout for:

1. $$(H,T,H, *,*,*,*)$$
2. $$(*,H,T,H, *,*,*)$$
3. $$(*,*,H,T,H, *,*)$$
4. $$(*,*,*,H,T,H, *)$$
5. $$(*,*,*,*,H,T,H)$$

where the $$*$$ indicates either of $$H$$ or $$T$$, but we don't really care for the moment.

These are the only ways you could get the specified string $$(H,T,H)$$ out of $$7$$ flips. Notice there are $$7-3+1=5$$ ways. So, here we're making the (not so deep) observation that an occurrence of $$(H,T,H)$$ within a flip of $$7$$ coins is fully characterized by when it begins.

Note that we don't want to do something like $$7/3=2+\frac{1}{3}\approx 2$$ and claim that there are only two positions where we can get $$(H,T,H)$$. When you do such a division, you're only taking into account occurrences of $$(H,T,H)$$ which are "disjoint" (i.e options (1), (5) above). For example, $$(H,T,H,*,H,T,H)$$ is an example of what (I think) you might be thinking of, but you're missing out on several others.

Just to be concrete, here is a possible outcome $$\omega=(H,T,H,T,H,T,H)$$. The number of occurrences of the string $$(H,T,H)$$ is 3 here (we have options (1), (3), (5) happening here).

Consider the random variable $$N$$ which describes how many times a string of $$(H,T,H)$$ is found in a flip of seven coins. Then \begin{align} N=\sum_{i=1}^5\mathbf{1}_{\{\omega\,: (\omega_i,\omega_{i+1},\omega_{i+2})=(H,T,H)\}} \end{align} Here $$\mathbf{1}_A$$ means the indicator function of the set $$A$$. The above sum just adds a $$1$$ if we find $$(H,T,H)$$ in the $$i,i+1,i+2$$ slots, and it does so for each $$1\leq i\leq 5$$, so it counts all the times it sees a string of $$(H,T,H)$$. By linearity of expectation (or integrals) it follows that \begin{align} \Bbb{E}(N)=\sum_{i=1}^5\Bbb{E}\left(\mathbf{1}_{\{\omega\,: (\omega_i,\omega_{i+1},\omega_{i+2})=(H,T,H)\}}\right)= 5\cdot 2^{-3} \end{align} In your problem, you just have to replace the number $$7$$ by $$10^6$$ (a million) and $$3$$ (the length of the string) by $$12$$.

Now, as a bonus, try to figure out the general formula for when you do $$n$$ coin flips, and you're looking for expected value of the number of times a certain string of length $$k$$ (where $$1\leq k\leq n$$) occurs.

So you want to know how often the pattern

$$HHHHHHTTTTTT$$

appears on million fair coin tosses. Note that we must consider another pattern

$$THHHHHHTTTTTTH$$

to count all possibilities right.

We generalize the problem taking unfair coin with probability of heads equal to $$p$$ and tails equal to $$q=1-p$$ and consider a case of strings of $$m$$ heads followed by $$m$$ tails. $$m=6$$ corresponds to the original case.

Let $$u_n$$ be the probability of the pattern at the $$n$$th flip. The probability that there are $$m+1$$ heads and $$m+1$$ tails in $$2m+2$$ flips is

$$(pq)^{m+1}$$

The pattern may also appear at the $$(n-2m)$$th flip. Because these two appearances of the pattern are mutually exclusive we get the following recurrence relation

$$u_n+u_{n-2m}(pq)^m=(pq)^{m+1}$$

Note that $$u_n$$ is not a probability mass function.

Now, theory says that

$$\lim_{n \to \infty}u_n=\frac{1}{E(x)}$$

Here $$E(x)$$ denotes the expectation of the number of flips until the first occurrence of the pattern. Thus

$$E(x)=\frac{1+(pq)^m}{(pq)^{m+1}}$$

Or in the case of fair coin ($$p=q=\frac{1}{2}$$)

$$E(x)=4(4^m+1)$$ For the original case $$m=6$$

$$E(x)=16388$$

Thus the expected number of this pattern in one million flips of a fair coin is

$$\frac{1000000}{16388}\approx 61$$

Quite a complicated calculation gives the following expression for the variance (fair coin case)

$$Var(x)=16^{m+1}+(20-16m)4^m+4$$

From this the standard deviation for $$m=6$$

$$SD=\sqrt{Var(x)}=16374.5$$

That means the expectation is roughly equal to the standard deviation!!!