2
$\begingroup$

Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a statistical/thermal physics point of view, but now I'm trying to understand how it is applied for real computers.

Normally the messages we want to store and process in a computer have grammar and meanings, which seems to suggest the symbols constituting the message must follow some conditional probability distribution, and the utterance of the symbol at the nth position should change the probability distribution of the symbol that will appear at the (n+1)-th position. However, in Shannon's definition symbols are assumed to be independent and identically distributed random variables, which seems to be far from realistic, so how come it is still a useful concept for computers?

$\endgroup$
  • 1
    $\begingroup$ Where is this assumption made? As far as I know, independence isn't assumed for entropy in information theory, we even have the case of conditional Shannon entropy, which would be useless to define if independence was an assumption. Can you state the definition here and where you found it? $\endgroup$ – Discrete lizard Apr 15 '18 at 21:20
  • $\begingroup$ @Discretelizard,for example I'm looking at this definition: en.wikipedia.org/wiki/Entropy_(information_theory)#Definition. Here it uses a single random variable $X$, but if one takes each position of a string of symbols to be a random variable, then this is the same as saying these random variables are i.i.d. $\endgroup$ – Jia Yiyang Apr 16 '18 at 0:25
  • $\begingroup$ Your conclusion that the individual symbols must be iid does not follow, as D.W. states. If you wish to know why this is the case, please edit your question with your reasoning why you think these symbols must be iid. $\endgroup$ – Discrete lizard Apr 16 '18 at 9:54
3
$\begingroup$

No. Shannon's definition is perfectly general.

There is a special case when the symbols are iid random variables, and you might have seen a formula for that special case (which is indeed simpler), but the definition is fully general. Note that when we write the entropy $H(X)$, you should take the random variable $X$ to be the entire sequence of symbols. Then the standard definition applies directly, and doesn't assume that each individual symbol in $X$ is iid.

$\endgroup$
  • $\begingroup$ I see,, +1, in physics language I misunderstood "ensembles" as "levels". This brings me the next question, in a real computer, when I see a file has size say 5MB, exactly what is the random variable $X$? It probably depends on the type of the file? For txt files, since I heard each letter is assigned a fixed amount of bits, it probably means the random variable in this case is just single letters. $\endgroup$ – Jia Yiyang Apr 16 '18 at 16:28
  • $\begingroup$ @JiaYiyang, asking about the (Shannon) entropy of a file does not make sense and is not well-defined. What is well-defined is the entropy of a random process. The random process defines a random variable $X$ (a distribution), and then you can calculate the (Shannon) entropy of that random variable. So if you told me "I have a process for generating a random file; what is the entropy of that process?", that would be an answerable question. If you tell me "I have a file, what is the (Shannon) entropy of that file?", that's not answerable, as the notion isn't even well-defined. $\endgroup$ – D.W. Apr 16 '18 at 16:53
  • $\begingroup$ That makes sense. However when I see a file which is labeled to have 5MB content, is that "5MB" not some sort of information entropy? Or is it that there is always some presumed random process associated with it? $\endgroup$ – Jia Yiyang Apr 17 '18 at 0:29
  • $\begingroup$ @JiaYiyang, I don't know what you mean by "labeled to have 5MB content". Who did that labeling, and what do they mean by it? If you mean that the file is 5MB long, that's a statement about its length, not its entropy. (Of course, the length gives an upper bound on the entropy, but it is not itself a value for the entropy, as the actual entropy could be smaller.) If you mean something else, I suspect you'd have to tell us where that label came from, what it means, and how it was computed. $\endgroup$ – D.W. Apr 17 '18 at 5:01
  • $\begingroup$ If I right-click a file and look into "properties", one of the attributes of this file is "size", let say this "size" is labeled "5MB". $\endgroup$ – Jia Yiyang Apr 17 '18 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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