# Randomness

• Jan 2nd 2006, 07:12 PM
ThePerfectHacker
Randomness
Something tells me I made a similar post before but I did not find it.
What is the rigorous mathematical definition of randomness? I was thinking like this: Assume you have an algorithm which produces numbers then we can define it as random if the limit of the correlation coefficient approaches zero as $n \rightarrow \infty$.
I am talking about concepts (probability and algorithms) which I have never studied thus you might not understand what I am trying to say. But I am trying to say for example an algorithm is defined in such a way it produces only one's. Then we can create a plot with the x-axis being the number of times the algorithm used and y-axis is its result output. Then by the correlation coefficient formula that coefficient is always one. Thus, the limit as increasing the number of times using the algorithm is 1 not zero thus that algorithm is not random. Does anyone understand what I am trying to ask?
CaptainBlack this is what you know best Computability Theory, help me.
• Jan 2nd 2006, 11:35 PM
rgep
One good definition is that of algorithmic incompressibility: a sequence of bits is incompressible if the size S(n) of the shortest computer program (Turing machine) which produces the first n bits satisfies S(n)/n -> 1: that is, you cannot write a shorter program than one which simply copies the bits from a file.
• Jan 3rd 2006, 02:59 PM
ThePerfectHacker
I have no idea what you just said. No need to explain it to me, just asking what you think about my definition?
• Jan 14th 2006, 01:29 PM
hpe
Quote:

Originally Posted by ThePerfectHacker
What is the rigorous mathematical definition of randomness? I was thinking like this: Assume you have an algorithm which produces numbers then we can define it as random ...

If you produce a sequence of numbers with an algorithm, that sequence is not random.
• Jan 14th 2006, 01:48 PM
CaptainBlack
You might want to look at Gregory Chaitin's pages, lots of articles there
on this stuff. If you can you might as well consult the horses mouth :D

The most recent of these may be the best place to start, as it is pitched
at a semi-popular level.

RonL
• Jan 29th 2006, 07:01 PM
rabeldin
Rigorous definition of randomness
Guess what? There is no such thing! We postulate a space of possibilities and a subset of events and assign probabilities to them. Some people will say that a selection in accordance with those probabilities is a "random" selection, others will insist that only "equiprobable events" can provide random selection.

Actually, mathematicians don't discuss randomness very much. Probability measures, yes, randomness, no.
• Jan 29th 2006, 07:55 PM
SkanderH
A rigorous definition of randomness
I think that the only problem with PerfectHacker's definition is his use of the word algorithm.
Otherwise I think it is a good starting point to work form. It seems to me that some definition of the notion of onservation or measurment is necessary -consider quantum mechanics, where a physical process is completley non-random or deterministic (unitary evolution), until somebody decides to measure an observable of the system.

Any thoughts?