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?

  • 1
    "...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](http://www.stat.fsu.edu/pub/diehard/)...2011-10-23
  • 1
    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$.2011-10-23
  • 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