1

I came across a computing function which gave me random output from a group of numbers. I've asked this question on StackOverflow. Do we really understand what is randomness? We can calculate probability of a particular event, we can plot the probability distribution and say that it is always a bell curve. But the curve itself is plotted after taking something natural, maybe a dice?

What if we were to explain a computer or a kid, about randomness, can we explain it? There's no method for computing something random, if we can compute it then how is it even random?

Does this have to deal with mathematical probability?

This topic seems broad to me, is it?

Community
  • 1
brainst
  • 345
  • (1,7). That's a random series. Prove to me that it's not random. (4, 19,-3). How is this one not random? What rule did I use to create it? (17,-222489943,0,0,1). What's not random about this one? How did I come up with these numbers? – CuriousOne Feb 20 '16 at 09:36
  • 1
    @CuriousOne I don't understand where are you leading me? – brainst Feb 20 '16 at 10:31
  • I am simply asking you how you would prove to me that these series are not random? How would you go about it to make a definitive statement that two numbers or twenty numbers or twenty billion numbers are not the result of a random process? All you could ever say is that, by YOUR definition of a random process, a certain series is unlikely to have been generated randomly. It's a judgement call and it's usually one that is driven by a technical need. There is no other, "more natural" definition. – CuriousOne Feb 20 '16 at 10:43
  • 1
    This is more of a mathematics question – Jaywalker Feb 20 '16 at 11:52
  • @Jaywalker : If we know the limits of the computation methods, algorithms may be seeded by physical measures and then it's a physicist question related to the differences between the randomness of a dice and of a quantum state –  Feb 20 '16 at 15:31

1 Answers1

3

The definition I find most satisfying is from Kolmogorov complexity (and pretty much rigorously axiomatizes your remark about computability). A string (or sequence of integers, etc) is random if no program shorter than that string can generate it. For example, 3.14159... is non-terminating, non-repeating, etc, but far from random. There are short programs that can sequentially emit the digits of $\pi$, one-by-one. On the other hand, truly random processes, let's say flipping a coin and generating (infinite in the limit) sequences like HTTHTHHH..., produces strings that can only be generated by a program which essentially stores and prints them, e.g., printf("HTTHTHHH...\n");. So the program's just as long as the string. If there were a shorter algorithm that generated the string, then it wouldn't be random wrt Kolmogorov complexity.

Edit: Coincidentally, there's a new arXiv article http://arxiv.org/abs/1602.06987 that uses Kolmogorov complexity/randomness to develop the authors' approach. (And it contains a (very) short introduction to the subject in Section II.)

  • How would you proof the non-existence of a short program that generates your random-looking sequence? – ScienceAndPhilosophy Feb 20 '16 at 10:51
  • @JohnForkosh I am interested in your answer. Is randomness to do with unpredictability? What you cannot predict with certainty is what the next coin toss will bring whereas you can predict with certainty what the next digit in the pi sequence will be. – Farcher Feb 20 '16 at 11:07
  • @ScienceAndPhilosophy That's not always provable, as far as I understand it, a la the usual incompleteness, noncomputability arguments, etc. So it's not always a constructive definition (again, as far as I understand it). You can see https://en.wikipedia.org/wiki/Kolmogorov_complexity for more complete discussion, in particular the section devoted to Kolmogorov randomness. –  Feb 20 '16 at 11:09
  • @Farcher You're asking "Is randomness...?", whereas I'm only remarking about one particular definition of randomness (which, like I said, "I find most satisfying"). By this definition, randomness >>explicitly<< has to do with non-computability rather than non-predictability, which was your (explicit) question. Does non-predictable$\Leftrightarrow$non-computable (or maybe one-way only)? Again, see the wikipedia page above for further discussion. Also, Chaitin's reprint book http://www.worldscientific.com/worldscibooks/10.1142/1048 is very readable and thorough. –  Feb 20 '16 at 11:19