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.


Here's an empirical approach, based on compression as a proxy for algorithmic complexity:
import bz2
import random
import statistics

s1 = "TTHHTHTTHTTTHTTTHTTTHTTHTHHTHHTHTHHTTTHHTHTHTTHTHHTTHTHHTHTTTHHTTHHTTHHHTHHTHTTHTHTTHHTHHHTTHTHTTTHHTTHTHTHTHTHTTHTHTHHHTTHTHTHHTHHHTHTHTTHTTHHTHTHTHTTHHTTHTHTTHHHTHTHTHTTHTTHHTTHTHHTHHHTTHHTHTTHTHTHTHTHTHTHHHTHTHTHTHHTHHTHTHTTHTTTHHTHTTTHTHHTHHHHTTTHHTHTHTHTHHHTTHHTHTTTHTHHTHTHTHHTHTTHTTHTHHTHTHTTT"
s2 = "HTHHHTHTTHHTTTTTTTTHHHTTTHHTTTTHHTTHHHTTHTHTTTTTTHTHTTTTHHHHTHTHTTHTTTHTTHTTTTHTHHTHHHHTTTTTHHHHTHHHTTTTHTHTTHHHHTHHHHHHHHTTHHTHHTHHHHHHHTTHTHTTTHHTTTTHTHHTTHTTHTHTHTTHHHHHTTHTTTHTHTHHTTTTHTTTTTHHTHTHHHHTTTTHTHHHTHHTHTHTHTHHHTHTTHHHTHHHHHHTHHHTHTTTHHHTTTHHTHTTHHTHHHTHTTHTTHTTTHHTHTHTTTTHTHTHTTHTHTHT"

def compressed_len(s):
    return len(bz2.compress(s.encode()))

trials = []
for x in range(100000):
    sr = "".join(random.choice("HT") for _ in range(300))
    trials.append(compressed_len(sr))

mean = statistics.mean(trials)
stddev = statistics.stdev(trials)

print("Random trials:")
print("Mean:", mean)
print("Stddev:", stddev)

l1 = compressed_len(s1)
l2 = compressed_len(s2)

o1 = l1 - mean
o2 = l2 - mean

d1 = o1 / stddev
d2 = o2 / stddev

print("Selected trials:")
print("Seq", "Len", "Dev", sep="\t")
print("S1", l1, d1, sep="\t")
print("S2", l2, d2, sep="\t")


Roughly speaking:

*

*Compress a bunch (100k) of random coinflips.

*Observe the resulting length distribution. (In this case I'm approximating it as a normal distribution of lengths; a more thorough analysis would check and pick an appropriate distribution instead of blithely assuming normality.)

*Compress the input sequences.

*Compare with observed distribution.

Result (note: not exactly reproducible due to the use of random trials; if you want to be reproducible add a random seed):
Random trials:
Mean: 105.05893
Stddev: 2.6729774976956002
Selected trials:
Seq Len Dev
S1  88  -6.381995364609942
S2  109 1.4744119632124217

Based on this, I'd say that S1 is the non-random one here. 6.38 standard deviations below the mean is rather improbable.

The nice thing about this approach is that it's relatively generic, and takes advantage of the pre-existing work of a bunch of smart people.
Just be aware of its limitations and quirks:

*

*You want a compression algorithm that's designed for space over compression speed. BZ2 works well enough here.

*This doesn't work if the compression algorithm simply gives up and writes a raw block to the output.

*A null result does not mean that the sequence is random. It means that this compression algorithm is unable to distinguish this input from random.

