Checking if a coin is fair

I was asked the following question by a friend. I could not help her out but I hope someone can explain it to me. I could not find any similar example.Thanks for any help and explanation.

Q: Results of 100 coin toss experiments are recorded as 0="Tail" and 1="Head". The output x is a string of 0's and 1 of length 100. And the number of times when we get 1-0-0 in x is calculated and it is 20 (ex: if x=(001001110100), 1-0-0 occurs 2 times). Do you think this is a fair coin?

• This question doesn't sound like an exact reallife problem. Is this homework? – Martijn Weterings Feb 11 at 16:04
• I am not sure. As I indicated it was asked me by a friend. I could not help her out, but I still want to learn how to solve or answer this kind of question.@MartijnWeterings – Jimmy Dur Feb 11 at 16:08
• stats.stackexchange.com/questions/158490/… contains a fairly full account of the situation. For more, see stats.stackexchange.com/… – whuber Feb 11 at 20:32
• @JimmyDur don't you have any idea about the interpretation or meaning of the question. For instance. You phrase the question as "Do you think this is a fair coin?". This sounds like a trick question. – Martijn Weterings Feb 11 at 21:26
• ... However, from certain points of view this might not be a correct way to tackle it, and one might desire a Bayesian approach, e.g. if one knows something like a prior probability distribution of fairness of coins. Without any knowledge of the background and circumstances any computation will just be math exercise and not an answer to your explicit question "do you think this is a fair coin?". – Martijn Weterings Feb 11 at 21:29

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 100 coin flips is equal to the 1 minus the probability that it takes more that 100 flips to make 20 sequences'. 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
 0.0003247105
> # estimated from simulation
> sum(counts>=20)/10^6
 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).
• Why not pursue a closed form solution via MLE? – Digio Feb 11 at 20:42
• I don't, I'm just curious. Wouldn't $\hat{p}_{ML} = argmax_p [P(X_1,...,X_n | p, n)]$ with $X \sim Binomial(n, p)$ and a confidence interval for $\hat{p}_{ML}$ make a valid answer, @whuber ? – Digio Feb 11 at 22:12
• Thanks for this thorough answer Martijn, I really like the second approach. My thoughts were along the lines of a more direct solution: estimate $p$ as the parameter of a single Binomial or multiple Bernoulli distributions. Then if the confidence interval of probability $p$ does not include .5, then we'd say that the coin is biased. – Digio Feb 12 at 9:42
• For example, for $X=\{0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0\}$, we get $\hat{p} = {{x}\over{n}}={5 \over 12}=0.42$ with a margin of error $1.96 \sqrt{\hat{p}(1-\hat{p}) \over {n}} = 0.28$. And since $0.42+0.28 < 0.50$, we may conclude that the coin is not biased (at the 5% significance level). – Digio Feb 12 at 9:42
• @FrankHarrell neither is there anything in the problem setup that makes us think that the flips are uncorrelated. The problem setup is relatively poor with information. My example that goes into the correlation of flips is just in order to cover the broadness of the question. I am not stating that this is the way to answer it. But say that somebody (possibly the OP) is doing research on DNA sequences or some other problem setup where the possibility of correlation makes more sense, then they have an example how it could turn out. – Martijn Weterings Feb 12 at 14:07