Determining whether a sequence of coin flips is random

Question

Say we have observed a finite sequence of coin flips. Is there a metric for how likely this sequence is generated by a truly random coin flip.

For example, if we flip a coin 1000 times presumably seeing 500 heads and then 500 tails is less likely than a random assortment of Heads and Tails.

Also, presumably we would not see every even flip be a tails and every odd flip to be a heads.

Answer 1

There are some different metrics which can be used to indicate randomness when flipping a coin. One of these is to analyze the length of longest runs.

Longest runs:

A run is a sequence of consecutive heads or tails. We can calculate the probability of runs of length $k$ of a fair coin via the generating function \begin{align*} W_k(z)=\frac{1-z^{k+1}}{1-2z+z^{k+1}} \end{align*} where the coefficient $[z^n]$ of $W_k(z)$ gives the number of possibilities to have runs of length $\leq k$ when flipping a coin $n$ times. The probability for a run having length $k$ is therefore \begin{align*} \frac{1}{2^n}[z^n]\left(\frac{1-z^{k+1}}{1-2z+z^{k+1}}-\frac{1-z^{k}}{1-2z+z^{k}}\right) \end{align*}

The derivation of this generating function is given in detail in section I.4.1 in Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick.

They also cite a nice story attributed to T. Varga (p. 52) around this theme:

• ''A class of high school children is divided into two sections. In one of the sections, each child is given a coin which he throws two hundred times, recording the resulting head and tail sequence on a piece of paper. In the other section, the children do not receive coins, but are told instead that they should try to write down a ‘random’ head and tail sequence of length two hundred. Collecting these slips of paper, [a statistician] then tries to subdivide them into their original groups. Most of the time, he succeeds quite well.”

  The statistician’s secret is to determine the probability distribution of the maximum length of runs of consecutive letters in a random binary word of length $n$ (here $n=200$). The probability that this parameter equals $k$ is \begin{align*} \frac{1}{2^{200}}[z^{200}]\left(\frac{1-z^{k+1}}{1-2z+z^{k+1}}-\frac{1-z^{k}}{1-2z+z^{k}}\right) \end{align*} The probabilities are then easily computed using any symbolic package: for $n=200$, the values found are $$ \begin{array}{r|ccccc} k&3&4&5&\color{blue}{6}&\color{blue}{7}\\ \hline\\ \mathbb{P}(k)&6.54\,10^{-8}&7.07\,10^{-4}&0.0339&\color{blue}{0.1660}&\color{blue}{0.2574}\\ \\ \\ k&\color{blue}{8}&\color{blue}{9}&\color{blue}{10}&\color{blue}{11}&\color{blue}{12}\\ \hline\\ \mathbb{P}(k)&\color{blue}{0.2235}&\color{blue}{0.1459}&\color{blue}{0.0829}&\color{blue}{0.00440}&\color{blue}{0.0226}\\ \end{array} $$ Thus, in a randomly produced sequence of length $200$, there are usually runs of length $6$ or more: the probability of the event turns out to be close to $97\%$ (and there is still a probability of about $8\%$ to have a run of length $11$ or more). On the other hand most children (and adults) are usually afraid of writing down runs longer than $4$ or $5$ as this is felt as strongly “non-random”. The statistician simply selects the slips that contain runs of length $6$ or more as the true random ones. Voilà!

Another metric is the first and last equality of number of heads and tails when flipping a fair coin $n$ times. This is strongly connected with the so-called Arcsine law. The following is from chapter III: Fluctuations in Coin Tossing and Random Walks of the classic An Introduction to Probability Theory and Its Applications, Vol. I by W. Feller.

Arcsine law:

Let's assume we play a game, flipping a fair coin. We interprete resulting sequences of heads and tails as random walks starting in $(0,0)$ and going $(1,1)$ if head occurs and $(1,-1)$ if tail occurs.

Then the following is valid: With probability $\frac{1}{2}$ no equalization occurs in the second half of the game regardless of the length of the game. Furthermore, the probabilities near the end point are greatest.

