5
$\begingroup$

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?

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ Nov 27 '21 at 13:50
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.