Is a coin biased based on the occurrence of substrings of its results?

Question

First off: yes, this is a homework question. Anything leading to the right answer or hints would be much appreciated! (Rather than simply providing an answer).

Okay, so say we have a coin where H = 0 and T = 1. And we flip it 100 times to create a binary sequence such as X = 00110100001001110.

Then we count the number of occurrences of the substring '100' (two, in the case above). And then we lose the original strip. In our strip, we counted 21 occurrences of the substring '100' (which cannot overlap with itself).

Question: Can we use the fact that we counted 21 occurrences to prove whether or not the coin is biased?

My line of thinking:

So I was dumbfounded to begin with, so I found the maximum and minimum number of times '100' could occur: 0 and 33, respectively.

Then I found the number of "frames" in a string that was 100 characters long: 100 - 3 + 1: 98.

And that really didn't seem to help, so I found the probability of any given sequence, provided we have a fair coin, as: $$(\frac{1}{2})^{100}$$

And thus the number of unique possibilities is the reciprocal of that.

For example, the number of times '100' could occur just once is 98 times that: $$98 \times (\frac{1}{2})^{100}$$

But calculating this for 1 occurrence, 2 occurrences, up to 33 is time consuming, so instead I calculated the chance it wouldn't occur as: $$(1 - (\frac{1}{2})^3)^{100}$$

And from there derived the probability it would occur exactly 21 times as: $$((1 - (\frac{1}{2})^{22})^{100}) - ((1 - (\frac{1}{2})^{20})^{100})$$

But then... I hit a roadblock. I'm not sure how to connect that probability back to the original question. Is it too high or low to be considered "normal"? What is "normal" in this context? Or am I just completely wrong?

Thanks so much!

(This is being done in R by the way, so any code/packages that lead in the right direction would be great as well).

Answer 1

The probability of each 100 occuring is $q:=p(1-p)^2$, where $p$ is the bias of the coin. The expected number of such occurances is then $(n-2)q$, where $n$ is the number of flips. The variance on this can be calculated as follows: each flip occurs at index $i$, so let $X_i$ denote the event that you get a 100 starting at index $i$. The variance of this will be less than $nq(1-q)$. This is because you can't have overlaps, so simultaneous occurrences of $X_i,X_j$ for $|i-j|\leq 2$ are negatively correlated. If you want to work it out exactly, note that $E[X_i]E[X_j]=q^2$. There are $n-3$ adjacent pairs $(i,i+1)$ of $X_i$ and $n-4$ occurances two apart. So

$$\mbox{Var}(X_1+\cdots+X_n)=(n-2)q(1-q)-2(n-3)q^2-2(n-4)q^2$$,

With $n=100$ flips and an unbiased coin $p=1/2$, you therefore expect around 12.25 occurrences, with a variance of around 4, so 21 occurances is not so reasonable.