What is randomness? Nobody knows.. | Hacker News Reader

What is randomness? Nobody knows..

johndcook.com

38 pointsgnosis38 comments

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.

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 :)

Yep, exactly! Especially u can look on more common topic like success, and part of probability in it.

And sorry, they already have a second edition: http://www.amazon.com/gp/product/081297381X/ref=pd_lpo_k2_dp... ,

after this book, i highly recommend read his another book: fooled by randomness

You can in the same way argue that PI was random, but is not anymore now that it is known. The same could be said about any random sequence, like the tables of random numbers in calculus books or known PRNGs with known seeds.

Randomness is an interesting topic indeed.

For instance, up until 2012 introduced with Ivy Bridge, a true hardware-based random number generator hasn't been available to the masses. (http://en.wikipedia.org/wiki/RdRand)

what we believe to be random may not be, and I've seen UUIDs generated on cheap mobile devices can easily collide when their clock battery is dead.

There is also a measure of deegre of accuracy: if we have a sequence that is repeat(1..100), a predictor that always says 100 will be 1% accurate, while a prediction of repeat(2..101) will never be accurate but alway off just by one.

If I give you the sequence 3.14159265, you will glance at it and say "Pi" and predict 35 as the next digits.

If I give you 7, 5, 8, 5, 9, 13, 6, 10, 9, you may not see the pattern at all, when it's "digit of pi + 4", and therefore is as predictable.

Your definition seems to depend on the intelligence of the observer. Is that measuring "how much random something is" or "how clever the viewer is"? (And, is there a difference?)

You can simply assume the cleverest observer, but actually it's not just about smartness (ability to compute / recognize) but also the amount of data the observer has access to. For instance in a PRNG where I use some kind of source of entropy, like delay between user keystrokes, an observer that is able to watch the user typing can predict the sequence, another can not.

The right question isn’t “is this system random?” but rather “is it useful to model this system as random?”

I couldn't agree more on this. As George E.P. Box put it, "Essentially, all models are wrong, but some are useful".

I love when financial types talk about a "20% chance" of X happening (like earnings miss, default, etc) If you are familiar with the postulates of probability, you realize that they are talking out of their butts, and are trying to sound oh-so-precise-and-mathematical.

Much of the financial world is about the appearance of quantitative thinking and not actual quantitative thinking.

It is better to be wrong than to be vague. --Freeman Dyson

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."

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.

Randomness should be a function of both a numeric series and an agent. It should measure the ability of a given agent to predict the next element in the series.

Good article. I liked the points made, especially the comparison to continuous variables.

The argument about "true" randomness versus psuedo-randomness is very interesting. As the dilbert comment posted elsewhere points out, it's impossible to really know how "random" something is, because if it matches your expectations, then it isn't.

So it's hard even to compare "true" random number generators and psuedo-ones. You might even argue that PRNGs are better in some cases because you can make provable statements about the distribution of their output. (Of course, those statements might depend on the seed being "random"....)

Anyway, I guess the takeaway is that, as the author says, randomness is poorly understood; instead, we can only make statements about random numbers and probabilities and do our best to reconcile those with what we have to work with in real life. This seems like poor comfort to academics who rely on some formal notion of randomness that is unachievable, but on the other hand randomness seems to always work "well enough" in practice.....

I tend to think of randomness as a quantitative measurement of our ignorance of the world.

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

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.

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?

No. There are plenty of random variables without non-uniform distributions. Plus an event in probability theory is not what you think it is. An event can be any subset of the sample space.

The behaviour that dice and spinners and coins are trying to emulate is precisely what dsthysd said. In each case you hope that the faces of the die, sections of the spinner, and sides of the coin are equally likely each time.

I don't think I'm being unrealistic, how can learning more about probability theory change the conventional definition of random?

Isn't the real difficulty in trying to make a non-deterministic system out of a computer, since all we ever do with computers is feed instructions into them?

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!?!?)? Enter philosophy land.

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!

That's how science works. If you keep asking why & digging deeper, you eventually reach something that hasn't been "explained" in terms of something else.

nothing is really random in an absolute way, when we have stuff that is very complex or hard to compute and we can't figure out what it is we call it random

Well, maybe quantum indeterminacy.

Reminds me of the question of consciousness.

they are related, what is free will?

You could be conscious and live under the illusion of free will...

That's unlikely, though. See http://www.ams.org/notices/200902/rtx090200226p.pdf

I keep reading that sentence. I guess I had no choice in the matter. What is free will?

Both may be related.

A major candidate for the physical substrate of consciousness is the ability for a system to integrate information, thereby locally reducing its entropy and thus its randomness, at the expense of its environment.

- Consciousness as Integrated Information: a Provisional Manifesto; Giulio Tononi; http://www.biolbull.org/content/215/3/216.long

- Integrated Information in Discrete Dynamical Systems: Motivation and Theoretical Framework; David Balduzzi, Giulio Tononi; http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...

- Qualia: The Geometry of Integrated Information; David Balduzzi, Giulio Tononi; http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...

http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...

- A perturbational approach for evaluating the brain's capacity for consciousness; Marcello Massimini1, Melanie Boly, Adenauer Casali1, Mario Rosanova1, Giulio Tononi; http://www.coma.ulg.ac.be/papers/vs/massimini_PBR_coma_scien... - http://www.sciencedirect.com/science/article/pii/S0079612309...

- Granger Causality Analysis of Steady-State Electroencephalographic - Signals during Propofol-Induced Anaesthesia; Adam B. Barrett, Michael Murphy, Marie-Aurélie Bruno, Quentin Noirhomme, Mélanie Boly, Steven Laureys, Anil K. Seth1; http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjourna...

- Hierarchical clustering of brain activity during human nonrapid eye movement sleep; Mélanie Boly, Vincent Perlbargb, Guillaume Marrelec, Manuel Schabus, Steven Laureys, Julien Doyon, Mélanie Pélégrini-Issacb, Pierre Maquet, and Habib Benalib; http://www.pnas.org/content/109/15/5856.short

Relevant xkcd: http://xkcd.com/221/

Reminds me of the delbert comic: http://dilbert.com/strips/comic/2001-10-25/

Reply on news.ycombinator.com