Per Martin-Löf and a definition of random sequences

2013 March 13

So I did a little googling, and came up with an interesting article on random sequences. The basic concept is that a sequence is not random if there exists some computable (recursively enumerable, or what's assumed to be the same "turing computable") statistical test that rejects the sequence but rejects "random" sequences at most 2^{-n} times for any n sufficiently smaller than the length of the sequence.

In other words, if we come up with some computable test based on intuition about what randomness should mean which rejects "truly random" sequences very rarely, then those accepted by the test should be considered truly random. Then he shows that we can assume that there is a "universal test" even if we don't know what it is. Finding such a universal test is basically equivalent to computing the Kolmogorov complexity, so it's not possible to say what the test is  (even though the test itself would be computable).

This is nice because together with some other basic Kolmogorov complexity results, it seems that we can assume that for any finite length n there exists a "random" sequence of that length, by transfer we'd get that there exists a nonstandard length random sequence. So there is a random generator of real numbers \xi(n). I'll have to look at some of the additional research to see if someone's already proved in what sense such a thing is uniform.


Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS