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

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).

• No, but that might be more about the clarity of the Question. The coin cannot be anything, based on any part of its results. That would be to prove some kind of time-warping effect. Your coin could be shown to be whatever mattered, and "shown to be" is as different a question as heads or tails. Commented Feb 26, 2021 at 22:42

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.

• This seems to partition the $3n$ flips into $n$ non-overlapping groups. While the pattern may not overlap with itself, the pattern may start at any position in the sequence of flips, not just on positions of the form $3k+1$. Commented Sep 14, 2017 at 17:56
• Also, I think $q$ should be $p(1-p)^2$, not $p^3$. Obviously in the case of a fair coin, $p(1-p)^2=p^3$ though. Commented Sep 14, 2017 at 17:58
• The expected number of occurrences is $(100 + 1 - 3) / 2^3 = 12.25$.
– whuber
Commented Sep 14, 2017 at 18:19
• @Max Tried it once more, after some coffee :) Commented Sep 14, 2017 at 19:18
• @whuber: Whoops forgot to edit that part. Thanks for the corrections! Commented Sep 18, 2017 at 20:35