5 ms·

Kolmogorov Complexity - A Primer

101 points by vgnet 14y ago

deleted 14y ago
[deleted]
chimeracoder 14y ago
> So in a sense, the huge body of mathematics underlying probability has already failed us at this basic juncture because we cannot speak of how random one particular outcome of an experiment is. This reminds me of the 'Is 14 a random number?' debate. Part of the problem, though, is that we have terminology that is horribly misleading. First, a random variable is neither random nor a variable. They're not variables, because they're functions that yield non-deterministic values - a huge distinction. You can't have a random number - the idea itself doesn't make any sense. Second, the definition of 'random' is itself problematic - or at least contested. Randomness implies probability, but probability can be defined in two different (and incompatible) ways, one of which is essentially the inverse of the other. Ironically, the one that Keynes proved back in 1921 to be logically inconsistent is the one that is more commonly used today (probably because it is more intuitive and mathematically convenient... even if it is almost always incorrect!). The question 'Is 14 a random number' doesn't really make any sense. 14 cannot be a random number; it can only be a number drawn from a random distribution. That may seem like it simply begs the question, but in fact, this subtle shift is incredibly important - determining whether a number was drawn from a random distribution is much easier to frame in terms of probability, and probability, not randomness, is the language of statistics. Unfortunately, this is one of those cases where the two definitions of probability yield widely different answers. You could tell me that the answer is undefined, in almost exactly the same way that division-by-zero is undefined in mathematics. Or you could construct a model over all possible distributions of numbers, the probabilities associated with each of those distributions, and integrate accordingly to yield some (probably computationally unfeasible) functional answer. In this school of thought, we can speak of how 'random' a particular outcome is - we're essentially partitioning the (potentially infinite) universe of functions f such that our value v is in the range of f into two categories: one designated as 'random' and the other designated as 'not random'. Then, we are determining the probability that our value was generated from one of the former, as opposed to the latter. Either one would be correct ways of answering this second question, but neither one addresses the first question, which is essentially nonsensical. (Well, I guess the answer is 'no, 14 is not a random number, because a number cannot be random', but that's a bit of a cop-out!).
- dsr_ 14y ago
  You can also think of randomness as a measure of predictability: given our knowledge prior to being presented with this number, how well could we predict this number?
  - chimeracoder 14y ago
    You're thinking like a Bayesian - I avoided using those terms, but that's essentially the latter approach. The prior knowledge is built into the model with our choice of the functions and the weights that we assign those functions. (It should be noted that the Bayesian approach doesn't guarantee a defined answer - we can easily have a divide-by-zero/undefined value in that school of thought as well. However, the frequentist approach always leads to an undefined outcome in this question, because it follows from the definition of probability itself, whereas in the Bayesian approach, it follows from insufficient information in the model specification.)
- MathProgramming 14y ago
  I think I made the point to say that random only applies to things being drawn from a distribution, but that's really the whole point of the theory: we _want_ to be able to talk about how random a number is! We just call it 'Kolmogorov random' now, and by luck or insight, numbers chosen uniformly at random are almost always Kolmogorov random.
  - chimeracoder 14y ago
    I'm assuming you're the author of the original post. My comment wasn't meant to invalidate your main argument, since it runs mostly orthogonal to the bulk of what you're saying. If anything, it actually supports it slightly (see below). I understand what you meant by that example; I was just intrigued by seeing it in this context, and it reminded me of the related example that I brought up. And not to belabor the point with pedantry, but a tiny bit of rephrasing illustrates that your statement can be viewed as completely compatible with my latter definition: > numbers chosen from a random uniform distribution function appear to be indistinguishable from numbers chosen from a Kolmogorov random function From the looks of it, it appears that the Kolmogorov example is really just a special case of the distributional viewpoint, in which case your system of partitioning the universe of possible distributions revolves around the Kolmogorov criterion. (And while I made it seem like the partitioning is binary in my previous post, the principle can easily be generalized, so that's not a problem). And we may even be able to equate this statement with an alternate form based on the distributional difference between uniform and Kolmogorov. I'm familiar with Kolmogorov, though not enough to be confident about this last hypothesis - I'll have to think about it some more.
dsr_ 14y ago
Mentioning the pigeonhole principle by name might have been useful. It almost got defined here...
deleted 14y ago
[deleted]
andrewcooke 14y ago
if people find that interesting, they might enjoy this book - http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://www.amazon.com/The-Computational-Beauty-Nature-Explorations/dp/0262561271 http://www.amazon.com/The-Computational-Beauty-Nature-Explor...
archgoon 14y ago
Well, I guess it basically goes to show how hard it is to determine the actual kolmogorov complexity (even once specifying a particular encoding of a Turing Machine) of a string, but the following is a new upper bound on the complexity (in Python) of the second string. print '00011101001000101101001000101111010100000100111101' print bin(128141569638717)[2:] In general, any string of 1s and 0s will be compressible using this method in python once the binary number is greater than 212 (you break even at 211). However, again, I only claim this to be an upperbound ;). (also assuming that invoking built-ins isn't cheating).
- MathProgramming 14y ago
  In the context of Turing machines, the output is really a _binary_ string, not a string of arbitrary characters. So in a sense, those two programs are the same thing. But of course, the Kolmogorov complexity of any number n is bounded by log(n) + c.
- mmphosis 14y ago
  print "000"+bin(0x748b48bd413d)[2:]
  - archgoon 14y ago
    ah... good catch :)
strictfp 14y ago
With the given definition I assume that it would be impossible to have a Kolmogorov complexity higher than the size of the smallest PRNG program (+seed)? If so it might be of limited usefulness for larger strings.
- ajuc 14y ago
  PRNGs are not interchangeable, they produce different subsets of all possible strings (let's define result of PRNG+seed as all the bits of generated numbers concatenated, until PRNG starts to repeat). And any program returning something can be seen as a PRNG (at worst it won't accept seed, so it will only produce one string).
  - strictfp 14y ago
    True. What you say must imply that no PRNG-generated sequence has a particularly high K complexity (> len(PRNG)). What still interests me in this scenario is that a true random source can still generate the same sequence as a PRNG. In that case the complexity of the string becomes small. So for a given true random source you can still get strings with low K complexity. Does this affect cryptography in any way?
    - ajuc 14y ago
      No, because cryptography just wants to ensure that given all past bits of generator output you can't predict future bit with probability different than 0.5. And besides, overwhelming majority of strings are random, once you got to strings long enough. Probabilty that random generator will make not Kolmogorov random string is 0.
eevilspock 14y ago
I'm no expert, but information theory answers the question of "randomness" more simply, intuitively and rigorously. This notion of Kolmogorov Complexity doesn't seem to add any additional value.

101 points by vgnet 14y ago

deleted 14y ago

[deleted]

> So in a sense, the huge body of mathematics underlying probability has already failed us at this basic juncture because we cannot speak of how random one particular outcome of an experiment is. This reminds me of the 'Is 14 a random number?' debate. Part of the problem, though, is that we have terminology that is horribly misleading. First, a random variable is neither random nor a variable. They're not variables, because they're functions that yield non-deterministic values - a huge distinction. You can't have a random number - the idea itself doesn't make any sense. Second, the definition of 'random' is itself problematic - or at least contested. Randomness implies probability, but probability can be defined in two different (and incompatible) ways, one of which is essentially the inverse of the other. Ironically, the one that Keynes proved back in 1921 to be logically inconsistent is the one that is more commonly used today (probably because it is more intuitive and mathematically convenient... even if it is almost always incorrect!). The question 'Is 14 a random number' doesn't really make any sense. 14 cannot be a random number; it can only be a number drawn from a random distribution. That may seem like it simply begs the question, but in fact, this subtle shift is incredibly important - determining whether a number was drawn from a random distribution is much easier to frame in terms of probability, and probability, not randomness, is the language of statistics. Unfortunately, this is one of those cases where the two definitions of probability yield widely different answers. You could tell me that the answer is undefined, in almost exactly the same way that division-by-zero is undefined in mathematics. Or you could construct a model over all possible distributions of numbers, the probabilities associated with each of those distributions, and integrate accordingly to yield some (probably computationally unfeasible) functional answer. In this school of thought, we can speak of how 'random' a particular outcome is - we're essentially partitioning the (potentially infinite) universe of functions f such that our value v is in the range of f into two categories: one designated as 'random' and the other designated as 'not random'. Then, we are determining the probability that our value was generated from one of the former, as opposed to the latter. Either one would be correct ways of answering this second question, but neither one addresses the first question, which is essentially nonsensical. (Well, I guess the answer is 'no, 14 is not a random number, because a number cannot be random', but that's a bit of a cop-out!).

dsr_ 14y ago
You can also think of randomness as a measure of predictability: given our knowledge prior to being presented with this number, how well could we predict this number?
- chimeracoder 14y ago
  You're thinking like a Bayesian - I avoided using those terms, but that's essentially the latter approach. The prior knowledge is built into the model with our choice of the functions and the weights that we assign those functions. (It should be noted that the Bayesian approach doesn't guarantee a defined answer - we can easily have a divide-by-zero/undefined value in that school of thought as well. However, the frequentist approach always leads to an undefined outcome in this question, because it follows from the definition of probability itself, whereas in the Bayesian approach, it follows from insufficient information in the model specification.)
MathProgramming 14y ago
I think I made the point to say that random only applies to things being drawn from a distribution, but that's really the whole point of the theory: we _want_ to be able to talk about how random a number is! We just call it 'Kolmogorov random' now, and by luck or insight, numbers chosen uniformly at random are almost always Kolmogorov random.
- chimeracoder 14y ago
  I'm assuming you're the author of the original post. My comment wasn't meant to invalidate your main argument, since it runs mostly orthogonal to the bulk of what you're saying. If anything, it actually supports it slightly (see below). I understand what you meant by that example; I was just intrigued by seeing it in this context, and it reminded me of the related example that I brought up. And not to belabor the point with pedantry, but a tiny bit of rephrasing illustrates that your statement can be viewed as completely compatible with my latter definition: > numbers chosen from a random uniform distribution function appear to be indistinguishable from numbers chosen from a Kolmogorov random function From the looks of it, it appears that the Kolmogorov example is really just a special case of the distributional viewpoint, in which case your system of partitioning the universe of possible distributions revolves around the Kolmogorov criterion. (And while I made it seem like the partitioning is binary in my previous post, the principle can easily be generalized, so that's not a problem). And we may even be able to equate this statement with an alternate form based on the distributional difference between uniform and Kolmogorov. I'm familiar with Kolmogorov, though not enough to be confident about this last hypothesis - I'll have to think about it some more.

dsr_ 14y ago

Mentioning the pigeonhole principle by name might have been useful. It almost got defined here...

deleted 14y ago

[deleted]

andrewcooke 14y ago

if people find that interesting, they might enjoy this book - http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://mitpress.mit.edu/books/FLAOH/cbnhtml/ http://www.amazon.com/The-Computational-Beauty-Nature-Explorations/dp/0262561271 http://www.amazon.com/The-Computational-Beauty-Nature-Explor...

archgoon 14y ago

Well, I guess it basically goes to show how hard it is to determine the actual kolmogorov complexity (even once specifying a particular encoding of a Turing Machine) of a string, but the following is a new upper bound on the complexity (in Python) of the second string. print '00011101001000101101001000101111010100000100111101' print bin(128141569638717)[2:] In general, any string of 1s and 0s will be compressible using this method in python once the binary number is greater than 212 (you break even at 211). However, again, I only claim this to be an upperbound ;). (also assuming that invoking built-ins isn't cheating).

MathProgramming 14y ago
In the context of Turing machines, the output is really a _binary_ string, not a string of arbitrary characters. So in a sense, those two programs are the same thing. But of course, the Kolmogorov complexity of any number n is bounded by log(n) + c.
mmphosis 14y ago
print "000"+bin(0x748b48bd413d)[2:]
- archgoon 14y ago
  ah... good catch :)

strictfp 14y ago

With the given definition I assume that it would be impossible to have a Kolmogorov complexity higher than the size of the smallest PRNG program (+seed)? If so it might be of limited usefulness for larger strings.

ajuc 14y ago
PRNGs are not interchangeable, they produce different subsets of all possible strings (let's define result of PRNG+seed as all the bits of generated numbers concatenated, until PRNG starts to repeat). And any program returning something can be seen as a PRNG (at worst it won't accept seed, so it will only produce one string).
- strictfp 14y ago
  True. What you say must imply that no PRNG-generated sequence has a particularly high K complexity (> len(PRNG)). What still interests me in this scenario is that a true random source can still generate the same sequence as a PRNG. In that case the complexity of the string becomes small. So for a given true random source you can still get strings with low K complexity. Does this affect cryptography in any way?
  - ajuc 14y ago
    No, because cryptography just wants to ensure that given all past bits of generator output you can't predict future bit with probability different than 0.5. And besides, overwhelming majority of strings are random, once you got to strings long enough. Probabilty that random generator will make not Kolmogorov random string is 0.

eevilspock 14y ago

I'm no expert, but information theory answers the question of "randomness" more simply, intuitively and rigorously. This notion of Kolmogorov Complexity doesn't seem to add any additional value.