[lutusp]

Here's my proof that we will never prove the existence of true randomness.

* To demonstrate the randomness of the members of a set, we must examine the entire set.

* A candidate set cannot be finite in size, because a finite set is by definition not random.

* Therefore the only legitimate test of randomness is against an infinite set.

* To examine all the members of an infinite set would require infinite time.

This doesn't mean randomness doesn't exist, it only addresses the issue of proof.

[mappu]

Why is a finite set not random? What if it's a random selection from the set of all sets?

[lutusp]

> Why is a finite set not random?

First, for a given finite set, one cannot say it's not random, only that its randomness cannot be proven.

Let's think a bit about what we mean by "random".

* Is an even distribution of the digits 0-9, and no preferred sequential order, evidence for randomness? Yes, but not very good evidence.

* How about sequences of digits taken two at a time -- if each pair of digits is equally likely and shows no discernible pattern in their order, then we can say that the set meets the twin test.

* Now to triplets -- does each set of three digits show a complete absence of pattern, i.e. are 000, 001, etc. equally likely and have no preferred ordering?

Do you see where this is going? For any finite set size, the randomness tests must end when the digit sequence size to be tested equals the set's finite size. That means we cannot fully test the set, and the reason is that it's finite in size.

> What if it's a random selection from the set of all sets?

Well,

* Typical examples drawn from an infinite random set won't themselves be provably random. Consider if we draw three digits from an infinite, random set -- they won't be likely to be random in isolation. Extend this to a selection of N digits from an infinite, random set -- as N increases, the probability of the selected set being random increases, but cannot be truly, provably random for any finite value of N.

* A random selection isn't the same as a random set. If I randomly select a location within an infinite set, I have no assurance that my random choice of N digits will itself prove to be be random, therefore my having chosen a random starting point doesn't either aid or hinder the process.

Consider these seeming paradoxes (not really paradoxical):

* Within an infinite random set, there will be an infinite number of examples (and repetitions) of infinitely repeating digits, i.e. infinite sequences of 1111 ... , 2222 ..., etc. In fact, if we accept the premise that the infinite set is in fact random, such repeating sequences must exist somewhere in the set, or the set is not random.

* Within an infinite random set, with appropriate search tools, we will find every book ever written or to be written, every state secret, every mathematical equation ever written or to be written, essentially everything. It's a simple matter of knowing where to look.

Given these examples, if we choose an arbitrary index within the infinite random set from which to extract 40,000 numbers in base 26, we cannot be sure the extract will not be a work of Shakespeare with every word spelled correctly. Obviously that's not a random subset. Therefore we cannot have any assurance that a subset of a random set is itself random.

Consider the infinite sequence represented by the digits of Pi. If we examine the digits of Pi expressed in base 26, where A = 0, B = 1, etc., it should be obvious that we will begin to see dictionary words of increasing size rather quickly in a practical search using present-day tools. To get a work of Shakespeare, one need only search more deeply.

[mappu]

Thanks for your answer!

You mean consecutive n-tuples, right? If you're checking every permutation of n-tuples in the set, it's equivalent to checking single indices.

I see what you're getting at, but i'm not sure i can accept it as-is - the result is pretty closely tied to your particular choice of a randomness-test, which predetermines several of the later examples. My concept of "random" would not be strictly based on comparing n-tuples, but more about 'unpredictability' - so how about a randomness test based on kolmogorov complexity? Although i expect that finding the shortest possible algorithm that describe a set must be NP, if possible at all (that consecutive n-tuple comparison algorithm certainly isn't guaranteed to find it).

[lutusp]

> Although i expect that finding the shortest possible algorithm that describe a set must be NP, if possible at all (that consecutive n-tuple comparison algorithm certainly isn't guaranteed to find it).

Okay, you've mentioned Kolmogorov complexity, that's a reasonable approach. In that definition, a function able to produce random numbers is not (cannot be) smaller than the resulting set, i.e. it has maximum entropy. The reason is that a function that is smaller than its result implies that a pattern is being exploited, and that, in turn, implies that the set isn't random (such a set by definition would have no exploitable patterns).

Another test, based on the same ideas, is a hypothetical compression algorithm, not one that we know of or can write, that is put to the task of compressing the "random" set. If the compression algorithm cannot make the set smaller, the set is random. This also addresses the issue of exploitable patterns and entropy.

But all these ways of thinking about randomness relies on the set being infinite in size (or an inexhaustible function as a source for the test values). If this condition isn't met, and if we acquire a finite set of numbers of size N, one can argue that the next set of that size will be a repetition of the same values, therefore not random. This objection can only be answered by defining the problem in terms of an infinite set.

[mappu]

That last paragraph sums it up pretty well. You're obviously correct, an inexhaustible function = infinite set is required.

Thanks!