29-08-2003, 22:23 #1 Syth Registered User     Join Date: Apr 2003 Location: Dublino! Posts: 1,859 Randomness 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?
 30-08-2003, 22:50 #2 smiles purplized     Join Date: Aug 2000 Location: Ireland Posts: 2,611 http://mathworld.wolfram.com/RandomNumber.html is an interesting read. << Fio >>
 02-09-2003, 22:07 #3 Capt'n Midnight 00:00     Join Date: Mar 2003 Posts: 40,611 ramdom thoughts 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
03-09-2003, 20:09   #4
Syth
Registered User

Join Date: Apr 2003
Location: Dublino!
Posts: 1,859
Quote:
 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...

 13-09-2003, 23:10 #5 Dalamar Registered User   Join Date: Jul 2002 Location: Slacker central Posts: 178 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.
 14-09-2003, 19:57 #6 Capt'n Midnight 00:00     Join Date: Mar 2003 Posts: 40,611 You can use statistics to measure randomness If there is any correlation between the numbers then they are not random.
 14-09-2003, 22:11 #7 silverside Registered User     Join Date: Dec 2002 Posts: 1,362 not as simple as that 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.
15-09-2003, 17:03   #8
Syth
Registered User

Join Date: Apr 2003
Location: Dublino!
Posts: 1,859
Quote:
 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?

 15-09-2003, 17:13 #9 Thanx 4 The Fish Great gooogly moooogly     Join Date: Mar 2001 Location: Engerland Posts: 10,629 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.
 15-09-2003, 17:13 #10 mr_angry Registered User     Join Date: Jun 2003 Location: Rolling off your tongue, like a brick Posts: 3,248 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.
15-09-2003, 18:38   #11
ecksor
Puppy Shotgun

Join Date: Apr 2000
Location: Seattle
Posts: 10,090
Quote:
 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).

 15-09-2003, 19:27 #12 Syth Registered User     Join Date: Apr 2003 Location: Dublino! Posts: 1,859 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...
16-09-2003, 19:18   #13
ecksor
Puppy Shotgun

Join Date: Apr 2000
Location: Seattle
Posts: 10,090
Quote:
 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.

 17-09-2003, 22:08 #14 Capt'n Midnight 00:00     Join Date: Mar 2003 Posts: 40,611 http://csrc.nist.gov/rng/rng9.html - Tests for randomness in bit streams http://www.jesus.ox.ac.uk/~clifford/a5/chap1/node2.html