Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is randomness? Nobody knows..

johndcook.com

Post reply on HN
Print view View original

21–30 of 39 posts

Re: What is randomness? Nobody knows..

#21

Post by jasomill »

pierrebouchet wrote: post #17

I think one of the most widely accepted definitions of randomness in mathematics was given by Martin-Löf. Basically it says that a process is random iff it doesn't exhibit any atypical property that you can test with an algorithm. In other words: if there is no computable way of proving that it's not random, then it is random.

How does this not trivially exclude everything (the first definition, not the circular restatement)? Considering that, say, a sequence of coin flips either has the property of "beginning with heads" or "beginning with tails," it certainly appears to.

Re: What is randomness? Nobody knows..

#23

Post by MrJagil »

Mahh wrote: post #12
dsthysd wrote: post #5

Randomness is an equal chance that one of a number of events occur. Is he arguing that we do not know what randomness is? Or that we have not found anything truly random?

His discussion pertains to actual sources of randomness(not just the notion of randomness). Even randomness in our technology is generated from deterministic models. It's sort of strange -- Physics seems like it should be deterministic, so where could random possibly come from? If the Universe is deterministic, then shouldn't anything we observe that seems 'random' actually not random(including human thoughts!?!?)? E…

As an aspiring philosopher i love these thoughts! Thank you!

I have long thought that Chaos Theory is a vastly underestimated scientific field. They should teach it in elementary school!

Re: What is randomness? Nobody knows..

#24

Post by jasomill »

WiseWeasel wrote: post #20
pierrebouchet wrote: post #17

I think one of the most widely accepted definitions of randomness in mathematics was given by Martin-Löf. Basically it says that a process is random iff it doesn't exhibit any atypical property that you can test with an algorithm. In other words: if there is no computable way of proving that it's not random, then it is random.

In a practical sense, I'd say the definition is simply our inability to recognize a pattern at this point; it's completely subjective.

Lehmer (1951), by way of Knuth Vol. 2, "A random sequence is a vague notion embodying the idea of a sequence in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests, traditional with statisticians and depending somewhat on the uses to which the sequence is to be put."

Re: What is randomness? Nobody knows..

#25

Post by dexen »

powertower wrote: post #22

Randomness has at least one property... It can't be compressed. That is, it has no pattern.

For lack of a better idea, that's how I once tested a toy PRNG I programmed. Feed output to rzip, check compression level, tweak a few knobs till it compresses worst.

However, that's not a good guaranty of true randomness. Encrypted data (for decent encryption algorithms) has high entropy just as well, even if the plaintext is non-random.

On the other hand, if you have a truly random process with very low probability of occuring, its output would indeed compress well via, for example, RLE.

The property of not being compressable is about both entropy and uniform distribution. See also http://en.wikipedia.org/wiki/Randomness_extractor

Re: What is randomness? Nobody knows..

#26

Post by antirez »

I think there is very good, and at the same time trivial, definition of how much random something is.

Given any source of data, you define randomness the inverse of the ability of somebody observing the output sequence to guess what the next item will be.

For instance in a stream of random bytes the observer will not be able to guess with more probability than 1/256 what the next byte will be, but if the sequence is "ffaaffaaffaa..." it will be trivial.

Note that this covers a lot of interesting things, for instance PI has a random-looking distribution of digits, but is not random, because from the sequence it will be easy to predict, the observer will see it is PI and will predict the next digits with 100% accuracy.

Actually in this reasoning there is an "observer" that is the one that will try to come up with a model to improve the probability to guess the next item, but still I think it's an interesting way to define randomness, a lot more intuitive than talking about models.

Re: What is randomness? Nobody knows..

#27

Post by pierrebouchet »

jasomill wrote: post #21
pierrebouchet wrote: post #17

I think one of the most widely accepted definitions of randomness in mathematics was given by Martin-Löf. Basically it says that a process is random iff it doesn't exhibit any atypical property that you can test with an algorithm. In other words: if there is no computable way of proving that it's not random, then it is random.

How does this not trivially exclude everything (the first definition, not the circular restatement)? Considering that, say, a sequence of coin flips either has the property of "beginning with heads" or "beginning with tails," it certainly appears to.

My bad, I was being too vague - sorry for that.

I meant "any atypical property" instead of "any property".

An "atypical property" being a property that almost no sequence has, i.e the set of sequences which exhibit this propery is a measure-zero set.

Re: What is randomness? Nobody knows..

#28

Post by reizenikker »

antirez wrote: post #26

I think there is very good, and at the same time trivial , definition of how much random something is. Given any source of data, you define randomness the inverse of the ability of somebody observing the output sequence to guess what the next item will be. For instance in a stream of random bytes the observer will not be able to guess with more probability than 1/256 what the next byte will be, but if the sequence is…

Hi, Salvatore, Read http://www.amazon.com/Black-Swan-Nassim-Nicholas-Taleb/dp/14... this book, Nassim discover and explore for most of people the true meaning of randomness, and actually he show useless of "Mathematical true randomness" in real life. Highly recommend this book. And Yep, u are absolutely right, the random effect, is totally depends on how to look at it.

Re: What is randomness? Nobody knows..

#29

Post by antirez »

reizenikker wrote: post #28
antirez wrote: post #26

I think there is very good, and at the same time trivial , definition of how much random something is. Given any source of data, you define randomness the inverse of the ability of somebody observing the output sequence to guess what the next item will be. For instance in a stream of random bytes the observer will not be able to guess with more probability than 1/256 what the next byte will be, but if the sequence is…

Hi, Salvatore, Read http://www.amazon.com/Black-Swan-Nassim-Nicholas-Taleb/dp/14... this book, Nassim discover and explore for most of people the true meaning of randomness, and actually he show useless of "Mathematical true randomness" in real life. Highly recommend this book. And Yep, u are absolutely right, the random effect, is totally depends on how to look at it.

Thank you! I'll buy the book, it's a truly interesting subject :)

Re: What is randomness? Nobody knows..

#30

Post by Teapot »

powertower wrote: post #22

Randomness has at least one property... It can't be compressed. That is, it has no pattern.

Sometimes randomness spits out what we call patterns. 123456 seems like a pattern to us, and our beloved compression algos we wrote. But 123456 is just as random as any combo. I think. Right?

Related thinking, Sean Carroll on TED- Arrow of Time http://y2u.be/WMaTyg8wR4Y He says there's 'more' or 'less' entropy, but is there really such a thing? Rolling 6666666 on a dice, and we scream luck! But rolling 3164536 should be just as likely/unlikely.

Post reply on HN