1
$\begingroup$

A comment was made to me saying the following in relation to Kolmogorov complexity:-

You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular to random, "non-algorithmic" data.

I now have a physical box on my bench that outputs perfectly random bytes with the following distribution:-

histogram

I'm trying to estimate the entropy rate of this box, and the problem is that these bytes are highly correlated. Very highly. I can't stress that enough. They are not independent nor identically distributed and arrive in blocks of 20,000ish bytes but that length varies randomly too.

How can Mr. Kolmogorov be useful to me with measuring this "non-algorithmic" data?

How to practically measure entropy of a file? has not yielded a practical answer so far.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

How can Kolmogorov complexity be useful to you in measuring the complexity of this data? It can't. The Kolmogorov complexity of a sequence of bytes is not computable.

Don't read too much into that comment. I'd take it as hinting that the idea of Kolmogorov complexity might be a relevant or interesting concept to know about, not necessarily that you can directly compute that value in a particular real-life situation. Anyway, just because someone wrote something doesn't mean it's true. If you're not sure what they meant by it, or you are wondering what justification they had for saying that, you might need to ask them.

I notice that Yuval Filmus's answer to the question you linked to provided a similar summary of Kolmogorov complexity, so I'm a bit confused about what is unclear here.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The comment was not made in isolation though. I've repeatedly asked across several of the .SE sites about measuring real world entropy from devices, and the answers tend to revert to hypothetical technobabble about KC. They then always end with "algorithmic entropy isn't computable", whereas I'm expecting a numeric value in bits /Shannons. When I suggest using compression, they say that's an upper bound. When I ask what's a lower bound, they say KC and off we go again. Perhaps entropy is just too hard. $\endgroup$
    – Paul Uszak
    Commented Aug 17, 2018 at 10:13
  • $\begingroup$ I guess the underlying answer to all my questions must be that I need to look elsewhere. It's enough to drive a chap to write long comments :-) $\endgroup$
    – Paul Uszak
    Commented Aug 17, 2018 at 10:13
  • $\begingroup$ @PaulUszak, I understand. My view is that KC is for the most part not useful in practice. I think you've already gotten a similar view before in one answer (cs.stackexchange.com/a/45475/755). Comments are second-class citizens here; they can't be voted down, so don't rely on them to be necessarily correct. And there's always the general principle of "don't necessarily believe everything you read on the Internet". :-) Yes, this is just too hard; there is in general no way to measure entropy like you are hoping for, at least not from the data. $\endgroup$
    – D.W. ♦
    Commented Aug 17, 2018 at 15:47
  • $\begingroup$ This notion of "not from the data" is also niggling. I have a physical box. It uses quantum mechanics to produce this totally random output that I graphed. There is nothing else but data sampling. The output is correlated due to physics and the unalterable sampling methodology outside of my control. So the Shannon summy log(p) thing can't be used as there is no easy way to determine p. Is no one working on this? Anywhere? The data storage industry? Comms? Cryptographers? PKZIP staffers? Really, no one? Thanks anyway :-) $\endgroup$
    – Paul Uszak
    Commented Aug 18, 2018 at 10:26
  • $\begingroup$ @PaulUszak, there's probably no one working on it because you can't do it that way. It's not for lack of effort -- it's a fundamental barrier -- there is no reliable way to estimate the entropy of a source given just observations/samples from the source. $\endgroup$
    – D.W. ♦
    Commented Aug 18, 2018 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.