Solving the problem by simulation
My first attempt would be to simulate this on a computer, which can flip many fair coins very fast. Below is an example with one milion trials. The event 'that the number of times $X$ the pattern '1-0-0' occurs in $n=100$ coin flips is 20 or more' occurs roughly once every three thousand trials, so what you observed is not very likely (for a fair coin).
Note that the histrogram is for the simulation and the line is the exact computation explained further below.
set.seed(1)
# number of trials
n <- 10^6
# flip coins
q <- matrix(rbinom(100*n, 1, 0.5),n)
# function to compute number of 100 patterns
npattern <- function(x) {
sum((1-x[-c(99,100)])*(1-x[-c(1,100)])*x[-c(1,2)])
}
# apply function on data
counts <- sapply(1:n, function(x) npattern(q[x,]))
hist(counts, freq = 0)
# estimated probability
sum(counts>=20)/10^6
10^6/sum(counts>=20)
Solving the problem with an exact computation
For an analytical approach you can use the fact that 'the probability to observe 20 or more sequences '1-0-0' in hundred coin flips is equal to the 1 minus the probability that it takes more that hundred flips to make 20 of those sequences'. (for this correspondence between counts and waiting time see also: https://stats.stackexchange.com/a/450135)
This is solved in the following steps:
Waiting time for probability of flipping '1-0-0'
The distribution, $f_{N,x=1}(n)$, of the number of times you need to flip untill you get exactly one sequence '1-0-0' can be computed as following:
Let's analyse the ways to get to '1-0-0' as a Markov chain. We follow the states described by the suffix of the string of flips: '1', '1-0', or '1-0-0'. For example if you have the following eight flips 10101100 then you passed, in order, the following eight states: '1', '1-0', '1', '1-0', '1', '1', '1-0', '1-0-0' and it took eight flips to reach '1-0-0'. Note that you do not have equal probability to reach the state '1-0-0' in every flip. Thus you can not model this as a binomial distribution. Instead you should follow a tree of probabilities. The state '1' can go into '1' and '1-0', the state '1-0' can go into '1' and '1-0-0', and the state '1-0-0' is an absorbing state. You can write it down as:
number of flips
1 2 3 4 5 6 7 8 9 .... n
'1' 1 1 2 3 5 8 13 21 34 .... F_n
'1-0' 0 1 1 2 3 5 8 13 21 F_{n-1}
'1-0-0' 0 0 1 2 4 7 12 20 33 sum_{x=1}^{n-2} F_{x}
and the probability to reach the pattern '1-0-0', after having rolled a first '1' (you start with the state '0', not having flipped a heads yet), within $n$ flips is a half times the probability to be in state '1-0' within $n-1$ flips:
$$f_{N_c,x=1}(n) = \frac{F_{n-2}}{2^{n-1}}$$
where $F_i$ is the $i$-th Fibonnaci number. The non-conditional probability is a sum
$$f_{N,x=1}(n) = \sum_{k=1}^{n-2} 0.5^{k} f_{N_c,x=1}(1+(n-k)) = 0.5^{n} \sum_{k=1}^{n-2} F_{k}$$
Waiting time for probability of flipping $k$ times '1-0-0'
This you can compute by a convolution.
$$f_{N,x=k}(n) = \sum_{l=1}^{n} f_{N,x=1}(l)f_{N,x=1}(n-l)$$
you will get as probability to observe 20 or more '1-0-0' patterns (based on the hypothesis that the coin is fair)
> # exact computation
> 1-Fx[20]
[1] 0.0003247105
> # estimated from simulation
> sum(counts>=20)/10^6
[1] 0.000337
Here is the R-code to compute it:
# fibonacci numbers
fn <- c(1,1)
for (i in 3:99) {
fn <- c(fn,fn[i-1]+fn[i-2])
}
# matrix to contain the probabilities
ps <- matrix(rep(0,101*33),33)
# waiting time probabilities to flip one pattern
ps[1,] <- c(0,0,cumsum(fn))/2^(c(1:101))
#convoluting to get the others
for (i in 2:33) {
for (n in 3:101) {
for (l in c(1:(n-2))) {
ps[i,n] = ps[i,n] + ps[1,l]*ps[i-1,n-l]
}
}
}
# cumulative probabilities to get x patterns in n flips
Fx <- 1-rowSums(ps[,1:100])
# probabilities to get x patterns in n flips
fx <- Fx[-1]-Fx[-33]
#plot in the previous histogram
lines(c(1:32)-0.5,fx)
Computing for unfair coins
We can generalize the above computation of the probability to observe $x$ patterns in $n$ flips, when the probability of '1=head' is $p$ and the flips are independent.
We now use a generalization of the Fibonacci numbers:
$$F_{n}(x) = \begin{cases}
1 & \quad \text{if $n=1$} \\
x & \quad \text{if $n=2$} \\
x(F_{n-1}+ F_{n-2}) & \quad \text{if $n>2$}
\end{cases}$$
the probabilities are now as:
$$f_{N_c,x=1,p}(n) = (1-p)^{n-1} F_{n-2}((1-p)^{-1}-1)$$
and
$$f_{N,x=1,p}(n) = \sum_{k=1}^{n-2} p(1-p)^{k-1} f_{N_c,x=1,p}(1+n-k) = p(1-p)^{n-1}\sum_{k=1}^{n-2} F_{k}((1-p)^{-1}-1)$$
When we plot this you get:
So while the p-value is small for a fair coin 0.0003247, we must note that it is not much better (only a single order) for different unfair coins. The likelihood ratio, or Bayes factor, is around 11 when the null hypothesis ($p=0.5$) is compared with the alternative hypothesis $p=0.33$. This means that the posterior odds ratio is only ten times higher than the prior odds ratio.
Thus if it you thought before the experiment that the coin was unlikely unfair, then now you should still think the coin is unlikely unfair.
A coin with $p_{heads} = p_{tails}$ but unfairness regarding '1-0-0' occurences
One could much easier test the probability for a fair coin by counting the number of heads and tails and use a binomial distribution to model these observations and test whether the observation is particular or not.
However it might be that the coin is flipping, on average, an equal number of heads and tails but is not fair regarding certain patterns. For instance the coin might have some correlation for succeeding coin flips (I imagine some mechanism with cavities inside the metal of the coin that are filledwith sand that will flows like an hourglass towards the opposite end of the previous coin flip, which is loading the coin to fall more likely on the same side as the previous side).
Let the first coin flip be equal probability heads and tails and succeeding flips are with probability $p$ the same side as the flip before. Then a similar simulation as the beginning of this post will give the following probabilities for the number of times that the pattern '1-0-0' exceeds 20:
You can see that it is possible to make it slighlty more likely to observe the '1-0-0' pattern (somewhere around $p=0.45$ a coin that has some negative correlation), but more dramatic is that one can make it much less likely to oberve the '1-0-0' pattern. For low $p$ you get many times the tails after a heads, the first '1-0' part of the '1-0-0' pattern, but you do not get so often two tails in a row the '0-0' part of the pattern. The opposite is true for the high $p$ values.
# number of trials
set.seed(1)
n <- 10^6
p <- seq(0.3,0.6,0.02)
np <- length(p)
mcounts <- matrix(rep(0,33*np),33)
pb <- txtProgressBar(title = "progress bar", min = 0,
max = np, style=3)
for (i in 1:np) {
# flip first coins
qfirst <- matrix(rbinom(n, 1, 0.5),n)*2-1
# flip the changes of the sign of the coin
qrest <- matrix(rbinom(99*n, 1, p[i]),n)*2-1
# determining the sign of the coins
qprod <- t(sapply(1:n, function(x) qfirst[x]*cumprod(qrest[x,])))
# representing in terms of 1s and 0s
qcoins <- cbind(qfirst,qprod)*0.5+0.5
counts <- sapply(1:n, function(x) npattern(qcoins[x,]))
mcounts[,i] <- sapply(1:33, function(x) sum(counts==x))
setTxtProgressBar(pb, i)
}
close(pb)
plot(p,colSums(mcounts[c(20:33),]),
type="l", xlab="p same flip", ylab="counts/million trials",
main="observation of 20 or more times '1-0-0' pattern \n for coin with correlated flips")
points(p,colSums(mcounts[c(20:33),]))
Using the mathematics in statistics
The above is all fine but it is not a direct answer to the question
"do you think this is a fair coin?"
To answer that question one can use the mathematics above but one should really first describe very well the situation, the goals, definition of fairness, etc. Without any knowledge of the background and circumstances any computation will just be math exercise and not an answer to the explicit question.
One open question is why and how we are looking for the pattern '1-0-0'.
- For instance maybe this pattern was not a target, which was decided upon before doing the investigation. Maybe it was just something that 'stood out' in the data and it was something that got attention after the experiment. In that case one needs to consider that one is effectively making multiple comparisons.
- Another issue is that the probabilty calculated above is a p-value. The meaning of a p-value needs to be considered carefully. It is not the probability that the coin is fair. It is, instead, the probability to observe a particular result if the coin is fair. If one has an environment in which one knows some distribution of the fairness of coins, or one can make a reasonable assumption, then one can take this into account and use a Bayesian expression.
- What is fair, what is unfair. Eventually, given enough trials one may find some tiny little bit unfairness. But is it relevant and is such a search not biased? When we stick to a frequentist approach, then one should describe something like a boundary above which we consider a coin fair (some relevant effect size). Then one could use something similar to the two one sided t-test in order to decide whether the coin is fair or not (regarding the '1-0-0' pattern).
