How can I determine which of two sequences of coin flips is real and which is fake? This is an interesting problem I came across. I'm attempting to write a Python program to get a solution to it; however, I'm not sure how to proceed. So far, I know that I would expect the counts of heads to follow a binomial, and length of runs (of tails, heads, or both) to follow a geometric.

Below are two sequences of 300 “coin flips” (H for heads, T for
tails). One of these is a true sequence of 300 independent flips of a
fair coin. The other was generated by a person typing out H’s and T’s
and trying to seem random. Which sequence is truly composed of coin
flips?
Sequence 1:
TTHHTHTTHTTTHTTTHTTTHTTHTHHTHHTHTHHTTTHHTHTHTTHTHH
TTHTHHTHTTTHHTTHHTTHHHTHHTHTTHTHTTHHTHHHTTHTHTTTHH
TTHTHTHTHTHTTHTHTHHHTTHTHTHHTHHHTHTHTTHTTHHTHTHTHT
THHTTHTHTTHHHTHTHTHTTHTTHHTTHTHHTHHHTTHHTHTTHTHTHT
HTHTHTHHHTHTHTHTHHTHHTHTHTTHTTTHHTHTTTHTHHTHHHHTTT
HHTHTHTHTHHHTTHHTHTTTHTHHTHTHTHHTHTTHTTHTHHTHTHTTT
Sequence 2:
HTHHHTHTTHHTTTTTTTTHHHTTTHHTTTTHHTTHHHTTHTHTTTTTTH
THTTTTHHHHTHTHTTHTTTHTTHTTTTHTHHTHHHHTTTTTHHHHTHHH
TTTTHTHTTHHHHTHHHHHHHHTTHHTHHTHHHHHHHTTHTHTTTHHTTT
THTHHTTHTTHTHTHTTHHHHHTTHTTTHTHTHHTTTTHTTTTTHHTHTH
HHHTTTTHTHHHTHHTHTHTHTHHHTHTTHHHTHHHHHHTHHHTHTTTHH
HTTTHHTHTTHHTHHHTHTTHTTHTTTHHTHTHTTTTHTHTHTTHTHTHT
Both sequences have 148 heads, two
less than the expected number for a 0.5 probability of heads.


This is a class activity I've first read about in the book Teaching Statistics. A Bag of Tricks, 2nd ed. by Andrew Gelman and Deborah Nolan (they recommend 100 flips, though). Their reasoning to detect the fabricated sequence is based on the combination of the longest run and the number of runs. For the following plot, I simulated 5000 fair coin tosses of length 300 and plotted the longest run on the y-axis and the number of runs on the x-axis (I once asked a question about the explicit joint probability). Each dot represents the result of 300 fair flips. For better visibility, the points are jittered. The numbers for the two sequences are plotted in color. The conclusion is obvious.

For a quick calculation, recall that a rule of thumb for the longest run of either heads or tails in $n$ tosses is$^{[1]}$ $l = \log_{1/p}(n(1-p)) + 1$. For an approximate 95% prediction interval, just add and subtract $3$ from this value. Surprisingly, this number (i.e. $\pm 3$) does not depend on $n$! Applied to a fair coin with $n=300, p=1/2$, we have $l=\log_2(300/2) + 1=8.22$. So we expect the longest run to be round $8$ and reasonably in the range of $8\pm 3$, so between $5$ and $11$. The longest run in sequence 2 is $8$, whereas it is $4$ in sequence 1. As this is outside the approximate prediction interval, we'd conclude that sequence 1 is suspicious under the assumption of $p=1/2$.
$[1]$ Schilling MF (2012): The Surprising Predictability of Long Runs. Math. Mag. 85: 141-149. (link)
