3
$\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?

Improve this question
$\endgroup$
5
  • 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 ♦
    Commented Apr 15, 2018 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
    Commented Apr 16, 2018 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 ♦
    Commented Apr 16, 2018 at 9:54
  • $\begingroup$ @Discretelizard, I upvoted questions and answer because these clarified some of my doubts. Thank you! Anyway, I'm interested in your comment "we even have the case of conditional Shannon entropy, which would be useless to define if independence was an assumption". What do you mean? I can open another question on the forum if you like. $\endgroup$
    – Mark
    Commented May 7, 2021 at 6:40
  • $\begingroup$ @Mark It's been a while, but I believe what I meant was that if two random variables $X,Y$ are independent, then the conditional entropy between them is equal to the ordinary entropy of one of them, i.e. $H(X\mid Y) = H(X)$. ($H(X\mid Y)$ is the conditional entropy of $X$ given $Y$). So, if the variables always are required to be independent, the conditional entropy doesn't give more information than the ordinary entropy. In hindsight, I'm not sure how relevant that remark was on this question, as I think it wasn't clear to me which independent random variables where asked about. $\endgroup$
    – Discrete lizard ♦
    Commented Jul 11, 2021 at 17:02

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Apr 16, 2018 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. ♦
    Commented Apr 16, 2018 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
    Commented Apr 17, 2018 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. ♦
    Commented Apr 17, 2018 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
    Commented Apr 17, 2018 at 15:20

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.