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?
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?
 A: 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.
A: 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:

*

*$(H,T,H, *,*,*,*)$

*$(*,H,T,H, *,*,*)$

*$(*,*,H,T,H, *,*)$

*$(*,*,*,H,T,H, *)$

*$(*,*,*,*,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.
A: 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!!!
