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 problem specifies that we have the following information:

*

*We observed two coin flip sequences: sequence $S_1$ and sequence $S_2$.

*Each of these sequences could have been generated by either mechanism $R$ corresponding to independent flips of a fair coin or some other mechanism $\bar{R}$.

*Exactly one of these two sequences was generated by the mechanism $R$.

Since both sequences $S_1$ and $S_2$ could possibly have been generated by $R$ or $\bar{R}$, we cannot be sure which of these two sequences was generated by $R$. However, probability theory provides us with the tools to quantify our belief $P(R_i|S_i)$ that sequence $S_i$ was generated by mechanism $R$. Then, given that we have been provided with the information $I$ that exactly one of these two sequences has been generated by mechanism $R$, then the probability that sequence 1 was generated by mechanism $\bar{R}$ and sequence 2 was generated by mechanism $R$ is:
$$
P(\bar{R_1}R_2|S_1 S_2 I) = \frac{P(R_2|S_2)}{P(R_1|S_1) + P(R_2|S_2)}
$$
This problem explicitly specifies what it means for a sequence to have been generated by mechanism $R$: the sequence $S_i$ is described by independent flips $y_{ij}$ of a fair coin, such that the likelihood is:
$$
P(S_i|R_i) = \prod_j \mathrm{Bernoulli}(y_{ij} | 0.5)
$$
However, in order to determine the probability that a given sequence was generated by mechanism $R$, $P(R_i|S_i)$, we also need to specify alternative mechanisms $\bar{R}$ by which the sequences may have been generated. At this point we have to use our own creativity and external information to develop models that could reasonably describe how these sequences might have been generated, if they were not generated by mechanism $R$.
The other answers to this question do a great job at describing various mechanisms $\bar{R}$ that describe how sequences could be generated:

*

*Sequences are generated by sampling pairs of coin flips from a distribution where the probability of different pairs of coin flips deviates from uniform: 1 2 3

*Sequences are generated in a way such that they do not have long runs of only heads or tails: 1

*Sequences are generated in such a way so that a given compression algorithm results in a small compressed size: 1

*Sequences are generated by a random walk such that a given coin flip outcome is affected by recent coin flip outcomes: 1 2 3
Note: we can always develop a hypothesis that appears to result in our observed sequence having been "inevitable", according to our likelihood, and if our prior probability for that mechanism of sequence generation is high enough, then using this hypothesis can always result in a low probability that the sequence had been generated by mechanism $R$. This practice is also referred to as HARKing, and Jaynes refers to this as a "sure-thing hypothesis". In general, we may have multiple hypotheses that can describe how a sequence may be generated, but the more contrived hypotheses such as "sure-thing hypotheses" should generally have sufficiently low prior probabilities such that we generally would not infer that those hypotheses have the highest probability of having generated a given sequence.
Here's an example using this procedure with one possible model for $\bar{R}$ sequence generation to quantify the probability that sequence 2 was the sequence that was generated by mechanism $R$. This stan model defines model_r_lpmf as the log likelihood for sequence generation mechanism $R$, and model_not_r_lpmf as the log likelihood for sequence generation mechanism $\bar{R}$. In this case, we are testing a hypothesis $\bar{R}$ in which coin flips can be correlated, and there is a fairly well defined correlation length. Then, we are modeling the probability that the sequence was generated by model $R$ as p_model_r, such that our prior probability considers mechanisms $R$ and $\bar{R}$ sequence generation equally probable.
// model for hypothesis testing whether a sequence of coin flips is generated by either:
// - model R: independent flips of a fair coin, or
// - model not R: unfair coin with correlations