This is due to the Arcsine law for last visits (see e.g. Vol 1, ch.3, section 4, Theorem 1 in W. Feller's book): The probability that up to and including epoch $2n$ the last visit to the origin occurs at epoch $2k$ is given by \begin{align*} \alpha_{2k,2n}=\frac{1}{4^n}\binom{2k}{k}\binom{2n-2k}{n-k} \end{align*} Since according to Stirling's formula \begin{align*} \binom{2k}{k}\sim \frac{1}{\sqrt{\pi k}} \end{align*} it can be shown that for fixed $0<x<1$ and $n$ sufficiently large \begin{align*} \sum_{k<xn}\alpha_{2k,2n}\approx \frac{2}{\pi}\arcsin \sqrt{x} \end{align*}

Other metrics are the number of changes of sign (more heads than tails or vice versa), first passages and returns to the origin, the equidistribution of heads and tails, etc. Chapter III by W. Feller provides a thorough introduction.

Answer 2

Familiar testing and confidence interval methods have been used to check whether a process is fair, producing equal numbers of Heads and Tails. Perhaps this discussion has reached the point were it is worthwhile to look separately at some methods to check whether a process produces Heads and Tails independently from trial to trial.

Independent Process. Roughly speaking, Markov chains may have one-step dependence, in which the next step depends (at most) on the current one. First, we look at a chain in which the steps are purely independent. You can think of it as successive tosses of an unfair coin in which $P(Heads) = \theta = 1/3$ (designated pp for population proportion in the R code below).

We make the following four plots of this elementary process:

• Bar chart showing 0s (Tails) and 1s (Heads),

• Trace showing convergence of cumulative means of Head counts to 1/3

• History plot showing the value (H =1, T=0), for the first few steps.

• ACF (autocorrelation function) plot

.

set.seed(123)
m = 10000;  n = 1:m;  pp = 1/3;  x = rbinom(m, 1, pp)
s.x = cumsum(x);  t.x = s.x/n
par(mfrow=c(2,2)); RLE = rle(sort(x))
  barplot(RLE$lengths/m, names=c("0=Tail", "1=Heads"), main="Barchart")
  plot(t.x, type="l", lwd=2, ylim=c(0,1), main="Trace")
     abline(h=pp, col="green")
  plot(1:100, x[1:100], type="s", main="History")
  acf(x, ylim=c(-.1,.1), main="ACF Plot")
par(mfrow=c(1,1))

Roughly speaking, the ACF plot is found by looking at correlations of 'lags':

lag $0:$ $(X_1, X_2, \dots, X_m)$ vs $(X_1, X_2, \dots, X_m),$ for which the correlation is always $r = 1)$; lag $1:$ $(X_2, X_3, \dots, X_m)$ vs $(X_1, X_2, \dots X_{m–1});$ lag $2:$ $(X_3, X_4, \dots, X_m)$ vs $(X_1, X_2, \dots, X_{m–2});$ and so on. (Actually, in finding all correlations, the sample mean and variance of all $m$ observations are used.)

In the four plots above: (i) The Barchart shows there are about $1/3$ Heads. (ii) The Trace shows that the cumulative proportion approaches $1/3$ according to the Law of Large Numbers. (iii) The History plot shows cycles: a cycle from $0$ to $1$ and back to $0$ takes $1/\theta + 1/(1 – \theta) = 3 + 3/2 = 4.5$ steps on average. (iv) The ACF plot For this independent process shows that only about $5\%$ of lagged correlations $r$ lie outside the confidence band (blue dotted lines).

Dependent Process. Now we show a dependent process that roughly models the rainy season of a so-called Mediterranean Climate. Rainly days (1) follow sunny days (0) with probability $\alpha =0.1,$ and sunny days follow rainy ones with probability $\beta = 0.2.$

set.seed(1237);  m = 10000;  w = numeric(m);  n = 1:m
alpha = 0.1;  beta = 0.2  # weather change probabilities
w[1] = 0                  # start with a sunny day
for (i in 2:m)  {
   if (w[i-1]==0)  w[i] = rbinom(1, 1, alpha)
   else            w[i] = rbinom(1, 1, 1 - beta)  }
s.w = cumsum(w);  t.w = s.w/n
par(mfrow=c(2,2));  RLE = rle(sort(w))
 barplot(RLE$lengths/m, names=c("0=Sun", "1=Rain"), main="Barchart")
 plot(t.w, type="l", lwd=2, ylim=c(0,1), xlab="Day", main="Trace")
  abline(h=alpha/(alpha+beta), col="green")
 plot(1:100, w[1:100], type="s", xlab="First 100 Days", main="History")
 acf(w, ylim=c(-.1,1), main="ACF Plot")
par(mfrow=c(1,1))

Here: (i) The Barchart shows About $\alpha/(\alpha + \beta) = 1/3$ Rainy days. (ii) The Trace shows the cumulative proportion of Rainy day approaches $1/3.$ (iii) The History plot show longer cycles than in the independent process. One cycle: from Sunny to Rainy and back takes $1/\alpha + 1/\beta =$ $10 + 5 = 15$ days on average. (iv) The ACF plot shows that dependence on the current day's weather "wears off" after about 10-12 days. But autocorrelation for the first few lags is significantly positive.