Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

An Algorithm/Turing machine Produces a symbol from a finite alphabet, and continues doing so
infinitely.

Another algorithm gets a copy of this symbol, Can this algorithm be so designed that it can tell weather the sequence
being generated is random.

My question in general is how does one define a "Random sequence" if we can define such a sequence at all

share|improve this question
2  
Clearly the algorithm cannot tell in finite time whether the sequence being generated "is random", at least not with probability of success 1. But also, if a Turing machine is producing the sequence of symbols, then isn't this sequence already known to be non-random? –  Sam Hopkins Jun 8 '13 at 18:44
1  
A start would be to look up Martin-L\"of randomness. en.wikipedia.org/wiki/Algorithmically_random_sequence –  John Engbers Jun 8 '13 at 19:14
2  
I agree with the second part of Sam Hopkins's comment. It's easy to tell whether the sequence of symbols produced by an algorithm is random; just say "no". –  Andreas Blass Jun 8 '13 at 19:31
    
.. and suppose that an interpretor is privy to the sequence and not the algorithm which generates it... So does the definition of a random infinite sequence depend on the fact of one knowing the algorithm which generates it. –  ARi Jun 9 '13 at 5:55

1 Answer 1

up vote 4 down vote accepted

This of course depends on your definition of "random".

Is 12345678901011121314151617181920212223... random (notice the pattern)? This depends on what properties you want a random string of symbols to have. For some normality is enough. The above sequence is normal in base 10 for example, but it has a pattern, so maybe we will say it is not random.

Hence, we would like to consider even more statistical properties that a random string should have. For example it should satisfy the law of the iterated logarithm.

If we take this too the extreme, we could require that a random string satisfies all probability one properties. However, this is too strong. One of those properties is that this string can't be $x$, where $x$ is the sting in question. So in this sense there are no random strings.

Nonetheless, there is a way to take a step back and consider only those strings which pass all "computable statistical tests". Such a sequence is called "algorithmically random". This is not a well-defined term until one clarifies what they mean by "computable statistical test". The two most common such notions of algorithmic randomness are Schnorr randomness and Martin-Löf randomness.

Both of these notions require (among much stronger properties) that the string is not computable. Hence a string outputed by a deterministic Turing machine cannot be, say, Martin-Löf random. Also, it is not possible to determine in a finite number of steps if a string is random. For example, consider a string that starts with a large number of 0's and then behaves randomly. This should still be random because maybe you got a little lucky.

This "luck factor" can be quantized as the randomness deficiency of the string. More formally it is the maximum (over numbers $n$) of $n - K(x \upharpoonright n)$ where $K(x \upharpoonright n)$ is the Kolmogorov complexity of the first $n$ digits of the 0-1 string $x$. A Martin-Löf random string $x$ is one with finite randomness deficiency (so you were not infinitely lucky).

If one wants to check for sequences that have just really high randomness deficiency (say over 1000), this is semi-computable, that is one can determine when a string has high deficiency (very likely not random), but not necessarily determine when it has low deficiency. Just wait until one finds an initial segment of $x$ with low Kolmogorov complexity.

Schnorr randomness also has a notion of randomness deficiency, but it is not as clearly defined and depends on a particular statistical property being tested. It however has the advantage that there is an algorithm which computes the randomness deficiency of all strings with a small chance of error.

There is a whole subject devoted to algorithmic randomness, including two books:

  • Algorithmic randomness and complexity by Downey and Hirschfelt
  • Computability and randomness by Nies
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.