8
$\begingroup$

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?

  • 0
    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*.2011-10-26

3 Answers 3

5

All the sequences you mentioned have a really low Kolmogorov complexity, because you can easily describe them in really short space. A random sequence (as per the usual definition) has a high Kolmogorov complexity, which means there is no instructions shorter then the string itself that can describe or reproduce the string. Ofcourse the length of the description depends on the formal system (language) you use to describe it, but if the length of the string is much longer then the axioms of your formal systems, then the Kolmogorov-complexity of a random string becomes independent of your choice of system.

Luckily, under the Church-Turing thesis, there is only 1 model of computation,(unless your machine uses yet undiscovered physical laws), so there is only 1 language your machine can speak that we have to check.

So to test if a string is random, we only have to brute-force check the length of the shortest Turing-program that outputs the first n bits correctly. If the length eventually becomes proportional to n, then we can be fairly certain we have a random sequence, but to be 100% we have to check the whole (infinite) string. (As per definition of random).

3

Leaving aside the theoretical aspect of your question, there are also pragmatic answers to it because there are real world uses for high-quality random generators (whether hardware or algorithmic). For statistical uses, "statistical randomness" is a used. For example you can use these "diehard tests" or TestU01.

2

This is discussed very nicely in Volume 2 of Knuth's The Art Of Computer Programming. The executive summary is that randomness is a mathematical concept that can be defined in mathematics but not easily.