# How do we check Randomness? [duplicate]

Let's imagine a guy who claims to possess a machine that can each time produce a completely random series of 0/1 digits (e.g. $1,0,0,1,1,0,1,1,1,...$). And each time after he generates one, you can keep asking him for the $n$-th digit and he will tell you accordingly.

Then how do you check if his series is really completely random?

If we only check whether the $n$-th digit is evenly distributed, then he can cheat using:

$0,0,0,0,...$
$1,1,1,1,...$
$0,0,0,0,...$
$1,1,1,1,...$
$...$

If we check whether any given sequence is distributed evenly, then he can cheat using:

$(0,)(1,)(0,0,)(0,1,)(1,0,)(1,1,)(0,0,0,)(0,0,1,)...$
$(1,)(0,)(1,1,)(1,0,)(0,1,)(0,0,)(1,1,1,)(1,1,0,)...$
$...$

I may give other possible checking processes but as far as I can list, each of them has flaws that can be cheated with a prepared regular series.

How do we check if a series is really random? Or is randomness a philosophical concept that can not be easily defined in Mathematics?

• "...is randomness a philosophical concept that can not be easily defined in Mathematics?" - pretty much. However we do want our (pseudo)random sequences to pass certain tests... – J. M. isn't a mathematician Oct 23 '11 at 5:17
• Any particular set of tests can be cheated if you know what is. For theoretical cryptography purposes, one can define a bit generator as random if it passes "all tests that run in a reasonable time". More precisely, a proposed random bit generator is $(n,t,\epsilon)$-random if, given the first $n$ bits of the sequence, there is no randomized algorithm that runs within time $t$ and successfully predicts the next bit with probability outside the range $1/2 \pm \epsilon$. – Ted Oct 23 '11 at 7:36
• Interesting. So ... "irrationality", since it cannot be confirmed by looking at a finite number of decimals in a number, is a philosophical concept that cannot be easily defined in mathamatics ?? "Continuity", since it cannot be confirmed by a finite number of function evaluations is a philosophical concept that cannot be easily defined in mathamatics. – GEdgar Oct 26 '11 at 13:20