How to check if a sequence is random?

Question

When I was thinking about various types of pseudo-randomness, the following question struck me:

Suppose that a sequence $a_n \in \{0,1\}$ is given. Is there a way to check if it is genuinely random?

More concretely, suppose that we know in advance that $a_n$ are either:

1. all chosen at random, according to the same distribution, and indenpendently, or
2. produced by some, unknown, algorithm (i.e. there exists a deterministic Turing machine which, given $n$ as input produces $a_n$ on output.)

Assume additionally that the distribution is not too close to degenerate (say, $.001 < Pr(a_n = 1) <.999$).

Does there exist an algorithm which gets the (infinite) sequence $a_n$ on input (i.e. is given access to a ``black box'' which produces $a_n$ given $n$) such that:

1. if the sequence $a_n$ is random, then the algorithm keeps going indefinitely with probability $>1 - \varepsilon$,
2. if the sequence is deterministic, the algorithm outputs YES in finite time, always.

Note that the restriction that the distribution is not too degenerate is necessary, else in 2. we don't know when to output YES for the constant sequence $0,0,0\dots$. Also, obviously, in 2. there is no hope of determining the Turing machine which produces $a_n$. The question only makes sense if the sequence $a_n$ is infinite, else every sequence is deterministic (as pointed out in the comments).

There is a related question, but it asks for practical test. What I am interested in is what the situation is ``in principle''. It seems to me that such algorithm should exist, but I am wondering if I am missing something.

Answer 1

I think you're essentially uncovering the foundations of algorithmic randomness.

The question is extremely related to Kolmogorov Complexity (which is at the basis of that field); intuitively, if any finite prefix of the sequence has small Kolmogorov complexity, then at least that part of the sequence is not very random.

This also leads to the answer being basically "no", we cannot check if the sequence is random, because Kolmogorov complexity is incomputable. So even checking whether a finite-length string is random is incomputable. Intuitively, it's very closely related to the halting problem and computing busy-beaver numbers.

Answer 2

No, you can't. There are many tests for randomness: having roughly half the bits be zero, having the right number of strings of $0$'s of various lengths, having the right proportion of each eight bit chunk, etc. If you search for "randomness test" you can read about many of them. Generally they can prove a string is not random (at a certain confidence level), but not that it is random. For example, suppose I gave you the string created by XORing the strings of $e$ starting from the millionth bit and $pi$ starting from the billionth. We would expect this string to pass all the statistical tests you might try, but it has a very simple rule behind it. Unless you recognize the string somehow, you are unlikely to figure out the rule.