6 ms·

The Quest for Randomness

70 points by ot 13y ago

Ono-Sendai 13y ago
Kolmogorov complexity as a measure of randomness / information content has problems in my opinion: http://www.forwardscattering.org/post/7 http://www.forwardscattering.org/post/7
- j2kun 13y ago
  I think your contention (if you're the author of this post) is misguided. In particular, the "languages" you define have the string hard coded in their definition, and are hence at least as long as the string you want to encode. In other words, your additive constant is not universal. The definition of Kolmogorov complexity is not with regard to whatever machine you want. You fix one and only one universal Turing machine U at the beginning, and then you measure the Kolmogorov complexity of a string using a different language with respect to U. Using your notation, K(x) is defined as K_U(x), and you can relate it to K_perl(x) by K_perl(x) + |perl interpreter written in U| = K_U(x). If you wanted to redefine all of Kolmogorov complexity using your L_{perl, i} language, you could do that just fine, but then it's your bad definition that makes the interpretation silly. Besides, if you pick an otherwise "random" string and single it out as being special, doesn't that intuitively make it no longer random?
  - Ono-Sendai 13y ago
    Thanks for the detailed reply, I'll ponder upon it and reply in a bit :)
  - Ono-Sendai 13y ago
    Hi, My overall point is that it matters which UTM you pick at the beginning.
- tromp 13y ago
  Your claimed definition: "The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages." is clearly wrong. You cannot take the minimum over all languages, or over all universal languages, because that leaves K() equal to a constant function. You really need to fix L. I tried to define the simplest possible language on which to base Kolmogorov complexity and ended up with http://en.wikipedia.org/wiki/Binary_lambda_calculus http://en.wikipedia.org/wiki/Binary_lambda_calculus
  - Ono-Sendai 13y ago
    Well my contention is that K(x) is constant, in fact K(x) = 0. The problem with fixing L is that it 'biases' the complexity based on the language chosen.
    - shasta 13y ago
      That bias with a fixed L is present, but you already mentioned the answer in your article: the difference is bounded. Compare to the situation with algorithm complexity. We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. We instead introduce Big-Oh and agree to ignore the differences in constants.
      - gwern 13y ago
        > We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. Unless you're Knuth!
      - Ono-Sendai 13y ago
        The difference is not really bounded in a meaningful way. The bound is large enough that the complexity can go to zero in some language.
Xcelerate 13y ago
Darn, the article stopped right before it got to the interesting part in my opinion. I love Scott Aaronson's writing and way of explaining things though. I was thinking how well this article was written before I looked at the author. Randomness is a subject that fascinates me, as I've been studying how it relates to quantum mechanics. I've arrived at the conclusion that a more useful word that "random" is "unpredictable".
- thibauts 13y ago
  And unpredictability depends on the information available to the observer. Thus randomness is objectively subjective.
- zhaphod 13y ago
  Scott writes very well. And he writes some of the lengthiest technical posts I have read. I find writing one paragraph of technical writing akin to chewing diamonds. Don't know how he does it. I have been lurking on his blog for some time and I have learned a great deal.
j2kun 13y ago
I wrote a more rigor-oriented article on Kolmogorov complexity a while back. HN readers might enjoy: http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-primer/ http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-prim... I too love Aaronson's writing style, so my work is no substitute for his insights.
cyborgx7 13y ago
At an intellectual level I have accepted that quantum mechanics truly are random, but in a small corner of my mind I still believe that the universe is deterministic.
- HCIdivision17 13y ago
  I think it's fair to say that's a reasonable coping mechanism for staying sane. QM notoriously has no everyday analog, whereas determinism holds up reasonably well in daily life!
  - cortesoft 13y ago
    I feel the opposite... determinism does NOT fit with my day to day observance, because my perception is that I have free will. If I accept determinism, I also have to accept that I actually don't have free will, and that seems contrary to my perception of myself.
    - beloch 13y ago
      So, what if some omnipotent trickster/adversary/god designed a deterministic universe specifically to fool you into thinking you have free will? I tend to believe in free will myself and I hate the above argument because I don't know of any way to refute it. As far as I know, the question of free-will vs determinism is unanswered. Even tests of randomness using Bell inequalities requires an assumption of free choice. It's... disquieting.
      - mamcx 13y ago
        Following that line, a deterministic universe is a better vehicle for free will that a truly random one. Why? Because a truly random one could self-kill, become one where will not exist anymore (of any kind), self-nullify itself, randomly chaos to laws and everything else. Have a stable "layer" for the universe is not (IMHO) a problem from a designed universe + free will, because the laws that make "free will" need to be stable to make sense and work!
0x0 13y ago
There's a challenge posted online to compress a file of one million presumably random digits, and it's been running for 10+ years without anyone claiming the prize: http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/ http://marknelson.us/2012/10/09/the-random-compression-chall...
- j2kun 13y ago
  Oh dear, now you've got me started trying to compress that.... EDIT: would this be an appropriate place to suggest my ideas for solutions?
- EzraVinh 13y ago
  If it was generated by a physical process, it might be possible that the signal has lower entropy than a truly random signal. It would be interesting to look at n-gram frequencies. First you would have to extract the original digits. Since log(10) * 10^6 / log(256) = 415241.01, and the binary file contains 415241 bytes, I assume that the binary file is produced by converting a million digit number to binary.
azth 13y ago
> As a first step, we could check whether the digits 0 through 9 appeared with approximately equal frequency, among, say, the first million digits. Passing such a test is clearly necessary for randomness... Why is that the case? This just means that the digits are uniformly distributed. Why can't they have a different distribution and still be "random"?
- j2kun 13y ago
  I think he is appealing to intuition here, where randomness means you can't predict the next drawn value with accuracy better than uniform. But you're right, you can draw randomly according to a different distribution. However, if you allow any distribution in your definition of "random" then you get the constant distributions. It's not very intuitively random anymore. So the question becomes, how do you pick which distributions are allowed and which aren't?
mrcactu5 13y ago
so much for i.i.d. random variables. we don't know if the variables are random and have no way to tell - definitely - if they are independent or identically distributed. i was always confused when cryptography textbooks only talk about pseudorandomness. probably `import random` is not sufficient for them and I was also confused by ergodic theory textbooks, which qualify levels of randomness like "equidistributed" or "3-fold mixing" but we can find dynamical systems which only go so far. that would be an interesting experiment to see what happens to the law of large numbers if the randomness bits are correlated.
kaa2102 13y ago
I've done some work with monte carlo and discrete event simulation. The runs/iterations produced utilize psuedo-random number generation. Many discrete-event simulation software platforms reproduce exactly the same numbers on a given run. Also, monte carlo simulation software like @Risk and CrystalBall enable users to select psuedo-random number generation methods. For instance, utilizing the Latin Hypercube method will sample more evenly from a Gaussian distribution rather than pulling more from the peak and tails.
throwaway21 13y ago
I think the guy working on TempleOS is basing his concept on the idea that computers can provide some sense of "randomness". Not really related, but I thought it was an interesting connection.

70 points by ot 13y ago

Kolmogorov complexity as a measure of randomness / information content has problems in my opinion: http://www.forwardscattering.org/post/7 http://www.forwardscattering.org/post/7

j2kun 13y ago
I think your contention (if you're the author of this post) is misguided. In particular, the "languages" you define have the string hard coded in their definition, and are hence at least as long as the string you want to encode. In other words, your additive constant is not universal. The definition of Kolmogorov complexity is not with regard to whatever machine you want. You fix one and only one universal Turing machine U at the beginning, and then you measure the Kolmogorov complexity of a string using a different language with respect to U. Using your notation, K(x) is defined as K_U(x), and you can relate it to K_perl(x) by K_perl(x) + |perl interpreter written in U| = K_U(x). If you wanted to redefine all of Kolmogorov complexity using your L_{perl, i} language, you could do that just fine, but then it's your bad definition that makes the interpretation silly. Besides, if you pick an otherwise "random" string and single it out as being special, doesn't that intuitively make it no longer random?
- Ono-Sendai 13y ago
  Thanks for the detailed reply, I'll ponder upon it and reply in a bit :)
- Ono-Sendai 13y ago
  Hi, My overall point is that it matters which UTM you pick at the beginning.
tromp 13y ago
Your claimed definition: "The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages." is clearly wrong. You cannot take the minimum over all languages, or over all universal languages, because that leaves K() equal to a constant function. You really need to fix L. I tried to define the simplest possible language on which to base Kolmogorov complexity and ended up with http://en.wikipedia.org/wiki/Binary_lambda_calculus http://en.wikipedia.org/wiki/Binary_lambda_calculus
- Ono-Sendai 13y ago
  Well my contention is that K(x) is constant, in fact K(x) = 0. The problem with fixing L is that it 'biases' the complexity based on the language chosen.
  - shasta 13y ago
    That bias with a fixed L is present, but you already mentioned the answer in your article: the difference is bounded. Compare to the situation with algorithm complexity. We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. We instead introduce Big-Oh and agree to ignore the differences in constants.
    - gwern 13y ago
      > We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. Unless you're Knuth!
    - Ono-Sendai 13y ago
      The difference is not really bounded in a meaningful way. The bound is large enough that the complexity can go to zero in some language.

Xcelerate 13y ago

Darn, the article stopped right before it got to the interesting part in my opinion. I love Scott Aaronson's writing and way of explaining things though. I was thinking how well this article was written before I looked at the author. Randomness is a subject that fascinates me, as I've been studying how it relates to quantum mechanics. I've arrived at the conclusion that a more useful word that "random" is "unpredictable".

thibauts 13y ago
And unpredictability depends on the information available to the observer. Thus randomness is objectively subjective.
zhaphod 13y ago
Scott writes very well. And he writes some of the lengthiest technical posts I have read. I find writing one paragraph of technical writing akin to chewing diamonds. Don't know how he does it. I have been lurking on his blog for some time and I have learned a great deal.

j2kun 13y ago

I wrote a more rigor-oriented article on Kolmogorov complexity a while back. HN readers might enjoy: http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-primer/ http://jeremykun.com/2012/04/21/kolmogorov-complexity-a-prim... I too love Aaronson's writing style, so my work is no substitute for his insights.

cyborgx7 13y ago

At an intellectual level I have accepted that quantum mechanics truly are random, but in a small corner of my mind I still believe that the universe is deterministic.

HCIdivision17 13y ago
I think it's fair to say that's a reasonable coping mechanism for staying sane. QM notoriously has no everyday analog, whereas determinism holds up reasonably well in daily life!
- cortesoft 13y ago
  I feel the opposite... determinism does NOT fit with my day to day observance, because my perception is that I have free will. If I accept determinism, I also have to accept that I actually don't have free will, and that seems contrary to my perception of myself.
  - beloch 13y ago
    So, what if some omnipotent trickster/adversary/god designed a deterministic universe specifically to fool you into thinking you have free will? I tend to believe in free will myself and I hate the above argument because I don't know of any way to refute it. As far as I know, the question of free-will vs determinism is unanswered. Even tests of randomness using Bell inequalities requires an assumption of free choice. It's... disquieting.
    - mamcx 13y ago
      Following that line, a deterministic universe is a better vehicle for free will that a truly random one. Why? Because a truly random one could self-kill, become one where will not exist anymore (of any kind), self-nullify itself, randomly chaos to laws and everything else. Have a stable "layer" for the universe is not (IMHO) a problem from a designed universe + free will, because the laws that make "free will" need to be stable to make sense and work!

0x0 13y ago

There's a challenge posted online to compress a file of one million presumably random digits, and it's been running for 10+ years without anyone claiming the prize: http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/ http://marknelson.us/2012/10/09/the-random-compression-chall...

j2kun 13y ago
Oh dear, now you've got me started trying to compress that.... EDIT: would this be an appropriate place to suggest my ideas for solutions?
EzraVinh 13y ago
If it was generated by a physical process, it might be possible that the signal has lower entropy than a truly random signal. It would be interesting to look at n-gram frequencies. First you would have to extract the original digits. Since log(10) * 10^6 / log(256) = 415241.01, and the binary file contains 415241 bytes, I assume that the binary file is produced by converting a million digit number to binary.

azth 13y ago

> As a first step, we could check whether the digits 0 through 9 appeared with approximately equal frequency, among, say, the first million digits. Passing such a test is clearly necessary for randomness... Why is that the case? This just means that the digits are uniformly distributed. Why can't they have a different distribution and still be "random"?

j2kun 13y ago
I think he is appealing to intuition here, where randomness means you can't predict the next drawn value with accuracy better than uniform. But you're right, you can draw randomly according to a different distribution. However, if you allow any distribution in your definition of "random" then you get the constant distributions. It's not very intuitively random anymore. So the question becomes, how do you pick which distributions are allowed and which aren't?

mrcactu5 13y ago

so much for i.i.d. random variables. we don't know if the variables are random and have no way to tell - definitely - if they are independent or identically distributed. i was always confused when cryptography textbooks only talk about pseudorandomness. probably `import random` is not sufficient for them and I was also confused by ergodic theory textbooks, which qualify levels of randomness like "equidistributed" or "3-fold mixing" but we can find dynamical systems which only go so far. that would be an interesting experiment to see what happens to the law of large numbers if the randomness bits are correlated.

kaa2102 13y ago

I've done some work with monte carlo and discrete event simulation. The runs/iterations produced utilize psuedo-random number generation. Many discrete-event simulation software platforms reproduce exactly the same numbers on a given run. Also, monte carlo simulation software like @Risk and CrystalBall enable users to select psuedo-random number generation methods. For instance, utilizing the Latin Hypercube method will sample more evenly from a Gaussian distribution rather than pulling more from the peak and tails.

throwaway21 13y ago

I think the guy working on TempleOS is basing his concept on the idea that computers can provide some sense of "randomness". Not really related, but I thought it was an interesting connection.