6 Heads Followed by 6 Tails (Coin Flipping)

Question

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

The answer given is:

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?

Answer 1

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.

Answer 2

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.

Answer 3

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!!!