Randomness

Syth

Just wondering about randomness and other posters ideas on it.

Here are some of my thouhts on randomness, for all this I'll be using a 'random' distribution of points on the real number line between 0 and 1:

Can we actaully define what randomness is? Or is all we can do is define many types of order and say if it doesn't fit then it's random? I don't really like this idea because what if there are an infinte number of types of order, then somethings random today mite wind up to be ordered tomorrow.

Can there be degrees of randomness or is it absolute? If there were infinite number of orders then this wouldn't happen...

If there were infinite number of orders then could you have randomness?

Any other randomness thoughts?

smiles

http://mathworld.wolfram.com/RandomNumber.html is an interesting read.

<< Fio >>

Capt'n Midnight

there has at one time existed a book containing a million random digits in the DCU library (it's a big one)

the digits of PI meet all tests for randomness and can be downloaded from guttenberg

gaussian distribution AFAIK the cube of random numbers produces a bell curve

you can't procduce truly random numbers from a digital proces - it depends on the initial seed number - hence need real randomness eg: - wind noise (cosmic noise or radioactive decay are good too - but water dripping through cracks is easier)

in a random walk after n moves you will be square root of n distance away from where you started (on average)

If it has ANY order then it is not random
eg: prime numbers are not predictable - but they are not random

look up the monte carlo method you feed large sets of random points into an equation and

Syth

meet all tests for randomness

Ah but what are the 'tests for randomness'? Can we know all tests for randomness? Etc Etc

Hmm quite metaphysical/philosopical for me... still...

Dalamar

If the numbers are truly random, there is no way to predict the next number in a squence, no matter how many numbers you've gotten before.

So, if you analysed the frequency of numbers in first million digits of Pi, you can't guess with any certainity the 1,000,001th number.

It is difficult to construct a test to prove a number is random though.

Capt'n Midnight

You can use statistics to measure randomness

If there is any correlation between the numbers then they are not random.

silverside

e.g. if you roll a red die and a green die at the same time. The number shown on the red die is correlated with the total shown on both dice, even though both are random.

Similarly for any series of random variables, (e.g. time series such as weather), they can be broken down into a random part and an expected change, even though there is some correlation between the values from one time period to the next.

Syth

If the numbers are truly random, there is no way to predict the next number in a squence

So is randomness just what you have if you can't show that it's ordered, ie to test for randomness do you test all the types of orderedness and then when nopthing (you know) fits, is it declared random? If so, you have to possibility of something being random today, and ordered tomorrow if someone discovers a new type of order. This could happen to all sequences that are 'random', so there might actually be no random sequences at all! It would be better if there was a test for randomness that wouldn't depend on testing for orderdness. Is there?

Thanx 4 The Fish

If there was a test for randomness then surely there would have to be some kind of order inherent in it wouldn't there. The test would have to be based on something which at the end of the day would be an order of some nature.

mr_angry

Any series can appear random when you are unaware of the structure behind it. Its all about perception really.

Take a look at James Gleich's "Chaos - Making A New Science ", if you're really interested.

ecksor

Originally posted by Thanx 4 The Fish If there was a test for randomness then surely there would have to be some kind of order inherent in it wouldn't there. The test would have to be based on something which at the end of the day would be an order of some nature.

I did some reading up on this, and the reading I came away with is that it reduces to order and complexity by specifying what exactly you mean by 'non-random' in terms of how much shorter the rule for generating the number is than the actual number itself (assume that you've figured out the most concise way to specify the rule or algorithm).

So, to take an example, if your criteria is that the rule must be 20 bits less than the number being generated, and you're looking for rules to generate 25 bit numbers, then you're looking at rules that consist of 5 bits, of which there are 2^5 (32). So, the maximum number of 25 bit numbers you can generate from 5 bit rules, is 32, which means that 2^20 of those numbers are essentially random. You can predict more numbers by allowing more complex rules. (Obviously, the more complex the rule, the less advantage there is in having the rule).

Syth

I've read Choas by Gleich. Damn fine book.

how much shorter the rule for generating the number is than the actual number itself
Isn't this more information theory than randomness? Is randomness part of inofrmation theory? I suppose it is in a way...

If there was a test for randomness then surely there would have to be some kind of order inherent in it wouldn't there
Can you explain this more, I don't really understand...

ecksor

Originally posted by Syth
Is randomness part of inofrmation theory? I suppose it is in a way...

I'm reading it more as complexity theory, and purely offering it as a way of measuring or defining 'how random'. Your original question was about how randomness relates to order. If you go down that route, then the scenario you painted seems to be a problem, so I'm trying to resolve that by showing that you can define how much confidence you need to have in the number being random (which may just be my perspective) by specifying what the bounds are for the complexity of the rule to generate it to try to get around the logical extremes that you offered earlier.

For example, this is potentially a nice way of thinking about how easy it is to subvert a cryptographic primitive (which may depend on arbitrary issues of complexity and not just randomness).

A truly random number won't have a rule that is shorter than the number you are trying to predict, because it is not deterministic and therefore the shortest rule is to just spit out the number.

Capt'n Midnight

http://csrc.nist.gov/rng/rng9.html - Tests for randomness in bit streams

http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node2.html