functions {
  // independent flips of a fair coin
  real model_r_lpmf(int[] sequence, int N) {
    return bernoulli_lpmf(sequence | 0.5);
  }

  // unfair coin with correlations
  real model_not_r_lpmf(int[] sequence, int N, int n, vector beta) {
    real tmp = 0;

    real offset = 0;
    for (i in 1:N) {
      offset = beta[1];
      for (j in 1:min(n - 1, i - 1)) {
          offset += beta[j + 1] * (2 * sequence[i - j] - 1);
      }
      tmp += bernoulli_logit_lpmf(sequence[i] | offset);
    }
    return tmp;
  }
}
data {
  int N;                                 // the length of the observed sequence
  int<lower=0, upper=1> sequence[N];     // the observed sequence
}
transformed data {
  int n = N / 2 + 1;                     // number of correlation parameters to model
}
parameters {
  real<lower=0, upper=1> p_model_r;       // probability that the sequence was generated by model R
  // not R model parameters
  real log_scale;                        // log of the scale of the correlation coefficients `beta`
  real log_decay_rate;                   // log of the decay rate for the correlation coefficients `beta`
  vector[n] alpha;                       // pretransformed correlation coefficients
}
transformed parameters {
  // transformed not R model parameters
  real scale = exp(log_scale);           // typical scale of the correlation coefficients
  real decay_rate = exp(log_decay_rate); // typical decay rate of correlation coefficients
  vector[n] beta;                        // correlation coefficients
  for (j in 1:n) {
    beta[j] = alpha[j] * scale * exp(-(j - 1) * decay_rate);
  }
}
model {
  // uninformative haldane prior for the probability that the sequence was generated by model R
  target += - log(p_model_r) - log1m(p_model_r);

  // priors for not R model parameters
  log_scale ~ normal(-1, 1);
  log_decay_rate ~ normal(-1, log(n + 1) / 2.0);
  alpha ~ normal(0, 1);

  // the sequence is was generated by model R with probability `p_model_r`, otherwise it was generated by model not R
  target += log_mix(
    p_model_r,
    model_r_lpmf(sequence | N),
    model_not_r_lpmf(sequence | N, n, beta)
  );
}

Using pystan with this model, we can evaluate the probability p_model_r that each of the two provided sequences were generated by mechanism $R$.
model = pystan.StanModel(model_code=MODEL_CODE)

sequence_1 = "TTHHTHTTHTTTHTTTHTTTHTTHTHHTHHTHTHHTTTHHTHTHTTHTHHTTHTHHTHTTTHHTTHHTTHHHTHHTHTTHTHTTHHTHHHTTHTHTTTHHTTHTHTHTHTHTTHTHTHHHTTHTHTHHTHHHTHTHTTHTTHHTHTHTHTTHHTTHTHTTHHHTHTHTHTTHTTHHTTHTHHTHHHTTHHTHTTHTHTHTHTHTHTHHHTHTHTHTHHTHHTHTHTTHTTTHHTHTTTHTHHTHHHHTTTHHTHTHTHTHHHTTHHTHTTTHTHHTHTHTHHTHTTHTTHTHHTHTHTTT"
samples_1 = model.sampling(
    data=dict(N=len(sequence_1), sequence=[int(c == "H") for c in sequence_1]),
    chains=16,
)
p_model_r_1 = samples_1["p_model_r"].mean()
# p_model_r_1 = 0.027

sequence_2 = "HTHHHTHTTHHTTTTTTTTHHHTTTHHTTTTHHTTHHHTTHTHTTTTTTHTHTTTTHHHHTHTHTTHTTTHTTHTTTTHTHHTHHHHTTTTTHHHHTHHHTTTTHTHTTHHHHTHHHHHHHHTTHHTHHTHHHHHHHTTHTHTTTHHTTTTHTHHTTHTTHTHTHTTHHHHHTTHTTTHTHTHHTTTTHTTTTTHHTHTHHHHTTTTHTHHHTHHTHTHTHTHHHTHTTHHHTHHHHHHTHHHTHTTTHHHTTTHHTHTTHHTHHHTHTTHTTHTTTHHTHTHTTTTHTHTHTTHTHTHT"
samples_2 = model.sampling(
    data=dict(N=len(sequence_2), sequence=[int(c == "H") for c in sequence_2]),
    chains=16,
)
p_model_r_2 = samples_2["p_model_r"].mean()
# p_model_r_2 = 0.790

Here we have quantified the probability that each sequence was generated according to the sequence generating model $R$ as the following:
$$
\begin{aligned}
P(R_1|S_1) &= 0.027 \\
P(R_2|S_2) &= 0.790 \\
P(\bar{R_1}R_2|S_1 S_2 I) &= 0.967 \\
\end{aligned}
$$
So, we are fairly certain that sequence 2 was generated by independent coin flips and sequence 1 was not, relative to the model of sequence generation $\bar{R}$ that we defined, and we quantify this belief with a probability of 0.967. This is a high probability, but of course we could still be wrong -- both sequences could have been generated by either model. Additionally, we could have selected a model of sequence generation for $\bar{R}$ that can not describe the procedure that was actually used to generate the sequences. This process for quantifying our belief that one of these two sequences was generated by a fair coin with independent flips is the piece of reasoning that currently appears to be missing from the other answers that are currently available.
